【数据结构】快速排序（三种实现方式）

目录

一、基本思想

二、动图演示（hoare版）

三、思路分析（图文）

四、代码实现（hoare版）

五、易错提醒

六、相遇场景分析

6.1 ❥ 相遇位置一定比key要小的原因

6.2 ❥ 右边为key，左边先走

6.3 ❥ 一边为key，另一边先走的原因

七、时间复杂度分析

八、快排的优化

8.1 ❥ key值的选取

8.1.1 随机数选key

8.1.2 三数取中

8.2 ❥ 小区间优化

九、挖坑法

9.1 ❥ 动图演示

9.2 ❥ 思路详解

9.3 ❥ 代码实现

十、前后指针法

10.1 ❥ 动图演示

10.2 ❥ 思路详解

10.3 ❥ 代码实现

一、基本思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。

其基本思想为：

  1. 任取待排序元素序列中的某元素作为基准值，按照该排序将待排序集合分割成两个子序列
  2. 左子序列中所有元素均小于基准值，右子序列中的所有元素均大于基准值
  3. 然后分别对左右两部分重复上述操作，直到将无序序列排列成有序序列。

二、动图演示（hoare版）

三、思路分析（图文）

以下以升序为例：

简言之，就是先进行单趟的排序，单趟排完之后，key已经放在它合适的位置上，分割出了一个左区间和右区间，然后进行递归排序，当左右区间都有序时，那么就整体有序。

四、代码实现（hoare版）

