【数据结构--八大排序】之快速排序

在这里插入图片描述

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 ：阿然成长日记 👈点击可跳转
📆 个人专栏： 🔹数据结构与算法🔹C语言进阶
🚩 不能则学，不知则问，耻于问人，决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

文章目录

  • 一、快速排序的单趟排序
    • 方法一：霍尔法
      • 1.基本思路：
      • 2.原理图：
      • 3.动图：
      • 4.代码实现：
    • 方法二：挖坑法
      • 1.基本思路：
      • 2.原理图：
      • 3.动图：
      • 4.代码实现：
    • 方法三：前后指针法
      • 1.基本思路：
      • 2.动图
      • 3.代码实现：
  • 二、快速排序
    • 1.原理
    • 2.递归法:
  • 三、快速排序的优化
    • 1.优化方式：
    • 2.优化的使用方法：
  • 四、快速排序的完整实现（霍尔法）：
  • 五、 时间复杂度

在这里插入图片描述
前言：

前面，我花费了大量时间学习排序算法，八大排序基本结束，本篇将开始快速排序的讲解。本篇文章适合刚开始学习快速排序的同学，总结的很全面，整理的很清楚，希望能帮到你，加油！

一、快速排序的单趟排序

快速排序的单趟排序:是以一个数作为基准值，实现将数组中比基准数小的数放在基准值的左侧，比基准值大的数放在基准值的右侧。

方法一：霍尔法

霍尔法的由来：霍尔是一个人的名字，他是最初发现快速排序的人，所以，它使用的单趟排序算法被称为霍尔法。

1.基本思路：

​用key标记基准值的下标(数组下标0的元素)，使用两个指针left和right分别指向待排数组的最左侧和最右侧，right指针找比key基准值小的数，left指针找比key基准值大的数，找到后将两个数交换位置，同时实现大数右移和小数左移，直到left与right相遇则排序完成，最后将key基准值的下标返回，就完成了单趟排序。

2.原理图：

第一步：以第一个数作为基准值key
在这里插入图片描述

第二步：right从右边开始先找小于key的值，找到并停下来。
在这里插入图片描述

第三步：left从左边开始找大于key的值，找到并停下来。

在这里插入图片描述
第四步：交换两个值。Swap(&a[left], &a[right]);

在这里插入图片描述

第五步：重复第二步，找小于key的值，找到并停下来。
在这里插入图片描述
第六步：第三步：left从左边开始找大于key的值，找到并停下来。
此时left，right相遇，则退出循环，并交换key和left的值。

在这里插入图片描述

以上就是一次完整的快速排序的单趟排序。

3.动图：

在这里插入图片描述

4.代码实现：

//霍尔法int Pritition1(int* a, int left, int right)
{//使用key保存基准值的下标int key = left;while (left < right){//先从右边开始向左找小于a[key]的值下标。while (left < right && a[key] < a[right])right--;//没找到就一直向左寻找//再从左边开始向右找大于a[key]的值下标。while (left<right && a[key]>a[left])left++;//没找到就一直向右寻找//交换两个值Swap(&a[left], &a[right]);}//当left和right相遇时，将a[left]赋值给a[key]//该操作是为了下一轮的排序Swap(&a[left], &a[key]);//left相当于分界点坐标return left;
}

方法二：挖坑法

1.基本思路：

挖坑法是将key基准值用变量单独保存，然后将key的位置空出来形成一个坑，left和right指针分别从左右两端向中心遍历，此时left先指向这个坑，从右边先开始，right找比key小的数，找到后将该数直接放进坑里，并将自己空出来的位置设置为坑，left找比key大的数，找到后将该数放进坑里，并将现在空出来的位置设置为坑，一直遍历，直到left与right相遇，相遇位置一定为坑(left和right必定有一个指向坑)，此时将key基准值放进坑内，并返回基准值下标完成单趟排序。

2.原理图：

第一步：使用变量key保存基准值。
在这里插入图片描述
第二步：right从右边开始先找小于key的值，找到就停下来，将该位置的值放入坑内。

在这里插入图片描述

第三步：left从左边开始找大于key的值，找到并停下来，将该位置的值放入坑内。
在这里插入图片描述

第四步：重复第二步，找小于key的值，找到并停下来。将该位置的值放入坑内。
在这里插入图片描述
第五步：left从左边开始找大于key的值，找到并停下来，将该位置的值放入坑内。

在这里插入图片描述
注意：此时没有找到就left和right相遇,此时left，right相遇，则退出循环，并交换key放入left。
在这里插入图片描述

3.动图：

在这里插入图片描述

4.代码实现：

