这篇文章上次修改于 398 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
1 背景
我们都知道，算法是解决实际问题的步骤，是前人智慧的结晶。那么为什么会有快速排序呢？这就需要了解下传统排序算法的缺点。传统的排序算法有冒泡排序、选择排序和插入排序。它们的共同点就是两两比较，算法的时间复杂度高达 O(n^2)，不适合大规模排序。我们接下来来看下时间复杂度仅为 O(nlogn) 的快速排序算法，它用到了分治思想，非常巧妙。
2 核心思想
分治，顾名思义，就是分而治之，将一个大的问题分解成 n 个规模较小，且结构与原问题相似的子问题，递归地解决这些子问题后，然后再合并其结果，就得到原问题的解。有的同学可能会发现这跟递归的定义有点像，是的，分治算法一般是用递归来实现的。分治是一种处理问题的思想，递归是一种编程技巧，两者并不冲突。
快速排序的步骤：
- 在数组中选定 pivot（分区点）
- 将小于 pivot 的数字移到 pivot 的左边
- 将大于 pivot 的数字移到 pivot 的右边
- 分别对左右子序列重复前面 3 步
3 案例
接下来我们通过一个例子来一起看下快速排序的过程。
假设有 5 个数字：3, 1, 5, 2, 4。
让我们选一个数字作为 pivot，有多种选择 pivot 的方式，最简单的方式选择第 1 个数字作为 pivot，即选取 3 作为 pivot，并记住它的位置，这个位置就相当于是一个坑：
[ ], 1, 5, 2, 4
设置左右两个指针分别指向数组的最左和最右两个元素：
[ ], 1, 5, 2, 4
￪ ￪
先从右边的指针开始，把右指针指向的元素与 pivot 进行比较。如果右指针指向的元素 >= pivot，则把右边的指针向左移动：
[ ], 1, 5, 2, 4
￪ ￪
如果右指针指向的元素 < pivot，则将右指针指向的元素 2 填入坑中：
2, 1, 5, [ ], 4
￪ ￪
这个时候，2 之前所在的位置成为了新的坑。同时，左指针向右移动一位：
2, 1, 5, [ ], 4
￪ ￪
此时，左指针左边的区域代表小于 pivot 的区域。
接下来将左指针指向的元素与 pivot 进行比较。如果左指针指向的元素 <= pivot，则左指针向右移动：
2, 1, 5, [ ], 4
￪ ￪
如果左指针指向的元素 > pivot，则左指针指向的元素填入坑中：
2, 1, [ ], 5, 4
￪ ￪
这时候 5 之前所在的位置成为了新的坑，同时右指针向左移动一位：
2, 1, [ ], 5, 4
￪￪
此时，右指针右边的区域代表大于 pivot 的区域。
当左右指针重合时，可以把 pivot 也就是 3 放到指针重合的位置上：
2, 1, [3], 5, 4
￪￪
此时，指针左边的元素都小于 3，右边的元素都大于 3，这一轮交换就结束了。
现在数列被 pivot 划分成了两个未排序的子序列，分别对两个子序列重复前面的步骤即可。
这就是分治的思想，数列每一轮被拆分成两部分，每一部分在下一轮又分别拆分成两部分，直到不可再分为止。
4 代码实现
递归公式：quick\_sort(left, right) = quick\_sort(left, mid-1) + quick\_sort(mid+1, right)
终止条件：left >= right
void quick_sort(int a[], int left, int right) {
if (left >= right) {
return;
}
int mid = partion(a, left, right);
quick_sort(a, left, mid - 1);
quick_sort(a, mid + 1, right);
}
// 将小于 pivot 的元素移到左边，将大于 pivot 的元素移到右边
int partion(int a[], int left, int right) {
int pivot = a[left];
while(left < right) {
while(left < right && a[right] >= pivot) {
right--;
}
a[left] = a[right];
while(left < right && a[left] <= pivot) {
left++;
}
a[right] = a[left];
}
a[left] = pivot;
return left;
}5 性能分析
（时间关系，这部分跳过）
因为划分过程涉及交换操作，如果数组中有两个相同的元素，它们的相对先后顺序可能会改变。所以，快速排序不是一个稳定排序算法。
5.1 时间复杂度
最好情况
划分后，左子序列和右子序列的长度相同，时间复杂度为 O(logn)，递推公式如下：
T(1) = C; n = 1 时，只需要常量级的执行
T(n) = 2 * T(n/2) + n; n>1递归公式的求解比较复杂，我们也可以根据递归树来求解。
最坏情况
序列本身是有序的，划分后的两个序列分别包含 0 个元素和 n-1 个元素，时间复杂度为 O(n^2)，递推公式如下：
T(1) = C; n = 1 时，只需要常量级的执行
T(n) = T(n-1) + n; n>1有点像冒泡排序，每趟排序后只能增加一个元素的有序性。
举个例子，比如 1, 2, 3, 4, 5，如果每次选择第 1 个元素作为 pivot，那么每次分区得到的两个区间都是不均等的。需要进行大约 n 次分区操作才能完成快排的整个过程，每次分区我们平均要扫描大约 n/2 个元素，从而使得时间复杂度退化成了 O(n^2)。
平均时间复杂度
假设每次分区操作都将区间分成 9:1 的两个小区间，时间复杂度为 O(nlogn)，递归公式变成如下：
T(1) = C; n = 1 时，只需要常量级的执行
T(n) = T(n/10) + T(9*n/10) + n; n>1可见，T(n) 在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端情况下才会退化到 O(n^2)，所以平均时间复杂度也是 O(nlogn)。
5.2 空间复杂度
主要是递归造成的栈空间的使用。
最好情况
递归树深度为 logn，每次递归中只使用了常数的空间，空间复杂为 O(logn)。
最坏情况
需要进行 n-1 次递归，每次递归中只使用了常数的空间，空间复杂度为 O(n)
平均空间复杂度
O(logn)
没有评论