【排序算法】快速排序(四个版本以及两种优化)含动图)

制作不易,三连支持一下吧!!!

文章目录

  • 前言
  • 一.快速排序Hoare版本实现
  • 二.快速排序挖坑法版本实现
  • 三.快速排序前后指针版本实现
  • 四.快速排序的非递归版本实现
  • 五.两种优化
  • 总结


前言

前两篇博客介绍了插入和选择排序,这篇博客我们将会介绍一个非常重要的排序算法——快速排序,它的实践价值要大远远于前两种排序。

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。


一、快速排序Hoare版本实现

动图展示如下:

这里再简单解释一下:

我们一般选取最左或最后边的值作为基准值(key),如果我们选择最左边的值为key,且我们要排成升序序列,那我们就让最右边先走(为了保证相遇位置的值一定比key小),找到比key小的位置停下来,然后左边再走,找到比key大的位置停下来,两者交换,循环上述操作,直至left和right相遇,再将相遇位置的值与key交换,这样就完成了单趟排序。

key位置的元素就排到了合适的位置。 

之后递归左右区间即可。

代码实现:

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void QuickSort(int* a, int begin, int end)
{
	//最小子问题,返回条件
	if (begin >= end)
		return;

	int key = begin;
	int left = begin;
	int right = end;

	while (left<right)
	{
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		while (left < right && a[left] <= a[key])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}
	Swap(&a[key], &a[left]);
	key = left;

	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);

}

 二.快速排序挖坑法版本实现

挖坑法是在hoare大佬版本的基础上为了好让大家理解而改进的一种思路,因为hoare版本如果以最左边的值做key,则必须要让右边先走,让最右边的值做key,则必须要让左边先走,否则会出现错误。 而如果是挖坑法,则无需关心这个问题。大家自然而然会按正确的方式实现。

动图演示如下: 

通俗一点解释:

我们将key位置的值保存下来,将那个位置视为一个坑位,右边先走,找到比key小的值就填到坑位中,坑位就更新到新的位置,左边再找大,再更新坑位的位置,直到left和right相遇,将原来key中的值放到坑位中就完成了单趟排序。

这样我们就避免了考虑哪边先走的问题,因为如果左边为坑,我们自然而然的就会让右边先走!

代码实现如下:

QuickSort2(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int left = begin, right = end;
	int key = a[begin];
	int hole = begin;

	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}

		a[hole] = a[right];
		hole = right;

		while (left < right && a[left] <= key)
		{
			left++;
		}

		a[hole] = a[left];
		hole = left;
	}

	a[hole] = key;
	int keyi = hole;

	QuickSort2(a, begin, keyi - 1);
	QuickSort2(a, keyi + 1, end);

}

三.快速排序前后指针版本实现 

前后指针版本是这三种方法里面最值得推荐的一种,因为它实现出来非常的简单。

动图演示如下:

 

 简单解释一下:

定义两个指针prev和cur,如果啊a[cur]比key位置的值小,就让prev前进一步,并交换cur和prev位置的值,如果a[cur]比key位置的值大,就只++cur。

最后,prev和cur之间的值就是整个序列中比key位置的值大的值。prev之前的值就是比key位置的值小的值。

代码实现如下: 

QuickSort3(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int prev = begin, cur = begin + 1;
	int keyi = begin;
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}

		cur++;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;

	QuickSort3(a, begin, keyi - 1);
	QuickSort3(a, keyi + 1, end);

}

 

四.快速排序非递归法实现 

之前的三种方法虽然思路略有不同,但本质都是分治递归的思想,这种思想比较容易理解,但是递归深度过深可能会导致栈溢出,因此,我们必须掌握非递归的实现,以适用于所有场景。 

从递归改成非递归的方法一般有两种:

  • 直接改成循环——例如:斐波那契数列
  • 借助于栈或队列的结构。

我们这里就是要借助于栈的数据结构。

整体思路就是压栈,每次取出一个区间进行单趟排序,然后再入栈,如果区间不存在或只有一个元素就不再入栈,直至栈为空时,排序就完成了。 

代码实现如下: 

void QuickSortNonR(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 prev = begin;
		int cur = begin + 1;
		int keyi = begin;
		while (cur <= end)
		{
			if (a[cur] < a[keyi] && ++prev != cur)
			{
				Swap(&a[prev], &a[cur]);
			}
			cur++;
		}
		Swap(&a[keyi], &a[prev]);
		keyi = prev;

		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi+1);
		}
		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);
}

 

五 两种优化(小区间优化和三数取中)

