做网站与平台的区别,wordpress主题 dux1.2原版,为什么说网络营销是一种整合营销,SharePoint做网站好吗文章目录 前言一、快排的思想二、Hoare版基本思路代码实现 三、挖坑法基本思路代码实现 四、双指针法基本思想代码实现 五、三数取中六、小区间优化七、三路划分八、自省排序总结 前言 其实下篇就单独讲个快速排序 你可能会想这是什么神通#xff0c;竟然能单独开一篇来讲… 文章目录 前言一、快排的思想二、Hoare版基本思路代码实现 三、挖坑法基本思路代码实现 四、双指针法基本思想代码实现 五、三数取中六、小区间优化七、三路划分八、自省排序总结 前言 其实下篇就单独讲个快速排序 你可能会想这是什么神通竟然能单独开一篇来讲解请往下看 一、快排的思想 无论是什么版本的快排都是遵循一个原则以升序为例选 key划分选取一个 key 使 key 左边的值小于等于 key 右边的值大于 key 然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止这是快排的核心思想由此一共有以下几种变式
二、Hoare版
基本思路 选取最左边的值为 key比较时右边先走因选的是左边所以右边会先走向左走当右边在走的过程中遇到小于等于 key 的值时停下右边走完后换左边走向右走当遇到大于 key 的值时停止此时交换左右两处的值当左遇到右时必定相遇因为一次走一步终止循环执行最后一步交换此时左右与 key 值此时就完成了需求右边值 key 左边值 完成这一单次排序后将排序这个大问题转成小问题指定 begin 与 end 此时 [beginkey - 1]、key、[key 1end]将其中的两块区域传入函数继续执行递归当所有数据都排序完成后快排就结束了 如果 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);//思路选出keykey 的右边小于keykey 的左边大于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位置交换换到左边leftcurcur遇到比key大的值后跟right位置交换换到右边right–注意cur并不需要自加cur遇到跟key相等的值后cur直到 cur right 结束 代码自己去实现吧~ 八、自省排序 其实这也是一个优化哈哈想不到吧还能继续优化~ 前面说过递归太深了开栈帧也是一个不小的消耗主排序仍然是快排当我们的深度超过了logN的时候则改用堆排序 如果求logN 总结 接下来会出一篇快排和归排的非递归版本我们的排序篇基本上也就结束了~
