【排序】快速排序详解
✨✨欢迎大家来到Celia的博客✨✨
🎉🎉创作不易,请点赞关注,多多支持哦🎉🎉
所属专栏:排序
个人主页:Celia's blog~
一、快速排序的思想
快速排序的核心思想是:
- 选定一个key值作为基准值(一般是整个数组的第一个元素)。
- 把整个数组中比key小的元素放到key的左边,比key大的元素放到key的右边。这需要通过一次单趟排序来实现。
- 单趟排序结束后,可以认为先前选定的key值的位置已经排好序了。根据这个key值的位置,将数组分为左右两个子数组,再分别进行单趟排序(重复2过程)。直到左右数组不能再分为止。
二、快速排序的原理分析
想要实现快速排序,最重要的就是实现单趟排序,单趟排序主要有三个方法:霍尔法、挖坑法、前后针法。
2.1 霍尔法
霍尔法的思想是:
- 定义左右两个指针分别指向当前数组的首尾两边。
- 让右指针先走,从右往左找到首个比key值小的元素。
- 再让左指针走,从左往右找到首个比key值大的元素。
- 交换左右指针所指向的两个元素。
- 重复2、3步骤,直到左右指针相遇。
- 将key值所在的位置与左右指针相遇的位置的元素交换。
- 单趟排序结束,key值所在的位置左边都比key值小,右边都比key值大。
还有一个很重要的问题,为什么在单趟排序之后,两个指针相遇位置的元素值一定比key小呢?
- 如果左指针遇到右指针,由于右指针是先走的,说明右指针已经找到了比key小的元素。
- 如果右指针遇到左指针,由于上一轮的交换,比key小的元素已经换到了当前左指针的位置,左指针的位置的元素一定也比key小。
结论:如果使用霍尔法进行单趟排序,只需要让与基准值(key)所在方位相反的指针先走就可以了。
2.2 挖坑法
挖坑法的思想是:
- 定义左右两个指针,分别指向数组的首尾位置。
- 选定一个基准值key(一般是数组的第一个元素),并记录。将当前基准值位置记作“坑”。
- 右指针先走,从右往左找到比key值小的元素。
- 将右指针所在的位置的元素移动到“坑”中,当前右指针所在的位置形成新的“坑”。
- 左指针再走,从左往右找到比key值大的元素。
- 将左指针所在的位置的元素移动到“坑”中,当前左指针所在的位置形成新的“坑”。
- 当左右指针相遇时,将key值填入左右指针相遇的位置。单趟排序结束。
这个方法相比于霍尔法更好理解,也不用考虑两指针相遇时的元素是否小于key的问题。 该方法效率与霍尔法相同。
2.3 前后指针法
前后指针法的思想是:
- 选定一个基准值,用key保存起来。
- 定义prev指针指向数组首位置,定义cur指向prev的下一个位置。
- 比较cur位置的元素与key的大小关系,若cur位置元素比key大,cur++。若cur位置元素比key小,先让prev++,再交换cur和prev位置的元素。
- 当cur大于数组大小时,结束遍历,将key所在的位置的值和prev所在位置的值交换。
三、快速排序的代码实现
3.0 核心代码逻辑
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
void QSort(int* a, int left, int right)
{if (left >= right)//递归结束条件return;int begin = left, end = right;//使用三种方法的其中一种进行单趟排序int mid = Part3(a, begin, end);//记录每一次排好的元素下标QSort(a, begin, mid - 1);//递归左右子数组QSort(a, mid + 1, end);
}
递归调用会将整个数组不断地分为两个子数组,如果递归传入的left和right相等,不用进行排序,如果left大于right,不符合区间的逻辑,也不需要排序。所以递归的结束条件为 left >= right。
3.1 霍尔法
//霍尔法
int Part1(int* a, int left, int right)
{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]);return begin;
}
3.2 挖坑法
//挖坑法
int Part2(int* a, int left, int right)
{int key = a[left];int hole = left;int begin = left, end = right;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;return hole;
}
3.3 前后指针法
//前后指针法
int Part3(int* a, int left, int right)
{int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] <= a[keyi]){prev++;Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[keyi], &a[prev]);return prev;
}
四、快速排序的时间复杂度和空间复杂度分析
4.1 时间复杂度
- 快速排序最核心的步骤是对每个子数组进行遍历比较操作,所以我们用遍历的次数来近似时间复杂度。
- 快速排序对数组的分组类似于二叉树,我们可以简易的把快速排序的层数(递归深度)设为h(类比二叉树深度),递归创建的总函数栈帧次数设为N(类比二叉树节点个数)。
- 则存在近似关系:
,则共有
层,每一层的每一个节点都要遍历数组,整个一层加起来的遍历次数近似
,则总遍历次数为
。
- 则快速排序的时间复杂度为
。
4.2 空间复杂度
- 快速排序所占用的额外空间主要为递归创建的函数栈帧,则空间复杂度就是递归创建的最大栈帧数量。由于栈的空间可以重复利用,则计算递归的最大深度即可,最大深度为:
。
- 快速排序的空间复杂度为:
。
五、快速排序的优化
- 快速排序在最好情况下可以看作一个完全二叉树,时间复杂度为
。但是如果排序数组有序,那么每次把数组首位置作为基准位置的话,每次排序就相当于将数组分为 1 和 N - 1 个元素。每次排好一个元素,那么递归的深度就会大大增加。
- 遍历的总数就会变成一个等差数列,n + n - 1 + n - 2 + ... + 2 + 1,用求和公式求出结果后,最大的次方项变成了
,这不仅仅严重降低了效率,也有可能会因为递归层数太深造成栈溢出的风险。
- 为了解决这两个问题,可以使用三数取中和小区间优化来解决这些问题。
5.1 三数取中
- 三数取中的思想是,取数组首、末、中三个位置的值,记录这三个位置上大小为中间值的下标。并将这个取中的值与数组首元素交换。这样一来,以首尾值为基准值,基准值最终排好的位置会趋近于数组中间,就会将数组尽可能分为长度大致相等的两部分进行递归,以增加效率和减少递归深度。
//三数取中
int FindMid(int* a, int left, int right)
{int mid = (left + right) >> 1;if (a[left] < a[mid]){if (a[mid] < a[right])return mid;else //a[mid] >= a[right] mid最大,选left和right中最大的{if (a[left] > a[right])return left;elsereturn right;}}else //a[left] >= a[mid]{if (a[mid] > a[right])return mid;else //a[mid] <= a[right] mid最小,选left和right中最小的{if (a[right] < a[left])return right;elsereturn left;}}
}
- 加入了三数取中,快速排序的核心代码就变成了:
void QSort(int* a, int left, int right)
{if (left >= right)return;int begin = left, end = right;int middle = FindMid(a, left, right);Swap(&a[left], &a[middle]);//交换int mid = Part3(a, begin, end);QSort(a, begin, mid - 1);QSort(a, mid + 1, end);
}
5.2 小区间优化
- 小区间优化主要是针对排序数组的元素数量较少时,进行递归开辟函数栈帧开销太大(就是没有必要),不如使用其他的排序算法(快一些,但不额外开辟空间)来进行排序。一般情况下,小区间优化使用的排序算法为插入排序。
//插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}elsebreak;}a[end + 1] = tmp;}
}
- 快速排序的主要逻辑变为:
void QSort(int* a, int left, int right)
{if (left >= right)return;if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);//插入排序}else{int begin = left, end = right;int middle = FindMid(a, left, right);Swap(&a[left], &a[middle]);//交换int mid = Part3(a, begin, end);QSort(a, begin, mid - 1);QSort(a, mid + 1, end);}
}
- 这里需要注意,由于递归进行到一定深度时,数组区间元素个数较少的情况下([left, right]),排序的区间是整个数组的一小段,故插入排序传入的首地址需要传 a + left,排序元素数量需要传right - left + 1。
相关文章:
【排序】快速排序详解
✨✨欢迎大家来到Celia的博客✨✨ 🎉🎉创作不易,请点赞关注,多多支持哦🎉🎉 所属专栏:排序 个人主页:Celias blog~ 一、快速排序的思想 快速排序的核心思想是: 选定一个…...

