1.快速排序的概念
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
[size=18.7879px] [size=18.7879px]2.核心操作有两步
[size=18.7879px] [size=18.7879px]①通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。
[size=18.7879px] ②再按此方法对这两部分数据分别进行快速排序。
3.C语言代码实现
void sort(int *a, int left, int right) {
int i = left;
int j = right;
int key = a[left];
// 1.递归条件判断（判断该部分是否是有序的）
if(left >= right)
{
return ;
}
// 2.快速排序：只需将数组中比 key 小的放在 key 的左边，比 key 大的放在 key 的右边（交换位置：蓝色部分）
while(i < j)
{
while(i < j && key <= a[j])
{
j--;
}
a = a[j];
while(i < j && key >= a)
{
i++;
}
a[j] = a;
}
a = key;
// 2.递归分别将左部分，右部分排序
sort(a, left, i - 1);
sort(a, i + 1, right);
} |
