DS几大常见排序讲解和实现(下)(15)

---

前言

  其实下篇就单独讲个快速排序
  你可能会想这是什么神通，竟然能单独开一篇来讲解，请往下看！

---

一、快排的思想

  无论是什么版本的快排，都是遵循一个原则：以升序为例，选 key划分，选取一个 key ，使 key 左边的值小于等于 key ，右边的值大于 key ，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止，这是快排的核心思想，由此一共有以下几种变式

二、Hoare版

基本思路

  选取最左边的值为 key，比较时右边先走，因选的是左边，所以右边会先走（向左走），当右边在走的过程中遇到小于等于 key 的值时停下，右边走完后，换左边走（向右走），当遇到大于 key 的值时停止，此时交换左右两处的值，当左遇到右时（必定相遇，因为一次走一步），终止循环，执行最后一步，交换此时左（右）与 key 值，此时就完成了需求：右边值 <= key < 左边值

  完成这一单次排序后，将排序这个大问题转成小问题，指定 begin 与 end ，此时 [begin，key - 1]、key、[key + 1，end]，将其中的两块区域传入函数，继续执行递归，当所有数据都排序完成后，快排就结束了

  如果 key 选在最左边，那么右边先走；如果 key 选在最右边，左边先走。这样做的目的是保证最后一次交换时（左右重叠时与 key 值的交换）key 左边的数小于等于 key，原因如下：

动图如下：

递归展开图如下：

代码实现