贪心算法总结(2)
一、买卖股票的最佳时机 . - 力扣(LeetCode) class Solution { public:int maxProfit(vector<int>& prices) {int miniINT_MAX;int ret0;for(int&price:prices){//遍历的时候,我们随时去更新最小的值,然后让每一位…...

弘景光电:技术实力与创新驱动并进
在光学镜头及摄像模组产品领域,广东弘景光电科技股份有限公司(以下简称“弘景光电”)无疑是一颗耀眼的明星。自成立以来,弘景光电凭借其强大的研发实力、卓越的产品性能、精密的制造工艺以及严格的质量管理体系,在光学…...

2024年7月23日~2024年7月29日周报
目录 一、前言 二、完成情况 2.1 一种具有边缘增强特点的医学图像分割网络 2.2 融合边缘增强注意力机制和 U-Net 网络的医学图像分割 2.3 遇到的困难 三、下周计划 一、前言 上周参加了一些师兄师姐的论文讨论会议,并完成了初稿。 本周继续修改论文࿰…...
M3U8流视频数据爬虫
M3U8流视频数据爬虫 HLS技术介绍 现在大部分视频客户端都采用HTTP Live Streaming(HLS,Apple为了提高流播效率开发的技术),而不是直接播放MP4等视频文件。HLS技术的特点是将流媒体切分为若干【TS片段】(比如几秒一段…...

保护您的数字财富:模块化沙箱在源代码防泄露中的突破
在数字化浪潮中,企业面临着前所未有的数据安全挑战。源代码、商业机密、客户数据……这些宝贵的数字资产一旦泄露,后果不堪设想。SDC沙盒防泄密系统,以其卓越的技术实力和创新的解决方案,为企业提供了一个坚不可摧的安全屏障。 核…...
FFmpeg源码:avio_r8、avio_rl16、avio_rl24、avio_rl32、avio_rl64函数分析
一、引言 AVIOContext是FFmpeg(本文演示用的FFmpeg源码版本为5.0.3)中的字节流上下文结构体,用来管理输入输出数据。打开一个媒体文件的时候,需要先把数据从硬盘读到缓冲区,然后会用到AVIOContext中的如下成员&#x…...
如何使用 API 查看极狐GitLab 镜像仓库中的镜像?
GitLab 是一个全球知名的一体化 DevOps 平台,很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab :https://gitlab.cn/install?channelcontent&utm_sourcecsdn 是 GitLab 在中国的发行版,专门为中国程序员服务。可以一键式部署…...

软件-vscode-plantUML-IDEA
文章目录 vscode基础命令 实操1. vscode实现springboot项目搭建 (包括spring data jpa和sqlLite连接) PlantUMLIDEA下载及安装Eval Reset插件配置修改IDEA创建项目的默认目录IDEA配置gitIDEA翻译插件translationIDEA断点调试IDEA全局搜索快捷键不能使用代…...

ES6语法详解,面试必会,通俗易懂版
目录 Set的基本使用WeakSet 使用Set 和 WeakSet 区别内存泄漏示例:使用普通 Set 保存 DOM 节点如何避免这个内存泄漏MapWeakMap 的使用 Set的基本使用 在ES6之前,我们存储数据的结构主要有两种:数组、对象。 在ES6中新增了另外两种数据结构&a…...

CTFshow--Web--代码审计
目录 web301 web302 web303 web304 web305 web306 web307 web308 web309 web310 web301 开始一个登录框, 下意识sql尝试一下 发现 1 的时候会到一个 checklogin.php 的路径下, 但啥也没有 好吧, 这是要审计代码的 ,下载好源码, 开始审计 看了一下源码 , 应该就是sql…...

Java语言程序设计——篇十(1)
🌿🌿🌿跟随博主脚步,从这里开始→博主主页🌿🌿🌿 接口介绍 接口概述接口定义接口的实现实战演练 👅接口的继承实战演练实战演练 接口的类型常量实战演练 静态方法默认方法解决默认方…...
Qt对比MFC优势
从Qt小白到现在使用了有四年的时间,之前也搞过MFC,WinForm,基本上都是桌面的框架, 从难易程度看MFC>QT>WinForm; 运行的效率上来看MFC>QT>WinForm; 开发效率上WinForm>QT>MFC; 跨平台Qt首选; 界面的美观难易程度Qt>…...

RuntimeError: No CUDA GPUs are available
RuntimeError: No CUDA GPUs are available 目录 RuntimeError: No CUDA GPUs are available 【常见模块错误】 【解决方案】 解决步骤如下: 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页,我是博主英杰,211科…...
URL参数中携带中文?分享 1 段优质 JS 代码片段!
本内容首发于工粽号:程序员大澈,每日分享一段优质代码片段,欢迎关注和投稿! 大家好,我是大澈! 本文约 800 字,整篇阅读约需 1 分钟。 今天分享一段优质 JS 代码片段,在发送 ajax 请…...
sass的使用
一、变量 //声明一个变量 $highlight-color: #F90; .selected {border: 1px solid $highlight-color; }//编译后 .selected {border: 1px solid #F90; }二、导入 import "xxx.scss"三、混合器简单定义 通过mixin定义,通过include调用 // mixin.scss /…...

【足球走地软件】走地数据分析预测【大模型篇】走地预测软件实战分享
了解什么是走地数据? 走地数据分析,在足球赛事的上下文中,是一种针对正在进行中的比赛进行实时数据分析的方法。这种方法主要用于预测比赛中的某些结果或趋势,如总进球数、比分变化、球队表现等。 在足球走地数据分析中…...

现在有什么赛道可以干到退休?
最近,一则“90后无论男女都得65岁以后退休”的消息在多个网络平台流传,也不知道是真是假,好巧不巧今天刷热点的时候又看到一条这样的热点:现在有什么赛道可以干到退休? 点进去看了几条热评,第一条热评说的…...

c程序杂谈系列(职责链模式与if_else)
从处理器的角度来说,条件分支会导致指令流水线的中断,所以控制语句需要严格保存状态,因为处理器是很难直接进行逻辑判断的,有可能它会执行一段时间,发现出错后再返回,也有可能通过延时等手段完成控制流的正…...
前端开发技术之CSS(层叠样式表)
盒模型(Box Model) CSS盒模型描述了如何计算一个元素的总宽度和高度。 它包括以下几个部分: 1. 内容(Content):元素的实际内容,比如文本或图片。 2. 内边距(Padding)&…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...

vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...

论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...