//挖坑法
int  Pritition2(int* a, int left,int right)
{//使用key保存基准值int key = a[left];//定义hole是坑；初始坑的位置下标是leftint hole = left;while (left < right){//从右向左找小于a[key]的值while (left < right && a[right] >= key)right--;//没找到就一直向左寻找a[left] = a[right];//将找到的值放入坑中hole = right;//并且将找到的位置置为新的坑while (left < right && a[left] <= key)left++;//没找到就一直向右寻找a[right] = a[left];//将找到的值放入坑中hole = left;//并且将找到的位置置为新的坑}a[hole] = key;//将基准值交换到hole位置//此时hole的位置就是分界点return hole;
}

方法三：前后指针法

1.基本思路：

（1） 用key保存数组第一个元素作为基准值，定义前指针prev指向第一个数，后指针cur指向前指针的后一个位置。

（2） 由cur挨个遍历数组中的数据，如果cur寻找比key基准值小的数，则prev后移一个位置，并且交换cur和prev所对应的元素值，cur和prev位置不变。

（3） 依次类推直到cur完全遍历完数组，停止。

prev之前的值一定小于key基准值，而prev与cur之间的一定大于基准值
最后将prev处与key位置的元素交换，将基准值下标返回（此时基准值下标已经交换到prev位置）。则完成单趟排序

2.动图

在这里插入图片描述

3.代码实现：

