排序算法(2)——快速排序

目录

1. 实现方式

1.1 霍尔法 ​

1.2 挖坑法

1.3 前后指针法

 2. 复杂度分析 

3. 快速排序优化

3.1 三数取中

3.2 小区间使用插入排序

3.3 非递归实现


快速排序是英国计算机科学家托尼・霍尔(C. A. R. Hoare)在 1960 年年提出的一种二叉树结构的交换排序方法。

基本思想:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

1. 实现方式

 1.1 霍尔法 

基本步骤:

  • 定义一个小兵right从数组最后一个元素开始向前遍历,如果找到比key小的值就停下来。
  • 定义一个小兵left从数组第一个元素开始向后遍历,如果找到比key大的值就停下来。
  • 交换left小兵和right小兵所在位置的值。
  • 当left小兵和right小兵相遇后,将第一个元素(key)与它们相遇位置的值交换。
  • 相遇位置的左区间和右区间继续递归上述步骤。

代码实现 

//快速排序——霍尔法
void QuickSort(int* a, int left, int right)
{if (left >= right) //数组长度为0、1 时递归停止return;int keyi = left; //第一个位置的元素作为基准值int begin = left, end = right;while (begin < end){//右边找比keyi小的值,right小兵先走while (begin < end && a[end] >= a[keyi])//注意判断条件,防止相遇没停继续找小情况发生!{--end;}//左边找比keyi大的值while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}	   Swap(&a[keyi], &a[begin]); //begin和end相遇,交换keyi = begin;	  //更新基准值的索引//分割区间 递归	QuickSort(a, left, keyi-1);//排列比基准值小的左子数组	QuickSort(a, keyi + 1, right);//排列比基准值大的右子数组
}

递归推演 

我们可能会产生这样的疑问,相遇位置的值如果比基准值大怎么办?

不会出现这种情况,因为相遇位置的值一定比基准值小,无非就以下面两种情况,可以发现相遇位置的值都比基准值要小,我们无需担心。

  1. right小兵先走,停下来,right小兵停下来位置的值一定比基准值小,left小兵没有找到比基准值大的值,就与left小兵相遇了。
  2. right小兵先走,找小,没有找到比基准值小的,就与left小兵相遇了,而left小兵停留的位置就是上一轮交换的位置,经过上一轮的交换把right小兵下比基准值小的值交换到left小兵所在位置了。

推论:如果让最右边的元素作为基准值,要让left小兵先走,可以保证相遇位置的值比基准值要大。(一边做基准值,要让另一边先走)

1.2 挖坑法

基本步骤:

  • 将第一个元素的位置作为第一个坑位,将基准值保存到变量key中。
  • 定义一个小兵right从数组最后一个元素开始向前遍历,如果找到比key小的值就停下来,将right下标对应的值赋给上一个坑位,并将right所在位置作为新的坑位。
  • 定义一个小兵left从数组第一个元素开始向后遍历,如果找到比key大的值就停下来,将left下标对应的值赋给上一个坑位,并将left所在位置作为新的坑位。
  • 当left小兵和right小兵相遇后,相遇的位置就是坑位,再将key的值放到坑位中。

代码实现 

//快速排序——挖坑法
void QuickSort(int* a, int left, int right)
{if (left >= right)return;int begin = left, end = right;int key = a[left]; //将基准值保存下来int hole = left; //建第一个坑while (begin < end){while (begin < end && a[end] >= key){end--;}a[hole] = a[end];//填坑hole = end;//变换坑的位置while (begin < end && a[begin] <= key){begin++;}a[hole] = a[begin];hole = begin;}a[hole] = key;//相遇位置的坑填基准值QuickSort(a, left, hole - 1);QuickSort(a, hole + 1, right);
}

1.3 前后指针法

//快速排序——前后指针法
void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = left;   //基准值位置int prev = left;   //定义prev指针int cur = left + 1;//定义cur指针while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)// cur指针找到小,prev指针+1,再交换,如果prev=cur就不用进行交换{Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[prev], &a[keyi]); //交换prev和keyi位置上的值	keyi = prev;QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);	
}

 2. 复杂度分析 

最好情况:每次把数组都平均分成两个部分,每一部分在下一轮又分别被拆分成两部分,这样递归下去会得到一个完全二叉树,如果排n个数字,递归的深度即二叉树的深度约logn,每次递归都需要遍历一次区间中的每一个元素,每一层的时间复杂度为O(n),总的时间复杂度为O(n*logn)