1.小区间优化

从分治的角度看,快速排序是一种二叉树结构的排序,有些大佬觉得最后几层占了整个递归次数的百分之八九十,消耗有些大,所以当区间长度小于一定数量(一般是10)时就直接用直接插入排序就好了。

也就是说最小子问题不再是区间不存在或只有一个值了,而是区间长度小于10.

if (end - begin + 1 <= 10)
InsertSort(a, end - begin + 1);

2.三数取中 

快速排序在序列有序时,效率是不高的,时间复杂度不再是O(N*logN),而是O(N^2)。

为了尽量避免出现最坏的情况,我们可以采用三数取中的方法,防止key是最大或最小的值。

//三数取中
int GetMid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[right] > a[mid])
		{
			return mid;
		}
		else if (a[right] < a[left])
		{
			return left;
		}
		else {
			return right;
		}

	}
	else {
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else {
			return right;
		}
	}
}

 

以hoare版本为例,加入三数取中后,就是这样: 

//快速排序Hoare版本
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int begin = left, end = right;

	//随机数作key
	//int randi=rand()%(right-left+1);
	//randi += left;
	//Swap(&a[randi], &a[left]);

	//三数取中
	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);


	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}

		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);

}

 


总结

快速排序是实践中运用非常多的一种排序,它的价值非常高,我们应该熟练掌握快速排序的思想。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

探索未来,与移动云共舞

探索未来&#xff0c;与移动云共舞 在数字化飞速发展的今天&#xff0c;云计算已经成为企业、政府乃至个人用户不可或缺的一部分。而在众多云服务提供商中&#xff0c;移动云凭借其独特的优势&#xff0c;为用户带来前所未有的体验。接下来&#xff0c;让我们一起走进移动云的世…

Java—选择排序

选择排序是一种简单但高效的排序算法。它的基本思想是从未排序的部分中选择最小&#xff08;或最大&#xff09;的元素&#xff0c;并将其放置在已排序部分的末尾。 实现步骤 具体实现选择排序的步骤如下&#xff1a; 遍历数组&#xff1a;从数组的第一个元素开始&#xff0…

为什么股票市场里有认贼为父的现象?

文章大纲&#xff1a;&#xff08;本文2648字&#xff0c;完整版本应该3500以上&#xff0c;耗时一个钟&#xff09; 1、前言&#xff1a;逻辑与博弈 2、直觉引入博弈焦点 3、上周4-5的市场博弈视角 4、下周一视角能看到的东西 5、视角背后看到的情绪周期市场共识下的博弈…

[LDAP: error code 34 - invalid DN]

目前我的项目版本&#xff1a; Spring版本:5.3.15SpringBoot版本:2.6.3 完整错误 org.springframework.ldap.InvalidNameException: [LDAP: error code 34 - invalid DN]; nested exception is javax.naming.InvalidNameException: [LDAP: error code 34 - invalid DN]at org.s…

MyBatis 学习笔记(一)

MyBatis 封装 JDBC :连接、访问、操作数据库中的数据 MyBatis 是一个持久层框架。 MyBatis 提供的持久层框架包括 SQLMaps 和 Data Access Objects&#xff08;DAO&#xff09; SQLMaps&#xff1a;数据库中的数据和 Java数据的一个映射关系 封装 JDBC 的过程Data Access Ob…

最新ChatGpt Desktop for Mac 安装使用教程

1. 下载地址 请点击链接下载 ChatGPT Desktop for MacOS 2. 使用要求 MacOS 版本 14需要时M1芯片的&#xff0c;如果你是因特尔的暂时还还不行 就算下载了也会出现下面的异常 3. 获取权限资格 目前 ChatGPT MacOS Desktop还不是全量开放的, 如果你没有收到通知说明你还没…

链接物化视图在 ClickHouse 中的应用

本文字数&#xff1a;7728&#xff1b;估计阅读时间&#xff1a;20 分钟 作者&#xff1a;Mark Needham 审校&#xff1a;庄晓东&#xff08;魏庄&#xff09; 本文在公众号【ClickHouseInc】首发 在 ClickHouse 中&#xff0c;物化视图【https://clickhouse.com/docs/en/guide…

E1载波:一种2.048Mbps速率的PCM载波

E1载波的基本帧由32个子信道组成 帧长为256个bit,分为32个相等时隙&#xff0c;一个时隙为8个bit。256/328 时隙的编号为CH0~CH31 全帧包含256位,且每一帧用 125us时间传送 E1载波支持的数据传输效率为2.048Mbps&#xff0c;用PCM编码&#xff08;即 256bit/125us2.048Mbps…