int Partition(int* arr, int left, int right)
{int begin = left, end = right;int key = arr[left];while (begin < end){// 找小// 不加等于，若左右指针指向同一个值，会陷入死循环while (begin < end && arr[end] >= key){ // 等于是必要的，不然可能会陷入死循环end--;}// 找大while (begin < end && arr[begin] <= key){begin++;}Swap(&arr[begin], &arr[end]);}Swap(&arr[begin], &arr[left]);return begin;
}void QuickSort(int* arr, int left, int right){if (left >= right){return ;}int KeyIndex = Partition(arr, left, right);QuickSort(arr, left, KeyIndex - 1);QuickSort(arr, KeyIndex + 1, right);
}

三、挖坑法

基本思路

  挖坑法核心思想与霍尔版一致，不过挖坑法为了便于理解，引入了坑位这个概念，简单来说就是先在 key 处挖坑，然后右边先走（假设 key 在最左边），找到小于等于 key 的值，就将此值放入到坑中，并在这里形成新坑；然后是左边走，同样的，找到值 -> 填入坑 -> 挖新坑，如此重复，直到左右相遇，此时的相遇点必然是一个未填充的坑，当然这个坑就是给 key 值准备的

动图如下：

代码实现

void QuickSort(int* arr, int left, int right)
{if (left >= right){return ;}int index = GetMidIndex(arr, left, right); // 三数取中，我们后面会讲Swap(&arr[index], &arr[left]);int begin = left, end = right;int pivot = begin;int key = arr[begin];while (begin < end){// 右边找小，放到左边while (begin < end && arr[end] >= key){end--;}// 小的放到左边的坑里，自己形成新的坑位arr[pivot] = arr[end];pivot = end;// 左边找大while (begin < end && arr[begin] <= key){begin++;}// 大的放到左边的坑里，自己形成新的坑位arr[pivot] = arr[begin];pivot = begin;}pivot = begin;arr[pivot] = key;QuickSort(arr, left, pivot - 1);QuickSort(arr, pivot + 1, right);
}

四、双指针法

基本思想

  双指针的实现方式与上面两种截然不同，但最核心的思想仍是依赖 key，一样的先找 key，然后定义两个指针 prev 与 cur ，prev 的起始位置为 key ，而 cur 则是位于 prev 的下一位，判断 cur 处的值是否小于等于 key 值，如果是，则先 ++prev 后再交换 prev 与 cur 处的值，如此循环，直到 cur 移动至数据尾，最后一次交换为 key 与 prev 间的交换，交换完成后，就达到了快排的要求

这个方法也是我最喜欢的解法，很漂亮

代码实现

int Partition(int* arr, int left, int right)
{int key = left;int prev = left, cur = left + 1;while (cur <= right){if (arr[cur] < arr[key] && ++prev != cur){ // 加个判断，防止无意义交换Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[prev], &arr[key]);return prev;
}void QuickSort(int* arr, int left, int right)
{if (left >= right){return ;}int index = Partition(arr, left, right);QuickSort(arr, left, index - 1);QuickSort(arr, index + 1, right);
}

五、三数取中

  前面说过，接近有序或逆序的数据，对于快排是不太友好的，因为未优化前的快排选 key 始终是最右或最左，即有可能是最大或最小数，就像二分取中一样，快排只有尽可能取到中间数，才能发挥它的最大实力

  因此我们可以借助一个函数：三数取中，分别取数据头、尾、中间进行比较，选取其中位于中间的数，再将其交换至数据首位（待会 key 取右边），经过这一优化后，快排的提升是非常明显的

int GetMidIndex(const int* arr, int left, int right)
{int mid = (left + right) >> 1; // 二进制向右移动一位if (arr[left] < arr[mid]){ // arr[left] < arr[mid]if (arr[mid] < arr[right]){return mid;}else if (arr[left] > arr[right]){return left;}else {return right;}}else { // arr[left] > arr[mid]if (arr[mid] > arr[right]){return mid;}else if (arr[left] < arr[right]){return left;}else {return right;}}
}

六、小区间优化

  对于递归来说，越是接近小区间，所耗费时间就越长，越不利于排序，此时坚持使用快排是个不明智的选择，为此我们可以借助其他排序，弥补快排在小区间排序中的不足，就像二叉递归树到最后几层节点最多，其实这很浪费栈帧，很不好

  这里借助的是直接插入排序，直接插入排序是个很不错的排序，稳定、速度也是中规中矩，小区间的定义取决于我们，我这里是将小于20的区间定义为小区间

void QuickSort(int* pa, int begin, int end)
{assert(pa);//思路：选出key，key 的右边小于key，key 的左边大于keyif (begin >= end)return;if ((end - begin + 1) < 20)InsertSort(pa + begin, (end - begin + 1));	//这就是小区间优化QuickSort(pa, begin, keyi - 1);QuickSort(pa, keyi + 1, end);
}

七、三路划分

力扣912.排序数组

这题蛮逆天的，官方给的快排竟然过不了，应该是题出得早，但是后面偷偷加了测试样例，原先的快排速度不足，就过不了了，我们看下报错样例，方法是官方给的快慢指针快排法

我们发现这个测试样例有一个特点，就是同一值的数据特别多，而我们的快排一趟排序只能选出一个数，对于别的一样的值却没有什么特别的处理方式，可以放左边，也可以放在右边

这个时候，有一个优化方式，就是三路划分，顾名思义，每趟排序将原数组分成三组，左边是小于key的，中间是等于key的，右边是大于key的，如图所示：

三路划分的核心在于控制中路的左右边界，这里需要借助三个变量：left、right、cur,显然 left 位于 begin 处，right 位于 end 处，cur 位于 begin + 1 处。实现起来也很简单

1. key默认取left位置的值
2. left指向区间最左边，right指向区间最后边，cur指向 left + 1 位置
3. cur遇到比key小的值后跟left位置交换，换到左边，left++，cur++
4. cur遇到比key大的值后跟right位置交换，换到右边，right–（注意cur并不需要自加！！！）
5. cur遇到跟key相等的值后，cur++
6. 直到 cur > right 结束

代码？自己去实现吧~

八、自省排序

  其实这也是一个优化，哈哈想不到吧！还能继续优化~
  前面说过，递归太深了，开栈帧也是一个不小的消耗，主排序仍然是快排，当我们的深度超过了logN的时候，则改用堆排序

如果求logN：

---

总结

  接下来会出一篇快排和归排的非递归版本，我们的排序篇基本上也就结束了~