C++算法恢复训练之快速排序

快速排序（Quick Sort）是一种基于分治思想的排序算法，它通过将待排序数组分成两个子数组，其中一个子数组的所有元素都比另一个子数组的元素小，然后对这两个子数组递归地进行排序，最终将整个数组排序。快速排序是一种原地排序算法，其时间复杂度为$O(nlogn)$。

下面是使用 C++ 实现的 经典 快速排序算法：

#include <vector>
#include <iostream>
using namespace std;int partitionSimple(vector<int>& array, int left, int right)
{if (left >= right){return -1;}// Use the value of index `right` as the pivotconst int pivot = array[right];int lessBound = left - 1;for (int i = left; i < right; i++){// If the current element is not more than then pivot value,// then swap it with the less part's next value, and make the less part add 1if (array[i] <= pivot){swap(array[i], array[++lessBound]);}}// At last, swap the pivot with the next element of less partswap(array[lessBound + 1], array[right]);return lessBound + 1;
}void quickSortSimple(vector<int>& array, int left, int right)
{if (left >= right){return;}const int pivotIndex = partitionSimple(array, left, right);quickSortSimple(array, left, pivotIndex - 1);quickSortSimple(array, pivotIndex + 1, right);
}void quickSort(vector<int>& array)
{quickSortSimple(array, 0, array.size() - 1);
}

经典快速排序的实现过程可以分为两个步骤：

• 分割子问题：选取一个元素作为基准值（pivot），将待排序数组分成两个子数组，一个子数组中的元素都小于等于基准值，另一个子数组中的元素都大于等于基准值。
• 合并解决方案：对两个子数组分别进行快速排序（递归），最后将两个已排序的子数组合并成一个有序数组。

递归的部分其实比较好理解和实现，那么现在可以将问题简化为：给定一个数组，和一个基准值，如何将小于等于基准值的元素放在数组左边，将大于基准值的元素放在数组右边？

我的实现思路是利用一个小于等于pivot值的边界的索引这样一个概念变量，对应代码中的lessBound，它对应的元素及其左边部分都小于等于pivot值。在随后的数组遍历过程中，如果遍历的元素满足这样的条件，则将该元素与lessbound的后一位对调，然后将lessbound的范围扩大一位。核心思路类似快慢指针：即lessbound扮演的是慢指针，i扮演的是快指针。

最后，数组已经被分成了两个子数组，其中一个子数组中的元素都小于等于基准值，另一个子数组中的元素都大于基准值。然后分别对这两个子数组进行递归。

快速排序的时间复杂度为 $O(nlogn)$，其中 $n$ 是待排序数组的长度。快速排序每次将待排序数组分成两个子数组，其中一个子数组中的元素都小于等于基准值，另一个子数组中的元素都大于等于基准值。

由于快速排序每次都将待排序数组分成两个子数组，因此递归树的高度为 $logn$。每个节点所处理的子问题的规模最大为 $n$，因此快速排序的时间复杂度为 $O(nlogn)$。

需要注意的是，在最坏情况下，快速排序的时间复杂度为 O(n2)O(n^2)O(n2)，此时待排序数组已经有序或者接近有序，且每次选取的基准值都是数组中的最小或最大元素。为了避免最坏情况的发生，可以采用以下优化措施：

• 随机选取基准值。
• 三数取中法（Median-of-three partitioning）：从子数组的左端、右端和中间位置分别选取一个元素，选择它们的中间值作为基准值。

除此以外，从算法本身出发，经典快排是利用某个值作为基准值，其算法实质在于一个周期内确定这个pivot的下标索引。从这点考虑，可以考虑在这个周期内将所有与pivot相等的值的位置都敲定，在递归时就不考虑这一批数。

C++相应的实现：

vector<int> partitionOptimized(vector<int>& array, int left, int right)
{if (left >= right){return {-1, -1};}int pivot = array[right];int lessBound = left - 1, moreBound = right;int i = left;while (i < moreBound){if (array[i] == pivot){i++;}else if (array[i] < pivot){swap(array[++lessBound], array[i++]);}else{// array[i] > pivotswap(array[--moreBound], array[i]);}}swap(array[right], array[moreBound++]);return {lessBound, moreBound};
}void quickSortOptimized(vector<int>& array, int left, int right)
{if (left >= right){return;}vector<int> bounds = partitionOptimized(array, left, right);quickSortOptimized(array, left, bounds[0]);quickSortOptimized(array, bounds[1], right);
}void quickSort(vector<int>& array)
{quickSortOptimized(array, 0, array.size() - 1);
}

新的算法的最显著的不同之处在于，partition的返回值是一个数组，保存了小于pivot的边界和大于pivot的边界，他们也是新一轮递归的依据。在计算这两个边界时（partition内），需要将一个数组拆分为：小于pivot的部分，等于pivot的部分，以及大于pivot的部分。此时主要是利用三个指针，分别指向小于pivot的部分的边界，大于pivot的部分的边界，以及当前遍历元素。如果当前元素小于pivot，则与之前的思路类似，将当前元素与小于边界的下一位调换，小于的边界扩大一位，继续下一个元素遍历；如果当前元素等于pivot，继续下一个元素遍历，其他不变；如果当前元素大于pivot，则需要将当前元素与大于边界的下一位进行调换，大于的边界减小一位，注意此时仍然需要调查被调换元素的大小，即不继续一个元素的遍历。

当然，虽说是优化，但是这个思路也仅仅是在数组中有重复元素时会比经典快排稍微快一些，本质上算法复杂度并没有发生改变，也没有改变快排依赖数组状况的问题。

利用随机取基准值的方法确实可以令这个问题得到改善，但是取随机数本身也是需要一定的指令，其产生的消耗也是一个需要考虑和权衡的问题。