最坏情况:每一轮只确定基准元素的位置,选取的基准值刚好是这个区间的最大值或最小值。比如:对n个数排序,最小值被放在了第一个位置,经过调换元素顺序操作,最小值被放在了第一个位置,剩余n-1个数放在第2-n个位置,这样递归下去,都只能将最小的数放到第一个位置,剩下的元素没有任何变化,所以对n个数排序,需要n-1次递归调用,递归树画出来是一颗斜树,比较次数为n-1+n-2+……+1=n(n-1)/2,时间复杂度为O(n^2)。

快速排序递归调用消耗空间,每次递归都要保持一些数据:

     最好情况下空间复杂度为:O(logn)  ,递归层次为logn层,每一次都平分数组的情况

     最差情况下空间复杂度为:O( n )      ,递归树画出来是一颗斜树的情况,递归深度很深

3. 快速排序优化

3.1 三数取中

在快速排序中,基准值的选择对算法的性能有很大影响。如果选择得当,可以将数组较为均匀地划分为两部分,从而提高排序效率。反之,如果选择不当,可能会导致数组划分极不均衡,从而退化为O(n²)的时间复杂度。

固定选取第一个位置的元素作为基准值会出现问题,比如有序的情况下,会出现递归深度太深,可能会导致爆栈问题,三数取中的好处是,即使数组已经部分有序(如完全有序或逆序),也能通过选择一个相对“居中”的元素作为枢纽,来保持数组划分的平衡性。

三数取中:在待排序数组的第一个、最后一个和中间三个元素中选取中间值作为基准值,例如对数组{9,1,5,8,3,7,4,6,2},取左9、中3、右2来比较,使得midi=3。

代码实现 

