文章目录
- 前言
- 一、快排的思想
- 二、Hoare版
- 基本思路
- 代码实现
- 三、挖坑法
- 基本思路
- 代码实现
- 四、双指针法
- 基本思想
- 代码实现
- 五、三数取中
- 六、小区间优化
- 七、三路划分
- 八、自省排序
- 总结
前言
其实下篇就单独讲个快速排序
你可能会想这是什么神通,竟然能单独开一篇来讲解,请往下看!
一、快排的思想
无论是什么版本的快排,都是遵循一个原则:以升序为例,选 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 处。实现起来也很简单
- key默认取left位置的值
- left指向区间最左边,right指向区间最后边,cur指向 left + 1 位置
- cur遇到比key小的值后跟left位置交换,换到左边,left++,cur++
- cur遇到比key大的值后跟right位置交换,换到右边,right–(注意cur并不需要自加!!!)
- cur遇到跟key相等的值后,cur++
- 直到 cur > right 结束
代码?自己去实现吧~
八、自省排序
其实这也是一个优化,哈哈想不到吧!还能继续优化~
前面说过,递归太深了,开栈帧也是一个不小的消耗,主排序仍然是快排,当我们的深度超过了logN的时候,则改用堆排序
如果求logN:
总结
接下来会出一篇快排和归排的非递归版本,我们的排序篇基本上也就结束了~