您好,登录后才能下订单哦!
请求超时!
请点击 重新获取二维码很多人提起快排和二分都觉得很容易的样子,但是让现场Code很多就翻车了,就算可以写出个递归版本的代码,但是对其中的复杂度分析、边界条件的考虑、非递归改造、代码优化等就无从下手,填鸭背诵基本上分分钟就被面试官摆平了。
快速排序Quicksort又称划分交换排序partition-exchange sort,简称快排,一种排序算法。最早由东尼·霍尔(C. A. R. Hoare)教授在1960年左右提出,在平均状况下,排序n个项目要O(nlogn)次比较。
在最坏状况下则需要O(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他算法更快,因为它的内部循环可以在大部分的架构上很有效率地达成。
在计算机科学中,分治法(Divide&Conquer)是建基于多项分支递归的一种很重要的算法范式,快速排序是分治思想在排序问题上的典型应用。
所谓分治思想D&C就是把一个较大规模的问题拆分为若干小规模且相似的问题。再对小规模问题进行求解,最终合并所有小问题的解,从而形成原来大规模问题的解。
字面上的解释是"分而治之",这个技巧是很多高效算法的基础,如排序算法(归并排序、快速排序)、傅立叶变换(快速傅立叶变换)。
分治法中最重要的部分是循环递归的过程,每一层递归有三个具体步骤:
快速排序使用分治法来把一个序列分为小于基准值和大于基准值的两个子序列。
递归地排序两个子序列,直至最小的子序列长度为0或者1,整个递归过程结束,详细步骤为:
#include<stdio.h>
int a[9]={5,1,9,6,7,11,3,8,4};
void exchange(int *p,int *q){
int temp=*p;
*p=*q;
*q=temp;
}
int quicksort(int left,int right){
if(left>=right){
return 0;
}
int i,j,temp;
temp=a[left];
i=left;
j=right;
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]);
}
quicksort(i+1,right);
quicksort(left,i-1);
}
int main(){
quicksort(0,8);
for(int i=0;i<=8;i++){
printf("%d ",a[i]);
}
}
#include<iostream>
using namespace std;
template <typename T>
void quick_sort_recursive(T arr[], int start, int end) {
if (start >= end)
return;
T mid = arr[end];
int left = start, right = end - 1;
//整个范围内搜寻比枢纽值小或大的元素,然后左侧元素与右侧元素交换
while (left < right) {
//试图在左侧找到一个比枢纽元更大的元素
while (arr[left] < mid && left < right)
left++;
//试图在右侧找到一个比枢纽元更小的元素
while (arr[right] >= mid && left < right)
right--;
//交换元素
std::swap(arr[left], arr[right]);
}
//这一步很关键
if (arr[left] >= arr[end])
std::swap(arr[left], arr[end]);
else
left++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
//模板化
template <typename T>
void quick_sort(T arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
int main()
{
int a[9]={5,1,9,6,7,11,3,8,4};
int len = sizeof(a)/sizeof(int);
quick_sort(a,len-1);
for(int i=0;i<len-1;i++)
cout<<a[i]<<endl;
}
两个版本均可正确运行,但代码有一点差异:
过程说起来比较抽象,稳住别慌!灵魂画手大白会画图来演示这两个过程。
以第一次
递归循环为例:
步骤1: 选择第一个元素为基准值pivot=a[left]=5,right指针指向尾部元素,此时先由right自右向左扫描直至遇到<5的元素,恰好right起步元素4<5,因此需要将4与5互换位置;
步骤2: 4与5互换位置之后,轮到left指针从左向右扫描,注意一下left的起步指针指向了由步骤1交换而来的4,新元素4不满足停止条件,因此left由绿色虚箭头4位置游走到元素9的位置,此时left找到9>5,因此将此时left和right指向的元素互换,也就是元素5和元素9互换位置;
步骤3: 互换之后right指针继续向左扫描,从蓝色虚箭头9位置游走到3的位置,此时right发现3<5,因此将此时left和right指向的元素互换,也就是元素3和元素5互换位置;
步骤4: 互换之后left指针继续向右扫描,从绿色虚箭头3位置游走到6的位置,此时left发现6>5,因此将此时left和right指向的元素互换,也就是元素6和元素5互换位置;
步骤5: 互换之后right指针继续向左扫描,从蓝色虚箭头6位置一直游走到与left指针相遇,此时二者均停留在了pivot=5的新位置上,且左右两边分成了两个相对于pivot值的子序列;
循环结束:至此出现了以5为基准值的左右子序列,接下来就是对两个子序列实施同样的递归步骤。
以第二次和第三次
左子序列递归循环为例:
步骤1-1:选择第一个元素为基准值pivot=a[left]=4,right指针指向尾部元素,此时先由right指针向左扫描,恰好起步元素3<4,因此将3和4互换;
步骤1-2:互换之后left指针从元素3开始向右扫描,一直游走到与right指针相遇,此时本次循环停止,特别注意这种情况下可以看到基准值4只有左子序列,无右子序列,这种情况是一种退化,就像冒泡排序每次循环都将基准值放置到最后,因此效率将退化为冒泡的O(n^2);
步骤1-3:选择第一个元素为基准值pivot=a[left]=3,right指针指向尾部元素,此时先由right指针向左扫描,恰好起步元素1<3,因此将1和3互换;
步骤1-4:互换之后left指针从1开始向右扫描直到与right指针相遇,此时注意到pivot=3无右子序列且左子序列len=1,达到了递归循环的终止条件,此时可以认为由第一次循环产生的左子序列已经全部有序。
循环结束:至此左子序列已经排序完成,接下来对右子序列实施同样的递归步骤,就不再演示了,聪明的你一定get到了。
特别注意:
以上过程中left和right指针在某个元素相遇,这种情况在代码中是不会出现的,因为外层限制了i!=j,图中之所以放到一起是为了直观表达终止条件。
分析一下:
个人觉得这个版本虽然同样使用D&C思想但是更加简洁,从动画可以看到选择pivot=a[end],然后左右指针分别从index=0和index=end-1向中间靠拢。
过程中扫描目标值并左右交换,再继续向中间靠拢,直到相遇,此时再根据a[left]和a[right]以及pivot的值来进行合理置换,最终实现基于pivot的左右子序列形式。
脑补场景:
上述过程让我觉得很像统帅命令左右两路军队从两翼会和,并且在会和过程中消灭敌人有生力量(认为是交换元素),直到两路大军会师。
此时再将统帅王座摆到正确的位置,此过程中没有统帅王座的反复变换,只有最终会师的位置,以王座位中心形成了左翼子序列和右翼子序列。
再重复相同的过程,直至完成大一统。
脑补不过瘾 于是凑图一张:
吃瓜时间:
印象中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;
}
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
聚圣源简爱读书笔记摘抄赏析马怎么起名字大全姓安男孩怎么起名结实的反义词宝宝起名字女有创意的生鲜超市起名按生辰八字起名大全网李佳怎么起名梦回唐朝演员表五行八字查询起名大全海森堡门店起名网免费取名大全叛逆的鲁鲁修第二季动漫猪年的宝宝起名宜用的字2018年给男孩起名羿字起名好听的发财起名足球俱乐部起名鲁滨逊漂流记好词好句斗罗大陆完整免费版漫画琴行起什么名字好用大水法美味的陷阱贾姓猪宝宝起名2012年春晚节目单英文 商标注册 起名起名诗词 男孩名字大全猪宝宝取名起名大全宜用哪些字爱国的小故事社交app起名字淀粉肠小王子日销售额涨超10倍罗斯否认插足凯特王妃婚姻让美丽中国“从细节出发”清明节放假3天调休1天男孩疑遭霸凌 家长讨说法被踢出群国产伟哥去年销售近13亿网友建议重庆地铁不准乘客携带菜筐雅江山火三名扑火人员牺牲系谣言代拍被何赛飞拿着魔杖追着打月嫂回应掌掴婴儿是在赶虫子山西高速一大巴发生事故 已致13死高中生被打伤下体休学 邯郸通报李梦为奥运任务婉拒WNBA邀请19岁小伙救下5人后溺亡 多方发声王树国3次鞠躬告别西交大师生单亲妈妈陷入热恋 14岁儿子报警315晚会后胖东来又人满为患了倪萍分享减重40斤方法王楚钦登顶三项第一今日春分两大学生合买彩票中奖一人不认账张家界的山上“长”满了韩国人?周杰伦一审败诉网易房客欠租失踪 房东直发愁男子持台球杆殴打2名女店员被抓男子被猫抓伤后确诊“猫抓病”“重生之我在北大当嫡校长”槽头肉企业被曝光前生意红火男孩8年未见母亲被告知被遗忘恒大被罚41.75亿到底怎么缴网友洛杉矶偶遇贾玲杨倩无缘巴黎奥运张立群任西安交通大学校长黑马情侣提车了西双版纳热带植物园回应蜉蝣大爆发妈妈回应孩子在校撞护栏坠楼考生莫言也上北大硕士复试名单了韩国首次吊销离岗医生执照奥巴马现身唐宁街 黑色着装引猜测沈阳一轿车冲入人行道致3死2伤阿根廷将发行1万与2万面值的纸币外国人感慨凌晨的中国很安全男子被流浪猫绊倒 投喂者赔24万手机成瘾是影响睡眠质量重要因素春分“立蛋”成功率更高?胖东来员工每周单休无小长假“开封王婆”爆火:促成四五十对专家建议不必谈骨泥色变浙江一高校内汽车冲撞行人 多人受伤许家印被限制高消费