数据结构初阶：快速排序
@八大排序
4.2 快速排序
基本思想
代码实现
复杂度分析
4 交换排序
4.2 快速排序
快速排序是对冒泡排序的一种改进，在思想层面上具有巨大进步，是Hoare提出的一种类似于二叉树结构的一种排序方法，距今大约有60年之久。快速排序的实现有递归和非递归两种方式，递归中又有三种递归版本，而这三种递归的思想大差不差。
快速排序和冒泡排序一样属于交换排序，通过交换两个元素来修正序列的顺序。接下来就是研究如何交换这两个元素。
基本思想
快速排序的递归思想类似于二叉树结构的遍历。
基本思想为：任取待排数组中的某个元素作为关键字key，通过一趟排序将该数组分割成两个独立的子数组，左数组的所有元素均小于该关键字，右数组的所有元素均大于该关键字。这就是一趟排序的流程，再对所得两个子数组分别重复上述过程，直至整个数组有序。
代码实现
快速排序的实现必须先理解清楚单趟排序，之后每趟排序都是最初的单趟排序的缩小版。
单趟排序版本1. Horae 版本
一般选最左边或最右边的元素作为关键字key。
单趟排序完成后必须使数组中比key小的元素在数组的左边，比key大的在数组的右边，最后关键字key也到了最终位置。
可以理解成单趟排序的目的就是将关键字key放到最终的正确位置，类似于冒泡排序的将最大值放到尾处的最终位置。都是一趟排序排好一个数，顺便整理了一下数组以便之后的下一趟排序。
单趟排序的具体步骤从上述对结果的描述也能看出来，定义左右下标：
-
右边找比 key小的数，左边找比key大的数（升序），二者找到后交换。
为使数组满足左小右大的升序，自然要右找小左找大，再进行交换。如果排的是降序，那就是右找小左找大。
-
左右下标相遇后停止循环，交换 key和当前下标所在位置的值。
// 递归版本1. Horae 版本
int Partition1(int* a, int left, int right) {
assert(a);
int keyi = left;
while (left < right) {
//右找小
while (left < right && a[right] >= a[keyi]) {
--right;
}
//左找大
while (left < right && a[left] <= a[keyi]) {
++left;
}
//左右交换
Swap(&a[left], &a[right]);
}
//交换key
Swap(&a[keyi], &a[left]);
return left;
}
在找左找右的代码中，有两个必须注意的问题，
-
移动下标的过程中必须加上 left<right的条件，否则会导致下标越界， -
判断条件 a[left]<=a[keyi]要加上等于的时候，以适应数组元素全相等的情况以免造成死循环。
左右先走问题分析
在单趟排序过程中有一个问题：当左右下标相遇后的值要与最左边
key交换，使得左区间的元素都比key要小，但有没有可能左右下标相遇位置的元素比key大，导致这个比key大的数被换到了左边呢？当然不会出现这样的问题，因为在左右指针移动时，有这样的规定：
-
选最左边的值作 key时，右边的下标r先走，保证左右相遇时的值比key要小。 -
选最右边的值作 key时，左边的下标l先走，保证左右相遇时的值比key要大。
我们以选最左边作key，右边先走为例解释一下，在左右下标移动的过程中，无非有两种情况：
-
特殊情况：数组中无比key小的数，右下标一次性就到了最左边与左下标相遇。这样key与key进行交换。 -
一般情况：数组中间有比key小的数，右下标经历几番波折才与左下标相遇。在相遇前的最后一步时可能有两种情况： -
要么最后右直接到左的位置，左虽找大但该左下标的位置的值已在上一轮交换中和比key小的数发生交换 ， -
要么最后右到了左的后一个位置，此位置的值自然比key小，接着左下标开始移动正好与右相遇 。
这两种子情况都是左右下标相遇位置的值比key要小，所以只要按照左key右先右key左先的规定，就不会出错。
看到这里，就可以先看下面的递归版本中把排序主函数用上，来实现一个完整的排序。
单趟排序版本2. 挖坑法
挖坑法是针对单趟排序 Hoare 版本的简化变形。
一样的左边作 key 右边先走，右边作 key 左边先走，同样以选最左边作key为例。
-
将最左边的值用临时变量 key 保存起来，形成一个坑位。 -
右下标先走，找比 key 小的值，找到放到左边的坑位中，自身又形成了一个坑位。 -
左下标再走，找比 key 大的值，找到放到右边的坑位中，自身又形成了一个坑位。 -
依次循环往复，左右下标相遇后停止循环，再将 key中的值放到当前下标所在位置的坑位中，就完成了单趟排序。
//2. 挖坑法
int Partition2(int* a, int left, int right) {
assert(a);
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
//定义key
int key = a[left];
//定义坑位
int pivot = left;
while (left < right) {
while (left < right && a[right] >= key) {
--right;
}
//右下标的值放到左边的坑位中
a[pivot] = a[right];
pivot = right;
//左下标的值放到右边的坑位中
while (left < right && a[left] <= key) {
++left;
}
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
return pivot;
}
挖坑法更简单流行，所以一般选择题所遇到的排序问题，默认都考察挖坑法。
单趟排序版本3. 前后指针法
前后指针版比较难以理解，但是是逻辑最简单的一种方法。涉及到双指针的问题，把两个指针放到一起比较难以理解，一般可以拆开看，思考每个指针的作用，再放到一起看就明了了。
-
第一个要注意的点仍是选 key问题。但没有左右下标也就没有先走后走的问题。
-
左边作 key， cur指针起始位置在第2个元素，prev指针指向cur前1个位置， 排序有效区间即是第2个元素到尾元素。 -
右边作 key， cur指针起始位置在第1个元素，prev指针指向cur前1个位置， 排序有效区间即是首元素到倒数第2个元素。
-
cur指针向后遍历数组，并找比 key 小的元素（升序）。cur找到满足条件的元素后，prev指针向后移动一位，再交换 cur 和 prev 指向元素的值。 -
cur遍历完数组时，将 key 与 prev 交换。prev 的值比 key 小，左边作 key 时可直接交换， 右边作 key 时 prev 应向后移动一位，将大的值交换到右边。
由上图可以看出，cur的任务就是遍历数组找比 key 小的值，prev的任务是紧跟比 key 大的值，以便之后二者进行交换。整个过程看起来就是，cur 把比 key 小的数往左放，prev 把比 key 大的数向右推。
prev 保证了 prev 左边及当前位置的值全部比 key 小，且 prev 紧跟比 key 大的序列。
//左边作key
int Partition(int* a, int left, int right) {
assert(a);
//三数取中
int midi = GetMidIndex(a, left, right);
int keyi = left;
int prev = left, cur = prev + 1;
//有效区间
while (cur <= right) {
//cur找小
if (a[cur] < a[keyi] && ++prev != cur) {
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
return prev;
}
//右边作key
int Partition(int* a, int left, int right) {
assert(a);
//三数取中
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
int keyi = right;
int cur = left, prev = cur - 1;
//有效区间
while (cur < right) {
//cur找小
if (a[cur] < a[keyi] && ++prev != cur) {
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[keyi], &a[++prev]);//把大的换到右边
return prev;
}
前后指针版本可能较难理解，但实现却是最简单的，一般面试的时候都可以写这种。
递归版本
单趟排序之后，分出了左右子区间，倘若左右子区间都是有序的，那么整个排序就完成了。
至于左右子区间怎么使其有序，则是再将左右子区间分别视为一个数组，继续对其执行单趟排序。不断分割直至所得“数组”仅有一个元素时默认排序完成。
这便是整体排序的递归结构，类似于二叉树的前序遍历。
void QuickSort(int* a, int left, int right) {
assert(a);
//区间只有一个值或区间不存在
if (left >= right) {
return;
}
//单趟排序
int keyi = Partition1(a, left, right);
//递归左区间
QuickSort(a, left, keyi - 1);
//递归右区间
QuickSort(a, keyi + 1, right);
}
从上述代码看出，每次排序都将数组分成这样的三部分 和 key 和 。key所在位置已经排好序，再对前后两个子区间进行分治，递归调用即可。
非递归版本
复杂的递归难以用一般的循环实现，快排二叉树形的递归称为双路递归。双路递归可以用栈的结构模拟，递归时栈帧中存储区间左右下标，所以可以借助栈模拟栈帧存储左右下标。
将排序区间的左右下标保存到栈中，按照先入后出的特点，先排序左区间先入右区间再入左区间，让单趟排序函数读取栈里的左右下标来排序数组。
void QuickSortNonR(int* a, int left, int right) {
assert(a);
Stack st;//建立栈
StackInit(&st);
//先入数组长度
StackPush(&st, left);
StackPush(&st, right);
while (!StackEmpty(&st)) {
//读取左右下标
int end = StackTop(&st);
StackPop(&st);
int begin = StackTop(&st);
StackPop(&st);
//进行单趟排序
int keyi = Partition1(a, begin, end);
//[begin,keyi-1] keyi [keyi+1,end]
//排序结果入栈
if (keyi + 1 < end) {//临界条件
StackPush(&st, keyi + 1);
StackPush(&st, end);
}
if (begin < keyi - 1) {
StackPush(&st, begin);
StackPush(&st, keyi - 1);
}
}
StackDestroy(&st);
}
非递归就是把原本存入递归栈帧中的区间左右下标存入栈结构中，每次循环即相当于一次递归。递归是将结果存到栈帧中而非递归是用堆区开辟的空间，堆比栈大得多，必然不会溢出。
递归和非递归只需要掌握一种即可。
复杂度分析
快速排序的时间复杂度和key的选择有很大的关系。如果每次我们都选到整个数组的中位数的话，是最佳情况如图所示：
这样根据单趟排序的遍历思想来看，整体复杂度就是长度乘二叉树高度即 。
快排的缺陷
-
当每次选到的 key 都是整个数组中的最小值或者最大值，那么每趟排序就只能解决一个数且其他元素不变，这样复杂度就变成和冒泡排序一样 ，可用三数取中优化。 -
递归结构越到后面递归的次数越多，而越到后面排序的数组越小，这样递归的性价比太低，可用小区间优化解决。 -
当数组序列为完全相同的元素时，快排无论如何也无法优化，只能像第一种情况一样，复杂度为 ，应提前避免。
快排的优化
1. 三数取中
正如前面所言，快排复杂度非常依赖key的选择，最优情况是每次都选到或接近中位数的元素递归后呈现二叉树的结构。最差情况则是数组顺序有序或接近有序时仍每次选择最左或最右边的最值作为key，如图所示：
这种情况下快排类似于冒泡排序，时间复杂度为 。此时若数据量大递归调用会建立栈帧太多容易栈溢出，递归的缺陷有：
-
相比循环程序，性能略差。 -
递归程度太深，会导致栈溢出。
早期编译器优化不够，现在二者性能不会差多少。栈区8M空间已经够调用几万层的，溢出了一般都是程序错误。
那如何解决快排面对数组有序的选key问题呢？可以随机选key，但是这样等于是将自己的命运交给随机，这样效果也不是特别好，还有一种解决方案叫三数取中。
三数取中：取出最左，最右，中间三者的中间数作key。也就是选出三者中不是最大也不是最小的值作key，借此保证快排的效率。
void GetMidIndex(int* a, int left, int right) {
int midi = left + ((right - left) >> 1);
//取中逻辑
if (a[left] < a[right]) { /** left < right **/
if (a[midi] < a[left]) //mid < left < right
return left;
else if (a[midi] < a[right]) //left < mid < right
return midi;
else //left < right < mid
return right;
}
else { /** left > right **/
if (a[midi] > a[left]) //mid > left > right
return left;
else if (a[midi] > a[right]) //left > mid > right
return midi;
else //left > right > mid
return right;
}
}
void Partition(int* a, int left, int right) {
//三数取中
int midi = GetMidIndex(a, left, right);
Swap(&a[left], &a[midi]);
//...
}
三数取中按照一定的逻辑去写代码。当 中分为 在 左边， 在 右边， 在二者中间的三种情况，当 $left<right$ 时同理。< p>
三数取中尽量保证了选到的key不大不小尽量是中间值，以尽量保证递归结构是一棵完美的二叉树，尽量避免了数组有序时那种最坏情况。
2. 小区间优化
如图所示，当递归深到一定层次的时候，递归的区间就愈发的小，但此时递归的次数却愈发的多了起来。
以上图为例，假设有1000个数，则递归深度为10，最后一行接近 次调用，倒数第二行接近 次调用，底层的递归次数占了总次数的绝大部分，而最后两层递归却只为了排好几个数。三层递归调用了7次，只排好了5个数，代价太大。
为了避免这样的情况，减少递归次数，可以使用小区间优化。小区间优化就是当递归区间小到一定程度时（例如仅有10元素），利用其他的排序方式而非快排进行排序，以减少复杂度。
//递归版本
void QuickSort(int* a, int left, int right) {
//临界条件
if (left >= right) {
return;
}
//小区间优化
if (right - left < 10) {
//调用插入排序
InsertSort(a + left, right - left + 1);
}
int keyi = Partition3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
每趟快排过后都会将数组变得更加接近有序，而插入排序对接近有序的数组排序效果最好，所以小区间优化选择用插入排序。调用插入排序时，注意数组区间的起始位置和区间长度。