//前后指针法
int PartSort3(int* arr, int left, int right)
{int key = left;int prev = left;int cur = left + 1;while (cur <= right){//arr[cur]小于基准值就交换//这里做了优化，使用前置++prev//如果prev+1等于cur则不用交换if (arr[cur] <= arr[key] && ++prev != cur)	{Swap(&arr[cur], &arr[prev]);}cur++;}//交换prev处元素到key位置Swap(&arr[key], &arr[prev]);//返回prev,相当于分界点return prev;
}

二、快速排序

1.原理

快速排序从整体上来看，是以一个选定的数为基准，将数组分为两个子序列，左子序列放比基准数小的，右子序列放比基准数大的数，然后再将子序列以以上方式同样分割，直到数组有序。
快速排序使用递归的方式调用单趟排序，每次调用后都以基准值为界，将数组分为2个子序列，继续排序。一直分到只有一个元素停止。

2.递归法:

void QuickSort(int* a, int left,int right)
{if (left >= right){return;}int privot = Pritition1(a, left,right );QuickSort(a, left, privot - 1);QuickSort(a, privot + 1, right);
}

三、快速排序的优化

1.优化方式：

采取三数取中法： 在left、right、和中间下标的值中选取一个折中值，基准值不可能为最大值或最小值，可以避免出现最差情况，从而提高快排的时间复杂度。

int GetMidIndex(int* arr, int left, int right)
{int mid = (left + right) / 2;if (arr[left] < arr[right]){if (arr[mid] < arr[left]){return left;}else if (arr[mid] <arr[right]){return mid;}else{return right;}}else{if (arr[mid] < arr[right]){return right;}else if (arr[mid] < arr[left]){return mid;}else{return left;}}
}

2.优化的使用方法：

在我们选择好基准值后，为了保证原来的单趟排序保持原有状态，我们将选好的基准数与数组中第一个数交换位置，然后使用第一个数作为基准值排序
使用方法：

int PartSort(int* arr, int left, int right)
{//获取基准值，并与left交换位置int key = GetMidIndex(arr, left, right);//交换key和left对应的值，但是key指向不变Swap(&arr[key], &arr[left]);//将key指向数组开始位置key = left;//单趟排序算法...
}

四、快速排序的完整实现（霍尔法）：

//三数取中
int GetMidIndex(int* arr, int left, int right)
{int mid = (left + right) / 2;if (arr[left] < arr[right]){if (arr[mid] < arr[left]){return left;}else if (arr[mid] < arr[right]){return mid;}else{return right;}}else{if (arr[mid] < arr[right]){return right;}else if (arr[mid] < arr[left]){return mid;}else{return left;}}
}
//单趟排序
int Pritition1(int* a, int left, int right)
{//使用三数取中int key = GetMidIndex(arr, left, right);Swap(&arr[key], &arr[left]);key = left;while (left < right){//先从右边开始向左找小于a[key]的值下标。while (left < right && a[key] < a[right])right--;//没找到就一直向左寻找//再从左边开始向右找大于a[key]的值下标。while (left<right && a[key]>a[left])left++;//没找到就一直向右寻找//交换两个值Swap(&a[left], &a[right]);}//当left和right相遇时，将a[left]赋值给a[key]//该操作是为了下一轮的排序Swap(&a[left], &a[key]);//left相当于分界点坐标return left;
}
//采用递归法
void QuickSort(int* a, int left,int right)
{if (left >= right){return;}int privot = Pritition1(a, left,right );QuickSort(a, left, privot - 1);QuickSort(a, privot + 1, right);
}

五、 时间复杂度

在这里插入图片描述

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

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

相关文章

Flink--9、双流联结（窗口联结、间隔联结）

Flink--9、双流联结（窗口联结、间隔联结）

星光下的赶路人star的个人主页 我还有改变的可能性&#xff0c;一想起这点&#xff0c;我就心潮澎湃 文章目录 1、基于时间的合流——双流联结&#xff08;Join&#xff09;1.1 窗口联结&#xff08;Window Join&#xff09;1.2 间隔联结&#xff08;Interval Join&#xff09;…
阅读更多...
苹果手机怎么备份所有数据？2023年iPhone 15数据备份常用的3种方法！

苹果手机怎么备份所有数据？2023年iPhone 15数据备份常用的3种方法！

当苹果手机需要进行刷机、恢复出厂设置、降级iOS系统等操作时&#xff0c;我们需要将自己的iPhone数据提前进行备份。 特别是在苹果发布新iOS系统时&#xff0c;总有一些小伙伴因为升降级系统&#xff0c;而导致了重要数据的丢失。 iPhone中储存着重要的照片、通讯录、文件等数…
阅读更多...
出去重复的列值(关键词:distinct)

出去重复的列值(关键词:distinct)

MySQL从小白到总裁完整教程目录:https://blog.csdn.net/weixin_67859959/article/details/129334507?spm1001.2014.3001.5502 语法格式: select distinct 列名 from 表名; 案例&#xff1a;查询emp表中&#xff0c;员工的职位&#xff08;job&#xff09;&#xff0c;并去重…
阅读更多...
Redis-分布式锁

Redis-分布式锁

分布式锁相关内容 超卖问题切入可以使用互斥锁给先获取到锁的线程加锁吗&#xff1f;使用redis分布式锁解决超卖问题setnx命令实现分布式锁为什么需要设置过期时间&#xff1f;Redis实现分布式锁如何合理控制锁的有效时长 redisson实现分布式锁 超卖问题切入 我们先来看一个项目…
阅读更多...
【Docker内容大集合】Docker从认识到实践再到底层原理大汇总

【Docker内容大集合】Docker从认识到实践再到底层原理大汇总

前言 那么这里博主先安利一些干货满满的专栏了&#xff01; 首先是博主的高质量博客的汇总&#xff0c;这个专栏里面的博客&#xff0c;都是博主最最用心写的一部分&#xff0c;干货满满&#xff0c;希望对大家有帮助。 高质量博客汇总https://blog.csdn.net/yu_cblog/categ…
阅读更多...
前端TypeScript学习day01-TS介绍与TS部分常用类型

前端TypeScript学习day01-TS介绍与TS部分常用类型

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 TypeScript 介绍 TypeScript 是什么 TypeScript 为什么要为 JS 添加类型支持&#xff1f; TypeScript 相…
阅读更多...
【已解决】spring-boot项目使用maven打包时出现BOOT-INF文件夹的问题

【已解决】spring-boot项目使用maven打包时出现BOOT-INF文件夹的问题

jar中多了这个BOOT-INF文件夹的原因&#xff0c;主要是因为我们在maven的pom文件中加入了spring-boot-maven-plugin这个插件&#xff0c;如下所示&#xff1a; 只需要将加个configuration标签&#xff0c;并在里面嵌套加入一个skip子标签&#xff0c;并将skip的值设为true&…
阅读更多...
vulnhub靶机doubletrouble

vulnhub靶机doubletrouble

下载地址&#xff1a;doubletrouble: 1 ~ VulnHub 主机发现 arp-scan -l 端口扫描 nmap --min-rate 1000 -p- 192.168.21.151 端口服务扫描 nmap -sV -sT -O -p22,80 192.168.21.151 漏洞扫描 nmap --scriptvuln -p22,80 192.168.21.151 先去看看web页面 这里使用的是qdpm …
阅读更多...
如何一步步优化负载均衡策略

如何一步步优化负载均衡策略

发展到一定阶段后&#xff0c;Web 应用程序就会增长到单服务器部署无法承受的地步。这时候企业要么提升可用性&#xff0c;要么提升可扩展性&#xff0c;甚至两者兼而有之。为此&#xff0c;他们会将应用程序部署在多台服务器上&#xff0c;并在服务器之前使用负载均衡器来分配…
阅读更多...
pycharm配置python3.8版本专门用于undecteded_chromedriver测试

pycharm配置python3.8版本专门用于undecteded_chromedriver测试

pycharm配置python3.8版本专门用于undecteded_chromedriver测试 作者&#xff1a;虚坏叔叔 博客&#xff1a;https://pay.xuhss.com 早餐店不会开到晚上&#xff0c;想吃的人早就来了&#xff01;&#x1f604; 一、Pycharm及python环境的配置 1.安装python-3.8.7rc1-amd64.e…
阅读更多...
医学影像归档与通讯系统（PACS）系统源码 PACS三维图像后处理技术

医学影像归档与通讯系统（PACS）系统源码 PACS三维图像后处理技术

医学影像归档与通讯系统&#xff08;PACS&#xff09;系统源码 PACS三维图像处理 医学影像归档与通讯系统&#xff08;PACS&#xff09;系统&#xff0c;是一套适用于从单一影像设备到放射科室、到全院级别等各种应用规模的医学影像归档与通讯系统。PACS集患者登记、图像采集、…
阅读更多...
NUWA论文阅读

NUWA论文阅读

论文链接&#xff1a;NUWA: Visual Synthesis Pre-training for Neural visUal World creAtion 文章目录 摘要引言相关工作视觉自回归模型视觉稀疏自注意 方法3D数据表征3D Nearby Self-Attention3D编码器-解码器训练目标 实验实现细节与SOTA比较T2I微调T2V微调V2V微调Sketch-t…
阅读更多...
基于SpringBoot的信息化在线教学平台的设计与实现

基于SpringBoot的信息化在线教学平台的设计与实现

目录 前言 一、技术栈 二、系统功能介绍 学生信息管理 教师信息管理 学生成绩管理 留言板 学生注册管理 留言反馈 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已…
阅读更多...
数据结构 2.1 单链表

数据结构 2.1 单链表

1.单链表 线性表&#xff1a;1.有限的序列 2.序列中的每一个元素都有唯一的前驱和后继&#xff0c;除了开头和结尾的两个节点。 顺序表&#xff1a;分配一块连续的内存去存放这些元素&#xff0c;eg、数组 链表&#xff1a;内存是不连续的&#xff0c;元素会各自被分配一块内…
阅读更多...
vue3 element-ui-plus Carousel 跑马灯 的使用 及 踩坑记录

vue3 element-ui-plus Carousel 跑马灯 的使用 及 踩坑记录

vue3 element-ui-plus Carousel 跑马灯 的踩坑记录 Carousel 跑马灯首页跑马灯demo Carousel 跑马灯 首先&#xff0c;打开其官网-跑马灯案例 跑马灯代码&#xff1a; <el-carousel :interval"5000" arrow"always"><el-carousel-item v-for"…
阅读更多...
【高级rabbitmq】

【高级rabbitmq】

文章目录 1. 消息丢失问题1.1 发送者消息丢失1.2 MQ消息丢失1.3 消费者消息丢失1.3.1 消费失败重试机制 总结 2. 死信交换机2.1 TTL 3. 惰性队列3.1 总结&#xff1a; 4. MQ集群 消息队列在使用过程中&#xff0c;面临着很多实际问题需要思考&#xff1a; 1. 消息丢失问题 1.1…
阅读更多...
深度学习——实战Kaggle比赛：预测房价

深度学习——实战Kaggle比赛：预测房价

深度学习——实战Kaggle比赛&#xff1a;预测房价 文章目录 前言一、Kaggle初识1.1. 注册Kaggle账号1.2. 进入房价预测比赛页面 二、预测房价实战2.1. 下载和缓存数据集2.2. 访问和读取数据2.3. 数据预处理2.4. 训练2.5. K折交叉验证2.6. 模型选择2.7. 提交Kaggle预测 总结 前言…
阅读更多...
Unicode与UTF-8

Unicode与UTF-8

软件开发中乱码问题经常遇到&#xff0c;Unicode&#xff0c;UTF-8, ASCII等都是高频词语&#xff0c;不过具体是啥意思其实都不清楚。这个周末研究了一下&#xff0c;略有了解&#xff0c;记录一下。 Unicode Unicode本身是纯理论的东西&#xff0c;和具体计算机实现无关。它…
阅读更多...
【数据库——MySQL】（15）存储过程、存储函数和事务处理习题及讲解

【数据库——MySQL】（15）存储过程、存储函数和事务处理习题及讲解

目录 1. 题目1.1 存储过程1.2 存储函数1.3 事务处理 2. 解答2.1 存储过程2.2 存储函数2.3 事务处理 1. 题目 1.1 存储过程 创建表 RandNumber &#xff1a;字段&#xff1a;id 自增长&#xff0c; data int&#xff1b; 创建存储过程向表中插入指定个数的随机数&#xff08;1-…
阅读更多...
Godot 官方2D游戏笔记(1)：导入动画资源和添加节点

Godot 官方2D游戏笔记(1)：导入动画资源和添加节点

前言 Godot 官方给了我们2D游戏和3D游戏的案例&#xff0c;不过如果是独立开发者只用考虑2D游戏就可以了&#xff0c;因为2D游戏纯粹&#xff0c;我们只需要关注游戏的玩法即可。2D游戏的美术素材简单&#xff0c;交互逻辑简单&#xff0c;我们可以把更多的时间放在游戏的玩法…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023