如何用C++写快速排序?
时间: 2023-01-11 22:55:36 浏览: 65
快速排序是一种基于分治的排序算法。它的基本思想是:
1. 从数列中选择一个基准数。
2. 将所有小于基准数的数放在它的左边,所有大于基准数的数放在它的右边。
3. 对基准数左右两边的数列分别进行快速排序,直到每个数列只剩下一个数。
下面是 C 语言实现的快速排序的代码:
```
#include <stdio.h>
void quick_sort(int array[], int left, int right) {
if (left >= right) {
return;
}
int pivot = array[left];
int i = left;
int j = right;
while (i < j) {
while (i < j && array[j] >= pivot) {
j--;
}
array[i] = array[j];
while (i < j && array[i] <= pivot) {
i++;
}
array[j] = array[i];
}
array[i] = pivot;
quick_sort(array, left, i - 1);
quick_sort(array, i + 1, right);
}
int main() {
int array[] = {3, 5, 1, 4, 2};
quick_sort(array, 0, 4);
for (int i = 0; i < 5; i++) {
printf("%d ", array[i]);
}
printf("\n");
return 0;
}
```
在这段代码中,我们将数组的第一个数作为基准数。然后使用双指针法将数组分为左右两部分,左边的数都小于基准数,右边的数都大于基准数。最后,我们对基准数的左右两边的数列分别进行快速排序。