void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}//hoare版
void QuickSort(int* a, int left, int right) //参数为数组下标
{//递归结束条件 if (left >= right){return;}int keyi = left;int begin = left;int 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[begin], &a[keyi]);keyi = begin;	//将begin下标位置赋给keyi//分割出左右区间// [left, keyi-1] keyi [keyi+1, right]//整体排序 递归QuickSort(a, left, keyi - 1);QuickSort(a, keyi+1,right);}

五、易错提醒

我们看如下一段代码：

void QuickSort(int* a, int left, int right) 
{if (left >= right){return;}int keyi = left;int begin = left;int end = right;while (begin < end){while (a[end] >= a[keyi]){end--;}while (a[begin] <= a[keyi]){begin++;}swap(&a[begin], &a[end]);}swap(&a[begin], &a[keyi]);keyi = begin;QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

上述代码是有问题存在的

通过调试可知，第二个while遇到相遇要停止，这里while少了相遇停止条件，否则可能会一直死循环下去

为何要创建begin和end？

通过上述思路分析易知，区间的每次分割，left都需要指向原始序列第一个元素的位置，right指向原始序列最后一个元素的位置，所以这里专门定义一个begin和end 而不是用left和right去++ --，就是为了便于分割区间。

六、相遇场景分析

6.1 ❥ 相遇位置一定比key要小的原因

我们发现，每次L与R相遇时与key进行交换时，L的值都小于key，这是为什么呢？

这里对他们相遇的场景进行分析：

相遇时无非两种场景，要么R遇见L，要么L遇见R

L遇R：

R先走，找小，停下来。

R停下条件是：遇见比key小的值，R停的位置一定比key小，L没有找到大的，遇见R停下

所以说：L遇R，它们相遇的位置就是R的位置

R遇L：

R先走，找小，没有找到比key小的，直接跟L相遇了。

L停留的位置是上一轮交换的位置

上一轮交换，把比key小的值，换到了L的位置

6.2 ❥ 右边为key，左边先走

我们发现，上面相遇场景都是左边做key，如果右边做key，让左边先走呢？

右边做key时：相遇位置一定比key要大

如下图所示：

结论：

  • 左边做key，右边先走，可以保证相遇位置一定比key小
  • 右边做key，左边先走，可以保证相遇位置一定比key大

6.3 ❥ 一边为key，另一边先走的原因

有人肯定会疑惑，为什么要一边做key，另一边先走，不可以做key的一边先走吗？

可以验证一下：

上图是让key在左边，且左边先走，在8相遇，然后与key==5进行交换

交换完后，5换到了数组下标为5的位置，并没有换到他所对应的正确位置，且左区间的8比5大。

我们知道，快排是当一趟排完之后，左区间都比key小，右区间都比key大，且key刚好在正确位置上，这样才可以继续分左右区间进行递归排序。

因此，不可以做key的一边先走

结论：一边做key，只能让另一边先走

七、时间复杂度分析

在比较理想的情况下，快排的递归结构接近完全二叉树，所以层数为logn层，每一层排序次数近似为n，（即单趟的时间复杂度为n）

故时间复杂度为：O(nlogn)

但是在有序场景下使用快排会性能会下降，时间复杂度为O(N^2)

如下图所示：

  • 当key在左边时，右边R找小就会找不到，然后一直往左走，直到在key处相遇，
  • 然后自己跟自己交换，结束一趟的排序。分割出左右区间。
  • 此处没有左区间，只存在右区间
  • 就这样依次类推......
  • 那么总共执行的次数就会是一个等差数列
  • 即：时间复杂度为O(N^2)
  • 它的效率就会大幅度降低。

八、快排的优化

  • 经过时间复杂度的分析，发现当前的快排算法还是存在一些缺陷的，那就是在有序场景下使用快排会性能会下降，此外，还有可能导致栈溢出。
  • 为什么在有序场景下会发生栈溢出？
  • 因为每走一层就是一个递归，这里递归的深度太深会有栈溢出的风险。
  • 所以快排在此还是有较为明显的缺陷的，面对这些缺陷，我们在此应怎么解决呢？
  • 我们知道，时间复杂度为O(nlogn)的前提是每次区间的划分都是二分，也就是每次选择交换的key，都是接近中间位置的值，哪怕不那么接近二分，但整体深度是logn就可以
  • 所以key值的选取非常关键，如果固定的选择最左边（下标为0）的值，就有可能选到最小的值，然后出现效率退化栈溢出的风险
  • 那如何选key才能避免有序的情况下效率退化呢？
  • 下面提供了两种选取key值的方式

8.1 ❥ key值的选取

8.1.1 随机数选key

  • 如果想要输出给定范围[a,b]内的随机数，需要使用rand()%(b-a+1)+a
  • 缺陷：可能刚刚好选到最大或者最小值

代码如下：

void rand_key(int* a, int left, int right)
{int randi = left + (rand() % (right - left + 1));swap(&a[left], &a[randi]);
}

8.1.2 三数取中

所谓三数取中，就是从最左边，最右边，最中间三个位置，选择中间的值（不大不小的值）作为key（赋值给key）

代码如下：

int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[left] > a[right]){if (a[left] < a[midi]) // r<l<m{return left;}else if(a[midi]<a[right])	//m<r<l{return right;}else	//r<m<l{return midi;}}else{if (a[right]<a[midi])	//l<r<m{return right;}else if (a[midi]<a[left])	//m<l<r{return left;}else   //l<m<r{return midi;}}	
}

注意

这里是选出的中间值还应跟最左边的值进行交换，还应该让最左边的值作为key

8.2 ❥ 小区间优化

为何要有小区间优化：

当将一组待排序列进行快排，递归到只剩下5个值时，我们还要进行选key，分割左右区间等操作让5个值有序，此刻使用递归调用花费代价太大（最后一层递归调用就要占整体递归调用的50%），这就引入了小区间优化的方式。

小区间优化目的：

当待排区间长度小于等于某个阈值时，不再递归分割排序，减少递归调用的深度和对栈空间的使用，避免过度分割导致的效率下降，可以在处理小规模数据时获得更好的性能，从而提高整体排序算法的效率。

思路分析：

  1. 这里选择直接插入排序，首先希尔排序适合数据量较大时使用，这里不适合使用。
  2. 直接插入排序在同是O(N^2)的情况下，它的速度要更快
  3. 因为通常情况下，它是达不到O(N^2)，只有在完全有序的情况下，才能达到O(N^2)
  4. 所以同级情况下，它要比其它排序更快一点，它的实践意义也在于此。
  5. 当然，引入小区间优化会使得效率低下，增加了算法的复杂度。

代码如下：

//直接插入算法
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--;}else{break;}}a[end + 1] = tmp;}
}//交换算法
void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}//三数取中
int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[left] > a[right]){if (a[left] < a[midi]) {return left;}else if (a[midi] < a[right])	{return right;}else	{return midi;}}else{if (a[right] < a[midi])	{return right;}else if (a[midi] < a[left])	{return left;}else {return midi;}}
}//hoare版
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;int 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[begin], &a[keyi]);keyi = begin;QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}

