用c++写一个类似于stl库sort的快排
时间: 2023-03-21 19:01:27 浏览: 58
下面是使用 C 语言实现的快速排序函数,与 STL 库中的 std::sort 函数类似:
```c
#include <stdio.h>
void quicksort(int arr[], int left, int right) {
if (left >= right) return;
int pivot = arr[right];
int i = left - 1, j = left;
for (; j < right; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
quicksort(arr, left, i);
quicksort(arr, i + 2, right);
}
int main() {
int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
quicksort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
该函数的参数包括要排序的数组、数组的左边界和右边界。在函数内部,首先判断左右边界是否已经重合,如果是,则说明只有一个元素,直接返回。选择最右边的元素作为枢轴(pivot),设置两个指针 i 和 j,开始遍历数组。
遍历过程中,如果当前元素 arr[j] 小于枢轴 pivot,则将其与指针 i 的下一个元素交换,这样,i 的左侧的元素都小于 pivot。最后,将枢轴与 i 的下一个元素交换,这样枢轴就在数组的正确位置上。
接下来,对左右两个子数组进行递归快排。需要注意的是,右子数组的左边界为 i+2,因为枢轴已经在位置 i+1 上。
在主函数中,使用示例数组进行排序,并输出排序结果。