江苏龙网

  1. 主页 > 生活百科 > >

看完这个，你觉得你真的懂快速排序吗？( 三 )

排序


脑补场景:
上述过程让我觉得很像统帅命令左右两路军队从两翼会和 ， 并且在会和过程中消灭敌人有生力量(认为是交换元素) ， 直到两路大军会师 。
此时再将统帅王座摆到正确的位置 ， 此过程中没有统帅王座的反复变换 ， 只有最终会师的位置 ， 以王座位中心形成了左翼子序列和右翼子序列 。
再重复相同的过程 ， 直至完成大一统 。
脑补不过瘾 于是凑图一张:

看完这个，你觉得你真的懂快速排序吗？

文章插图
 
快速排序的多种版本吃瓜时间：
印象中2017年初换工作的时候去CBD一家公司面试手写快排 ， 我就使用C++模板化的版本二实现的 ， 但是面试官质疑说这不是快排 ， 争辩之下让我们彼此都觉得对方很Low ， 于是很快就把我送出门SayGoodBye了_ 。
我想表达的意思是 ， 虽然快排的递归版本是基于D&C实现的 ， 但是由于pivot值的选择不同、交换方式不同等诸多因素 ， 造成了多种版本的递归代码 。
并且内层while循环里面判断>=还是>(即是否等于的问题) ， 外层循环判断本序列循环终止条件等写法都会不同 ， 因此在写快排时切忌死记硬背 ， 要不然边界条件判断不清楚很容易就死循环了 。
看下上述我贴的两个版本的代码核心部分：
//版本一写法while(i!=j){ while(i<j&&a[j]>=temp){ j--; } exchange(&a[i],&a[j]);while(i<j&&a[i]<=temp){ i++;} exchange(&a[i],&a[j]);}//版本二写法while (left < right) { while (arr[left] < mid && left < right) left++; while (arr[right] >= mid && left < right) right--; std::swap(arr[left], arr[right]);}覆盖or交换:
代码中首先将pivot的值引入局部变量保存下来 ， 这样就认为A[L]这个位置是个坑 ， 可以被其他元素覆盖 ， 最终再将pivot的值填到最后的坑里 。
这种做法也没有问题 ， 因为你只要画图就可以看到 ， 每次坑的位置是有相同元素的位置 ， 也就是被备份了的元素 。
个人感觉 与其叫坑不如叫备份 ， 但是如果你代码使用的是基于指针或者引用的swap ， 那么就没有坑的概念了 。
这就是覆盖和交换的区别 ， 本文的例子都是swap实现的 ， 因此没有坑位被最后覆盖一次的过程 。
快速排序的迭代实现所谓迭代实现就是非递归实现一般使用循环来实现 ， 我们都知道递归的实现主要是借助系统内的栈来实现的 。
如果调用层级过深需要保存的临时结果和关系会非常多 ， 进而造成StackOverflow栈溢出 。
Stack一般是系统分配空间有限内存连续速度很快 ， 每个系统架构默认的栈大小不一样 ， 笔者在x86-centos7.x版本使用ulimit -s查看是8192Byte 。
避免栈溢出的一种办法是使用循环 ， 以下为笔者验证的使用STL的stack来实现的循环版本 ， 代码如下：
#include <stack>#include <iostream>using namespace std;template<typename T>void qsort(T lst[], int length) { std::stack<std::pair<int, int> > mystack; //将数组的首尾下标存储 相当于第一轮循环 mystack.push(make_pair(0, length - 1)); while (!mystack.empty()) { //使用栈顶元素而后弹出 std::pair<int,int> top = mystack.top(); mystack.pop(); //获取当前需要处理的子序列的左右下标 int i = top.first; int j = top.second; //选取基准值 T pivot = lst[i]; //使用覆盖填坑法 而不是交换哦 while (i < j) { while (i < j and lst[j] >= pivot) j--; lst[i] = lst[j]; while (i < j and lst[i] <= pivot) i++; lst[j] = lst[i]; } //注意这个基准值回填过程 lst[i] = pivot; //向下一个子序列进发 if (i > top.first) mystack.push(make_pair(top.first, i - 1)); if (j < top.second) mystack.push(make_pair(j + 1, top.second)); }}int main(){ int a[9]={5,1,9,6,7,11,3,8,4}; int len = sizeof(a)/sizeof(int); qsort(a,len); for(int i=0;i<len-1;i++) cout<<a[i]<<endl;}
【看完这个，你觉得你真的懂快速排序吗？】


推荐阅读


上一篇：双节将至 茶市升温 强调性价比成礼茶主旋律

下一篇：我国历史上关于茶叶记载的书籍