九、挖坑法

这里的挖坑法是以单趟排序的思路优化出的挖坑法。

该方法没有效率的提升（因为单趟排序效率无提升空间，至少都得遍历一遍）

但理解起来更简单，因为它们相遇的位置是坑，所以不用分析左边做key，右边先走的问题，也不用分析相遇位置比key小的原因

9.1 ❥ 动图演示

9.2 ❥ 思路详解

  1. 将序列的第一个元素作为基准值，存放在临时变量key中，此时的第一个坑位形成
  2. L指向第一个元素，R指向最后一个元素
  3. R开始向前移动，R--，找比key小的值，找到后，将R指向的值填入L的坑位，此时R形成一个坑位
  4. 然后L开始向后移动，L++，找比key大的值，找到后，将L指向的值填入R的坑位，此时L形成一个坑位
  5. R和L交错移动，形成新的坑位，直到R与L相遇
  6. 此时将key值填入L和R共同所指向的坑位
  7. 单趟排序完成
  8. 然后分割左右区间进行递归排序
  9. 最后排成一个有序序列

9.3 ❥ 代码实现

//挖坑法
void QuickSort1(int*a,int left,int right)
{//递归结束条件 if (left >= right){return;}int key = a[left];int begin = left;int end = right;//单趟排序while (begin < end){while (begin<end&&a[end] >= key){end--;}a[begin] = a[end];	//甩给右区间坑while (begin<end&&a[begin] <= key){begin++;}a[end] = a[begin];	//甩给左区间坑}a[begin] = key;	//将key填入相遇的坑//进行递归排序QuickSort1(a, left, begin - 1);QuickSort1(a, begin + 1, right);}

十、前后指针法

前后指针法只是单趟逻辑改变，整体递归思路并没有改变。

该方法没有效率的提升。

10.1 ❥ 动图演示

10.2 ❥ 思路详解

  • 将key指向序列的第一个元素，设为基准值
  • prev指向key的位置，cur指向prev的下一个位置
  • 对cur进行判断：

如果cur>=key，则cur++ 

如果cur<key，prev++，交换cur和prev所指向的值，然后cur++

  • 再对cur进行判断，直到cur++到序列的最后一个元素的下一个位置，交换prev与key的值
  • 此时单趟排序完成
  • 然后分割左右区间进行递归排序
  • 最后排成一个有序序列

10.3 ❥ 代码实现

void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}//前后指针法
void QuickSort2(int* a, int left, int right)
{if (left >= right){return;}//单趟排序int keyi = left;int prev = left;int cur = left + 1;while (cur<=right){if (a[cur] < a[keyi]) //cur的值比keyi的值小{prev++;if (prev != cur)	//判断prev与cur是否指向同一位置{swap(&a[prev], &a[cur]);}}cur++;}swap(&a[prev], &a[keyi]);QuickSort2(a, left, prev - 1);QuickSort2(a, prev + 1, right);}

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

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

相关文章

dd小程序如何监听props中对象的值

dd小程序如何监听props中对象的值

组件内代码 Component({mixins: [],data: {infoData:{}},props: {rowData:Object},didMount() {console.log(this.props.rowData,this.props.rowDatathis.props.rowData)this.setData({infoData:this.props.rowData})},didUpdate() {console.log(this.props.rowData)},didUnmo…
阅读更多...
落实“双碳”行动，深兰科技推动分子能源技术在AI硬件产品领域的应用及产业化进程

落实“双碳”行动，深兰科技推动分子能源技术在AI硬件产品领域的应用及产业化进程

10月21日&#xff0c;上海气候周分子能研究中心(筹)成立仪式在上海环境能源交易所举行。仪式上&#xff0c;深兰科技践行“双碳”目标&#xff0c;与上海东八能源技术有限公司签署分子能源AI应用产业化合作协议。 根据协议&#xff0c;国际分子能量发电开拓者、上海气候周分子能…
阅读更多...
论当前的云计算

论当前的云计算

随着技术的不断进步和数字化转型的加速&#xff0c;云计算已经成为当今信息技术领域的重要支柱。本文将探讨当前云计算的发展现状、市场趋势、技术革新以及面临的挑战与机遇。 云计算的发展现状 云计算&#xff0c;作为一种通过网络提供可伸缩的、按需分配的计算资源服务模式&a…
阅读更多...
TMGM平台可靠么？交易是否安全？

TMGM平台可靠么？交易是否安全？

在选择外汇交易平台时&#xff0c;安全性与可靠性是投资者最关注的要素之一。作为全球知名的外汇及差价合约交易平台&#xff0c;TMGM&#xff08;tmgm-pt.com&#xff09;的安全性与可靠性可以从多个方面进行评估&#xff0c;包括监管环境、资金安全、客户服务、交易技术与服务…
阅读更多...
[项目][boost搜索引擎#4] cpp-httplib使用 | log.hpp | 前端 | 测试及总结

[项目][boost搜索引擎#4] cpp-httplib使用 | log.hpp | 前端 | 测试及总结

目录 编写http_server模块 1. 引入cpp-httplib到项目中 2. cpp-httplib的使用介绍 3. 正式编写http_server 九、添加日志到项目中 十、编写前端模块 十一. 详解传 gitee 十二、项目总结 项目的扩展 写在前面 项目 gitee 已经上传啦 &#xff08;还是决定将学校和个人…
阅读更多...
LabVIEW共享变量通信故障

LabVIEW共享变量通信故障

问题概述&#xff1a; 在LabVIEW项目中&#xff0c;使用IO服务器创建共享变量&#xff0c;并通过LabVIEW作为从站进行数据通信。通讯在最初运行时正常&#xff0c;但在经过一段时间或几个小时后&#xff0c;VI前面板出现错误输出&#xff0c;导致数据传输失败。虽然“分布式系统…
阅读更多...
【国潮来袭】华为原生鸿蒙 HarmonyOS NEXT（5.0）正式发布：鸿蒙诞生以来最大升级，碰一碰、小艺圈选重磅上线

【国潮来袭】华为原生鸿蒙 HarmonyOS NEXT（5.0）正式发布：鸿蒙诞生以来最大升级，碰一碰、小艺圈选重磅上线

在昨日晚间的原生鸿蒙之夜暨华为全场景新品发布会上&#xff0c;华为原生鸿蒙 HarmonyOS NEXT&#xff08;5.0&#xff09;正式发布。 华为官方透露&#xff0c;截至目前&#xff0c;鸿蒙操作系统在中国市场份额占据 Top2 的领先地位&#xff0c;拥有超过 1.1 亿 的代码行和 6…
阅读更多...
[LeetCode] 230. 二叉搜索树中第K小的元素

[LeetCode] 230. 二叉搜索树中第K小的元素

题目描述&#xff1a; 给定一个二叉搜索树的根节点 root &#xff0c;和一个整数 k &#xff0c;请你设计一个算法查找其中第 k 小的元素&#xff08;从 1 开始计数&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,1,4,null,2], k 1 输出&#xff1a;1示例 2&am…
阅读更多...
欧盟 RED 网络安全法规 EN 18031

欧盟 RED 网络安全法规 EN 18031

目录 1. &#x1f4c2; EN 18031 1.1 背景 1.2 专业术语 1.3 覆盖产品范围 1.4 EN 18031标准主要评估内容&#xff1a; 1.5 EN 18031标准主要评估项目&#xff1a; 1.6 EN 18031 与 ETSI EN 303 645 的主要差异 1.7 RED 网络安全法规解读研讨会 2. &#x1f531; EN 1…
阅读更多...
Docker：namespace环境隔离 CGroup资源控制

Docker：namespace环境隔离 CGroup资源控制

Docker&#xff1a;namespace环境隔离 & CGroup资源控制 Docker虚拟机容器 namespace相关命令ddmkfsdfmountunshare 进程隔离文件隔离 CGroup相关命令pidstatstresscgroup控制 内存控制CPU控制 Docker 在开发中&#xff0c;经常会遇到环境问题&#xff0c;比如程序依赖某个…
阅读更多...
VirtualBox虚拟机桥接模式固定ip详解

VirtualBox虚拟机桥接模式固定ip详解

VirtualBox虚拟机桥接模式固定ip详解 VirtualBox 桥接设置Ubuntu 24.04使用固定IP问题记录 VirtualBox 桥接设置 为什么设置桥接模式&#xff1f;桥接模式可以实现物理机和虚拟机互相通信&#xff0c;虚拟机也可以访问互联网&#xff08;推荐万金油&#xff09;&#xff0c;物…
阅读更多...
AudioSegment 提高音频音量 - python 实现

AudioSegment 提高音频音量 - python 实现

一些采集的音频声音音量过小可以通过 AudioSegment 实现音量增强。 按照 python 库&#xff1a; pip install AudioSegment 代码具体实现&#xff1a; #-*-coding:utf-8-*- # date:2024-10 # Author: DataBall - XIAN # Function: 音频增加音量import os from pydub import …
阅读更多...
网络安全领域推荐证书介绍及备考指南

网络安全领域推荐证书介绍及备考指南

在网络安全领域&#xff0c;拥有专业认证不仅可以证明个人的专业能力&#xff0c;还能帮助在实际工作中应用先进的技术和知识。以下是几种热门的网络安全证书介绍及备考指南。 1. OSCP (Offensive Security Certified Professional) 证书简介 OSCP是针对渗透测试领域的入门级…
阅读更多...
在示波器里面外触发输入通道(EXT TRIG)什么作用?

在示波器里面外触发输入通道(EXT TRIG)什么作用?

在示波器中&#xff0c;外部触发输入通道&#xff08;EXT TRIG&#xff09;具有以下作用&#xff1a; 1. 提供外部信号触发 外部触发输入通道允许用户使用来自外部设备的信号作为触发源&#xff0c;而不仅仅依赖于示波器自身的输入通道。比如&#xff0c;可以用一个特定事件或…
阅读更多...
Docker 基础入门

Docker 基础入门

Docker 基础入门 前言 在云计算和微服务架构日益盛行的今天&#xff0c;软件开发与部署的效率和灵活性成为了企业竞争力的关键因素之一。Docker&#xff0c;作为一种开源的容器化平台&#xff0c;凭借其轻量级、可移植性和易于管理的特性&#xff0c;迅速成为现代软件开发和运…
阅读更多...
qt QWidget详解

qt QWidget详解

一、概述 QWidget是容器组件&#xff0c;继承自QObject类和QPaintDevice类。能够绘制自己和处理用户输入&#xff0c;是QT中所有窗口组件类的父类&#xff0c;是所有窗口组件的抽象&#xff0c;每个窗口组件都是一个QWidget&#xff0c;QWidget类对象常用作父组件或顶级组件使…
阅读更多...
小新学习K8s第一天之K8s基础概念

小新学习K8s第一天之K8s基础概念

目录 一、Kubernetes&#xff08;K8s&#xff09;概述 1.1、什么是K8s 1.2、K8s的作用 1.3、K8s的功能 二、K8s的特性 2.1、弹性伸缩 2.2、自我修复 2.3、服务发现和负载均衡 2.4、自动发布&#xff08;默认滚动发布模式&#xff09;和回滚 2.5、集中化配置管理和密钥…
阅读更多...
信发软件之电脑版拖动——未来之窗行业应用跨平台架构

信发软件之电脑版拖动——未来之窗行业应用跨平台架构

一、电脑版拖动 二、电脑版随意移动函数 var _movefalse;//移动标记 var _x,_y;//鼠标离控件左上角的相对位置 $("#"宿主id).click(function(){ }).mousedown(function(e){ _movetrue; _xe.pageX-parseInt($("#"宿主id).css("left")); _ye…
阅读更多...
【Python爬虫实战】多进程结合 BeautifulSoup 与 Scrapy 构建爬虫项目

【Python爬虫实战】多进程结合 BeautifulSoup 与 Scrapy 构建爬虫项目

#1024程序员节&#xff5c;征文# &#x1f308;个人主页&#xff1a;易辰君-CSDN博客 &#x1f525; 系列专栏&#xff1a;https://blog.csdn.net/2401_86688088/category_12797772.html ​ 前言 在大数据时代&#xff0c;爬虫技术是获取和处理网络数据的利器。面对需要处理大…
阅读更多...
报表工具怎么选？山海鲸VS帆软，哪个更适合你？

报表工具怎么选？山海鲸VS帆软，哪个更适合你？

概述 在国产报表软件市场中&#xff0c;山海鲸报表和帆软这两款工具都占有一席之地&#xff0c;许多企业在选择报表工具时常常在它们之间徘徊。然而&#xff0c;随着企业对数据分析需求的不断增长和复杂化&#xff0c;如何选取一款高效、易用且性价比高的报表工具&#xff0c;…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023