现代密码学——消息认证和哈希函数

1.概述 1.加密-->被动攻击&#xff08;获取消息内容、业务流分析&#xff09; 消息认证和数字签名-->主动攻击&#xff08;假冒、重放、篡改、业务拒绝&#xff09; 2.消息认证作用&#xff1a; 验证消息源的真实性&#xff0c; 消息的完整性&#xff08;未被篡改…

基于Docker的ElasticSearch、Kibana服务搭建并开启用户鉴权

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;云原生与服务部署专栏 &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正 目录 1. 前言 2. 服务搭建 2.1. 部署ElasticSearch 2.2. 部署Kibana 3. …

Spring中RestTemplate用法

系列文章目录 文章目录 系列文章目录前言 前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff0c;这篇文章男女通用&#xff0c;看懂了就去分享给你的码吧。 RestTemplate 是从…

十进制异步计数器

十进制异步计数器 十进制异步加法计数器 【例1】设计一个十进制异步加法计数器&#xff0c;要求电路按 8421 BCD 码进行加法计数 Step1&#xff1a;建立原始状态转换图 根据状态转换图画出对应的时序图&#xff0c;然后从翻转要求出发&#xff0c;为每个触发器选择合适的时钟…

清理安卓手机广告

保存脚本另存为 Fuck_AD.sh&#xff0c;在手机执行后体验效果。 echo ""echo " " echo " - 开始执行清理广告库文件" sleep 3files(/data/app/*/*/lib/arm64/libpangleflipped.so/data/app/*/*/lib/arm64/libzeus_direct_dex.so/data/app/*/*/l…

Python+Flask+Pandas怎样实现任意时间范围的对比数据报表

话不多说,有图有源码: 1.上图 2.因为是低代码的,只能发重要有用的代码片段了 实现思路:1)获取指定时间范围内的数据:2)df合并 #----------年份替换----------------for syear in range(int(byear),int(eyear)1):start_datestr(syear)strbdate[4:]end_datestr(syear)stredate…

[Spring Cloud] (9)XSS拦截器

文章目录 简述本文涉及代码已开源Fir Cloud 完整项目防XSS攻击必要性&#xff1a;作用&#xff1a; 整体效果后端增加拦截器开关配置pom中增加jsoup依赖添加JSON处理工具类添加xss拦截工具类防XSS-请求拦截器 前端 简述 本文涉及代码已开源 本文网关gateway&#xff0c;微服务…

python-找出四位数中的玫瑰花数

【问题描述】玫瑰花数指一个n位数&#xff08;n>4),其每位上的数字的n次幂之和等于本身。 请求出所有四位数中的玫瑰花数 【输入形式】 【输出形式】 【样例输入】 【样例输出】1634 8208 9474 【样例说明】 【评分标准】 完整代码如下&#xff1a; for n in ra…

小程序-修改用户头像

1、调用拍照 / 选择图片 // 修改头像 const onAvatarChange () > { // 调用拍照 / 选择图片 uni.chooseMedia({ // 文件个数 count: 1, // 文件类型 mediaType: [image], success: (res) > { console.log(res) // 本地临时文件路径 (本地路径) const { tempFilePath } …

【大数据】MapReduce JAVA API编程实践及适用场景介绍

目录 1.前言 2.mapreduce编程示例 3.MapReduce适用场景 1.前言 本文是作者大数据系列专栏的其中一篇&#xff0c;前文我们依次聊了大数据的概论、分布式文件系统、分布式数据库、以及计算引擎mapreduce核心概念以及工作原理。 书接上文&#xff0c;本文将会继续聊一下mapr…

【zotero6】ZotCard笔记模板分享

zotcard插件下载链接&#xff1a;传送门 因为zotero出了新的zotero7&#xff0c;现在下载插件会出现zotero6和zotero7不兼容的情况&#xff0c;通过这个链接可以区分适配不同版本的插件。 下载后点击工具的附加组件 然后选择通过文件添加 就可以添加插件了 再通过 工具->…

【全开源】二手车置换平台系统小程序(FastAdmin+ThinkPHP+Uniapp)

二手车置换平台系统 特色功能&#xff1a; 车辆评估&#xff1a;系统提供车辆状况、性能和价值的评估功能&#xff0c;通过拍照、上传图片等方式自动识别车辆信息并给出估价建议&#xff0c;帮助买家和卖家更准确地了解车辆价值。 在线交易&#xff1a;平台提供在线购车、售车…