写一个快速排序c++
时间: 2023-03-01 16:01:43 浏览: 60
快速排序是一种基于分治的排序算法。它的基本思想是:
1. 先从数列中取出一个数作为基准数。
2. 分区过程,将比这个数大的数全部放到它的右边,小于或等于它的数全部放到它的左边。
3. 再对左右区间重复第二步,直到各区间只有一个数。
下面是快速排序的 C 语言代码实现:
```
void quick_sort(int *arr, int left, int right)
{
if (left >= right) { // 如果数组为空或只有一个元素,就不用排序了
return;
}
int i = left;
int j = right;
int pivot = arr[left]; // 取最左边的数为基准数
while (i < j) {
while (i < j && arr[j] >= pivot) { // 从右往左找第一个小于基准数的数
j--;
}
arr[i] = arr[j]; // 交换基准数和右边的数
while (i < j && arr[i] <= pivot) { // 从左往右找第一个大于基准数的数
i++;
}
arr[j] = arr[i]; // 交换基准数和左边的数
}
arr[i] = pivot; // 把基准数放到中间
quick_sort(arr, left, i - 1); // 递归排序左半边
quick_sort(arr, i + 1, right); // 递归排序右半边
}
```
使用的时候,只需要调用 `quick_sort(arr, 0, n - 1)` 即可对数组 `arr` 进行排序,其中 `n` 为数组的长度。