//三数取中实现
int GetMidi(int* a, int left, int right) //返回三个关键字里中间值的下标
{int midi = (left + right) / 2;//算出中间位置的下标if (a[left] < a[midi]){if (a[midi] < a[right]){return midi;}else if (a[left] < a[right]) // a[left] < a[midi] && a[right] < a[midi] && a[left] < a[right]{return right;}else// a[left] < a[midi] && a[right] < a[midi] && a[left] > a[right]{return left;}}else  //a[left] > a[midi]{if (a[midi] > a[right]){return midi;}else if (a[left] > a[right]){return right;}else{return left;}}
}
快排优化——三数取中
void QuickSort(int* a, int left, int right)
{if (left >= right)return;//三数取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);//交换,将三数取中取到的值作为基准值int keyi = left;int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]){--end;}while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);keyi = begin;//更新keyi的位置QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

三数取中对于非常大的待排序序列来说不足以保证能够选出一个好的基准值,还有一个办法就是九数取中,从数组中分三次取样,每次取三个数,三个样品里个取出中数,然后再从这三个中数里面取出一个中数作为基准值。

3.2 小区间使用插入排序

由于快排递归类似于二叉树结构,越到后面几层递归次数越多,每次递归调用都会耗费一定的栈空间,如果能减少递归,将会大大提高性能。我们对其进行优化,让它不进行后面几层的递归,递归分割成小区间后就不再让它递归,使用直接插入排序对小区间进行排序,(直接插入排序是简单排序中性能最好的)。

基本思想:增加一个判断,当区间不大于某个常数时(有资料认为7比较合适,也有资料认为50更合理,实际可调整),就用直接插入排序,下面我们选10作为小区间的判断条件 。

代码实现 

//快排优化——小区间使用插入排序
void QuickSort(int* a, int left, int right)
{if (left >= right)return;//小区间优化,不再递归分割排序,减少递归次数,提高运算效率if ((right - left + 1) < 10){InsertSort(a + left, right - left + 1);//直接插入排序}else{//三数取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]){--end;}while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);keyi = begin;QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}	
}

3.3 非递归实现

递归算法存在着栈溢出的风险,可以把它改造成非递归的形式,递归算法主要是在划分子区间,如果想采用非递归的方式实现快排,只需要用一个来保存区间就可以了。一般将递归程序改成非递归首先想到的就是使用栈,因为递归本身就是一个压栈的过程。

基本步骤:

  • 入栈的时候先入右,再入左,这样出栈的时候就会先出左,再出右。
  • 取两次栈顶元素作为区间的左和右,并弹出栈顶元素。
  • 再对该区间进行单趟排序。
  • 重复上述过程直到栈为空。
//快速排序——前后指针法
int PartSort(int* a, int left, int right)
{int keyi = left;   //基准值位置int prev = left;   //定义prev指针int cur = left + 1;//定义cur指针while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)// cur指针找到小,prev指针+1,再交换,如果prev=cur就不用进行交换{Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[prev], &a[keyi]); //交换prev和keyi位置上的值	keyi = prev;return keyi;
}
//非递归实现快速排序
#include"Stack.h"
void QuickSortNonRecur(int* a, int left, int right)
{ST st; //定义一个栈STInit(&st); //初始化栈STPush(&st, right); //入栈STPush(&st, left);  //入栈while (!STEmpty(&st)) //栈为空时结束循环{int begin = STTop(&st); //取栈顶元素STPop(&st); //出栈int end = STTop(&st);STPop(&st);//单趟排序int keyi = PartSort(a, begin, end);//[begin,keyi-1] keyi[keyi+1,end]if (keyi + 1 < end) //如果区间只有一个值或者没有值就不入栈了{STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/490663.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【python】最新版抖音js逆向拿到数据,非常详细教程(附完整代码)

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全…

apollo2.0.0本地调试运行

一、下载源码 https://github.com/apolloconfig/apollo/tree/v2.0.0 二、本地环境 jdk 1.8 mysql 5.7 maven 3.6.3 三、IDEA运行源码 IDEA直接Open打开项目即可 需要依次启动configservice、adminservice、portal三个服务 基于apollo-assembly模块的ApolloApplication…

STP(生成树协议)

STP的基本概念 概述 STP是一个用于局域网中消除环路的协议。运行该协议的设备通过彼此交互信息而发现网络中的环路&#xff0c;并对某些接口进行阻塞以消除环路。STP在网络中运行后会持续监控网络的状态&#xff0c;当网络出现拓扑变更时&#xff0c;STP能够感知并且进行自动…

3D 生成重建039-Edify 3D:Nvidia的3D生成大模型

3D 生成重建039-Edify 3D:Nvidia的3D生成大模型 文章目录 0 论文工作1 论文方法2 实验结果 0 论文工作 文档介绍了Edify 3D&#xff0c;一种为高质量的3D资产生成而设计的高级解决方案。首先在多个视点上合成了所描述对象的RGB和表面法线图像正在使用扩散模型。然后使用多视图…

Maven学习(依赖版本维护、依赖传递、解决Maven依赖冲突的3种方式)

目录 一、Maven的依赖版本维护。 &#xff08;1&#xff09;为什么需要依赖版本维护&#xff1f; &#xff08;2&#xff09;依赖统一管理的具体操作步骤。 第一步。在pom.xml文件中使用标签定义jar包的版本。 第二步。在的对应jar的中使用"${}"引入上面定义好的版本…

CV(4)--边缘提取和相机模型

前言 仅记录学习过程&#xff0c;有问题欢迎讨论 边缘提取&#xff08;涉及语义分割&#xff09;&#xff1a; 图象的边缘是指图象局部区域亮度变化显著的部分,也有正负之分&#xff0c;暗到亮为正 求边缘的幅度&#xff1a;sobel&#xff0c;Canny算子 图像分高频分量和低…

鸿蒙项目云捐助第三讲鸿蒙App应用的启动页实现

鸿蒙项目云捐助第三讲鸿蒙App应用的启动页实现 对于移动端的应用&#xff0c;一般启动app的时候&#xff0c;首先显示启动页&#xff0c;启动页中显示出该应用一些介绍内容&#xff0c;通过这个介绍内容可以了解这个应用具体处理的内容。 进入启动后&#xff0c;通过滑动启动…

flink sink kafka的事务提交现象猜想

现象 查看flink源码时 sink kafka有事务提交机制&#xff0c;查看源码发现是使用两阶段提交策略&#xff0c;而事务提交是checkpoint完成后才执行&#xff0c;那么如果checkpoint设置间隔时间比较长时&#xff0c;事务未提交之前&#xff0c;后端应该消费不到数据&#xff0c…

Mumu模拟器12开启ADB调试方法

在使用安卓模拟器进行开发或调试时&#xff0c;ADB&#xff08;Android Debug Bridge&#xff09;是一项不可或缺的工具。大多数模拟器默认开启了ADB调试功能&#xff0c;但在安装最新版的 Mumu模拟器12 时&#xff0c;可能会遇到 adb devices 无法识别设备的问题。 问题描述 …

C/C++中的宏定义

在C程序中&#xff0c;可以用宏代码提高执行效率。宏代码本身不是函数&#xff0c;但使用起来像函数。预处理器用复制宏代码的方式代替函数调用&#xff0c;省去了参数压栈、生成汇编语言的CALL调用、返回参数、执行return等过程&#xff0c;从而提高了速度&#xff0c;避免函数…

《拉依达的嵌入式\驱动面试宝典》—C/CPP基础篇(二)

《拉依达的嵌入式\驱动面试宝典》—C/CPP基础篇(二) 你好,我是拉依达。 感谢所有阅读关注我的同学支持,目前博客累计阅读 27w,关注1.5w人。其中博客《最全Linux驱动开发全流程详细解析(持续更新)-CSDN博客》已经是 Linux驱动 相关内容搜索的推荐首位,感谢大家支持。 《拉…

批量导出工作簿中高清图片-Excel易用宝

我同事在工作簿中做了三个图表&#xff0c;现在需要将工作簿中的图标导出保存为高清图片&#xff0c;通过右键另存为保存的图片并非高清图片&#xff0c;其实要把Excel工作簿中的图表或图片对象导出为高清图片也很简单。 单击Excel易用宝 Plus&#xff0c;导出高清图片。 在导出…

测试工程师八股文05|功能测试、业务测试

一、基础概念 1、软件测试分类 1️⃣按照软件产生的阶段划分 单元测试&#xff1a;针对程序源代码进行测试【开发自测】集成测试&#xff1a;针对模块之间功能交互进行测试系统测试&#xff1a;对整个系统&#xff08;功能、非功能&#xff09;进行全面测试验收测试&#xff…

“AI全网络深度学习系统:开启智能时代的新篇章

嘿&#xff0c;大家好&#xff01;今天咱们来聊聊一个特别前沿的话题——AI全网络深度学习系统。这名字听起来是不是有点像科幻电影里的玩意儿&#xff1f;但其实&#xff0c;它已经悄悄地走进了我们的生活&#xff0c;而且正在改变我们的工作方式。 首先&#xff0c;咱们得搞清…

【Linux|计算机网络】HTTPS工作原理与安全机制详解

目录 1、HTTPS是什么&#xff1f; 2、概念准备 2.1.什么是加密、解密、密钥 2.2.为什么要加密 2.3.常见的加密方式 1.对称加密 2.非对称加密 2.4.数据摘要 && 数据指纹 2.5. 数字签名 3.HTTPS 的工作过程探究 方案 1 - 只使用对称加密 方案 2 - 只使用非对…

shell脚本自动发布Java应用

单体项目或定制化小应用&#xff0c;频繁发布会有些麻烦&#xff0c;用脚本实现git提交完代码自动发布&#xff0c;并完成jar包备份 1.前提条件&#xff1a;linux安装了JDK、Maven、Git 安装参考链接&#xff1a; jdk安装 https://blog.csdn.net/weixin_44904239/article/de…

搭建自己的wiki知识库(重新整理)

写在前面&#xff1a; 之前写过一篇&#xff0c;因为这次修改的内容比较多&#xff0c;所以不想在原基础上修改了&#xff0c;还是重新整理一篇吧。搭建wiki知识库&#xff0c;可以使用在线文档&#xff0c;如xx笔记、xx文档、xx博客、git仓库&#xff08;如&#xff1a;GitHu…

【Python网络爬虫笔记】10- os库存储爬取数据

os库的作用 操作系统交互&#xff1a;os库提供了一种使用Python与操作系统进行交互的方式。使用os库来创建用于存储爬取数据的文件夹&#xff0c;或者获取当前工作目录的路径&#xff0c;以便将爬取的数据存储在合适的位置。环境变量操作&#xff1a;可以读取和设置环境变量。在…

MySQL:表的内置函数

目录 一. 日期函数 二. 字符串函数 三. 数学函数​编辑 四. 其他函数 博客开始为各位读者介绍一个投递简历的平台&#xff1a;万码优才 专属于程序员的投递平台&#xff0c;大家快去试试吧&#xff01;&#xff01;&#xff01; 此篇博客讲解MySQL中关于表的内置函数。…

亚马逊云科技2024 re:Invent大会亮点:Nova大模型与AI基础设施全面升级

引言 作为云计算领域的年度盛会,亚马逊云科技(AWS)的re:Invent大会一直是业界瞩目的焦点。2024年的大会不负众望,推出了一系列重磅产品和服务,尤其是在人工智能和大模型方面的创新令人印象深刻。本文将为您深入解析此次大会的主要亮点,探讨AWS在AI时代的最新布局及其对行业的潜…