算法思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

1、首先设定一个基准，通过该分界值将数组分成左右两部分。

2、将大于或等于基准的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于基准。

3、然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个基准，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4、重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

概括来说为 挖坑填数 + 分而治之。

算法图解

代码实现

#include <stdio.h>
#define N 10

// 函数声明
void quickSort(int arr[], int left, int right);

int main() {
// 标准的输入输出不需要缓存，直接输出
setbuf(stdout, NULL);

int arr[N] = {4, 3, 8, 2, 1, 7, 5, 6, 9, 0};

quickSort(arr, 0, N - 1);

printf("数组升序排列：");
for (int i = 0; i < N; ++i) {
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}

/**
* 快速排序
*/
void quickSort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int l = left, r = right;
int base = arr[left];
while (l < r) {
// 依次从右边判断元素是否比基准大，如果比基准大：右边指针往前走
while (l < r && arr[r] >= base) {
r--;
}
// 出并列的while循环：从右边比较时已经遇到比基准小的值【替换左边的值】
arr[l] = arr[r];
// 依次从左边判断元素是否比基准小，如果比基准小：左边指针往后走
while (l < r && arr[l] <= base) {
l++;
}
// 出并列的while循环：从左边比较时已经遇到比基准大的值【替换右边的值】
arr[r] = arr[l];
}
// 出并列的while循环：当前这一趟已经比较完毕，比基准大的在基准下标的右边，比基准小的在基准下标的左边
arr[r] = base;
// 递归排序左边
quickSort(arr, left, r - 1);
// 递归排序右边
quickSort(arr, r + 1, right);
}

运行结果