您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

看完这个,你觉得你真的懂快速排序吗?

时间:2019-11-27 16:33:30  来源:  作者:

看似青铜实则王者

很多人提起快排和二分都觉得很容易的样子,但是让现场Code很多就翻车了,就算可以写出个递归版本的代码,但是对其中的复杂度分析、边界条件的考虑、非递归改造、代码优化等就无从下手,填鸭背诵基本上分分钟就被面试官摆平了。

看完这个,你觉得你真的懂快速排序吗?

 

那年初识快速排序

快速排序Quicksort又称划分交换排序partition-exchange sort,简称快排,一种排序算法。最早由东尼·霍尔(C. A. R. Hoare)教授在1960年左右提出,在平均状况下,排序n个项目要O(nlogn)次比较。
在最坏状况下则需要O(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他算法更快,因为它的内部循环可以在大部分的架构上很有效率地达成。

快速排序的核心思想

在计算机科学中,分治法(Divide&Conquer)是建基于多项分支递归的一种很重要的算法范式,快速排序是分治思想在排序问题上的典型应用。

所谓分治思想D&C就是把一个较大规模的问题拆分为若干小规模且相似的问题。再对小规模问题进行求解,最终合并所有小问题的解,从而形成原来大规模问题的解。

字面上的解释是"分而治之",这个技巧是很多高效算法的基础,如排序算法(归并排序、快速排序)、傅立叶变换(快速傅立叶变换)。

分治法中最重要的部分是循环递归的过程,每一层递归有三个具体步骤:

  • 分解:将原问题分解为若干个规模较小,相对独立,与原问题形式相同的子问题。
  • 解决:若子问题规模较小且易于解决时,则直接解。否则,递归地解决各子问题。
  • 合并:将各子问题的解合并为原问题的解。

快速排序的基本过程

快速排序使用分治法来把一个序列分为小于基准值和大于基准值的两个子序列。

递归地排序两个子序列,直至最小的子序列长度为0或者1,整个递归过程结束,详细步骤为:

  • 挑选基准值: 从数列中挑出一个元素称为基准pivot,选取基准值有数种具体方法,此选取方法对排序的时间性能有决定性影响。
  • 基准值分割: 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面,与基准值相等的数可以到任何一边,在这个分割结束之后,对基准值的排序就已经完成。
  • 递归子序列: 递归地将小于基准值元素的子序列和大于基准值元素的子序列排序,步骤同上两步骤,递归终止条件是序列大小是0或1,因为此时该数列显然已经有序。

快速排序的递归实现

  • 版本一 C实现
#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]);
 }
}
  • 版本二 C++实现
#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,图中之所以放到一起是为了直观表达终止条件。

  • 版本二C++版本动画演示:
看完这个,你觉得你真的懂快速排序吗?

 

分析一下:

个人觉得这个版本虽然同样使用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;
}


Tags:排序   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  Tags: 排序  点击:(6)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15  Tags: 排序  点击:(16)  评论:(0)  加入收藏
试想一下,用 Excel 管理项目的时候,会有很严格的日期安排,而且项目中的各细目经常是并行作业的,这就意味着日期不一定是排序的 。 那么事项太多如何更好管理,而不至于遗忘关键节...【详细内容】
2021-11-16  Tags: 排序  点击:(23)  评论:(0)  加入收藏
说明Web应用程序,MySQL数据库,数据库中有三张表:health_patient(病人表)、health_patient_account(病人账户表)、 health_patient_medical_history(病例表),视图需求是,页面分页展示病...【详细内容】
2021-11-05  Tags: 排序  点击:(32)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  Tags: 排序  点击:(40)  评论:(0)  加入收藏
排序算法有很多,像冒泡排序,选择排序,插入排序,希尔排序,快速排序等等。今天这篇文章呢,我们来聊一聊简单的冒泡排序(Bubble Sort)。 想必大家都知道鱼吐泡泡的现象,气泡从鱼的嘴巴里...【详细内容】
2021-09-07  Tags: 排序  点击:(57)  评论:(0)  加入收藏
1. 插入排序步骤:1.从第一个元素开始,该元素可以认为已经被排序2.取下一个元素tem,从已排序的元素序列从后往前扫描3.如果该元素大于tem,则将该元素移到下一位4.重复步骤3,直到找...【详细内容】
2021-08-19  Tags: 排序  点击:(100)  评论:(0)  加入收藏
前言前面我们已经一起学习了冒泡排序(Python 实现经典算法之冒泡排序),这篇文章,大家与好奇心就一起再来看看选择排序吧。简介选择排序是一种简单直观的排序算法,无论什么数据进...【详细内容】
2021-07-23  Tags: 排序  点击:(122)  评论:(0)  加入收藏
01故事起源幼儿园放学,小朋友们集合,需要先从低到高排队,应该怎么排呢? 02开始行动小K身高180,是班里最高的,自然得往后排啦。小K先和身后的小B比较,然后和小B交换。 小K接着和身后...【详细内容】
2021-06-08  Tags: 排序  点击:(176)  评论:(0)  加入收藏
Hello,大家好,今天跟跟大家分享下如何在Excel中实现自动排序的效果。这个也是一个粉丝提问的问题,我们先来看下效果,当我们更改数据,后面的总分就会自动地发生变化,并且表格会按照...【详细内容】
2021-05-24  Tags: 排序  点击:(181)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条