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

目录

一、基本思想

二、动图演示（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);
	
}

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

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

相关文章

简单的windows java -jar 无法启动jar包解决方法

简单的windows java -jar 无法启动jar包解决方法

简单的windows java -jar 无法启动jar包解决方法 1. 问题 我们项目是使用nacos作为注册中心以及配置中心&#xff0c;我们本地使用idea 进行服务配置以及启动发现没有问题&#xff0c;然后我们的服务经过maven install 打包后发布到LINUX服务启动也没有问题&#xff0c;但是我…
阅读更多...
三种单例实现

三种单例实现

1、不继承Mono的单例 实现 使用 注&#xff1a; 使用需要继承BaseManager 泛型填写自己本身 需要实现无参构造函数 2、挂载式的Mono单例 实现 使用 注&#xff1a; 使用需要继承SingletonMono 泛型填写自己本身 需要挂载在unity引擎面板 3、不用挂载式的单例 实现 使…
阅读更多...
Matlab学习01-矩阵

Matlab学习01-矩阵

目录 一&#xff0c;矩阵的创建 1&#xff0c;直接输入法创建矩阵 2&#xff0c;利用M文件创建矩阵 3&#xff0c;利用其它文本编辑器创建矩阵 二&#xff0c;矩阵的拼接 1&#xff0c;基本拼接 1&#xff09; 水平方向的拼接 2&#xff09;垂直方向的拼接 3&#xf…
阅读更多...
无人机之自主降落系统篇

无人机之自主降落系统篇

一、定义与功能 无人机自主降落系统是指无人机在无需人工干预的情况下&#xff0c;按照预先设定好的程序或基于实时感知的环境信息&#xff0c;自主完成降落过程的技术系统。该系统能够确保无人机在完成任务后安全、准确地降落到指定位置。 二、系统组成 无人机自主降落系统主…
阅读更多...
C#中的LINQ之美：优雅的数据查询与操作

C#中的LINQ之美：优雅的数据查询与操作

LINQ&#xff08;Language Integrated Query&#xff0c;语言集成查询&#xff09;是C#中一个强大的工具&#xff0c;它将查询功能直接融入到语言中&#xff0c;使开发者能够以一种更直观、更接近自然语言的方式来操作数据。LINQ不仅能极大地提高开发效率&#xff0c;而且让代码…
阅读更多...
一款好用的搜索软件——everthing（搜索比文件资源管理器快）

一款好用的搜索软件——everthing（搜索比文件资源管理器快）

everthing官网链接 在官网选择下载 1.下载后双击打开 2.点击OK&#xff08;需要其他语言自己选择&#xff09; 3.选择安装位置&#xff08;路径最好别带中文和空格&#xff09; 继续点击下一步 4. 点击下一步 5.继续点击安装 6.然后就完成了 7.点击打开然后就可以搜索了
阅读更多...
论文速读：基于 YOLO 目标检测的无源域自适应（ECCV2024）

论文速读：基于 YOLO 目标检测的无源域自适应（ECCV2024）

原文标题&#xff1a;Source-Free Domain Adaptation for YOLO Object Detection 中文标题&#xff1a;基于 YOLO 目标检测的无源域自适应 论文地址&#xff1a; https://arxiv.org/abs/2409.16538 代码地址&#xff1a; https://github.com/vs-cv/sf-yolo 1、Abstract 无源域自…
阅读更多...
接口测试 —— Postman 变量了解一下！

接口测试 —— Postman 变量了解一下！

Postman变量是在Postman工具中使用的一种特殊功能&#xff0c;用于存储和管理动态数据。它们可以用于在请求的不同部分、环境或集合之间共享和重复使用值。 Postman变量有以下几种类型&#xff1a; 1、环境变量&#xff08;Environment Variables&#xff09;: 环境变量是在…
阅读更多...
kubernetes中的微服务详解

kubernetes中的微服务详解

华子目录 什么是微服务微服务的类型ipvs模式ipvs模式配置方式注意 微服务类型详解ClusterIP类型Services创建后集群DNS提供解析ClusterIP中的特殊模式&#xff1a;headless无头服务 NodePort类型访问过程NodePort默认端口 LoadBalancer类型访问过程metalLBmetalLB功能部署metal…
阅读更多...
百度搜索推广和信息流推广的区别，分别适用于什么场景！

百度搜索推广和信息流推广的区别，分别适用于什么场景！

信息流推广和搜索广告&#xff0c;不仅仅是百度&#xff0c;是很多平台的两个核心推广方式。 1、搜索广告&#xff1a; 就是基于用户的搜索习惯&#xff0c;更多是用户有疑问、还有用户当下就要做出行动的广告。 比如上门服务、线上咨询服务、招商加盟、了解产品各种型号和信…
阅读更多...
[JAVA]JDBC如何实现写数据？——利用Java新增MySQL中存储的员工字段信息

[JAVA]JDBC如何实现写数据？——利用Java新增MySQL中存储的员工字段信息

我们在实现JDBC写数据之前需要先工具类做一些前置准备。—封装DbUtils工具类&#xff0c;是一个用于操作数据库的工具类&#xff0c;它提供了一些便捷的方式来执行SQL语句&#xff0c;获取数据库连接等。简化程序的开发。DbUtils工具类主要帮我们封装&#xff0c;打开连接&…
阅读更多...
LabVIEW提高开发效率技巧----插入式架构

LabVIEW提高开发效率技巧----插入式架构

随着LabVIEW项目规模的扩大和系统复杂性的增加&#xff0c;传统的单一代码架构难以应对后期维护和功能扩展的需求。插入式架构&#xff08;Plug-In Architecture&#xff09;作为一种模块化设计方式&#xff0c;通过动态加载和运行子VI&#xff0c;使系统功能更加灵活、模块化&…
阅读更多...
【LLM之Agent】《Tool Learning with Large Language Models: A Survey》论文阅读笔记

【LLM之Agent】《Tool Learning with Large Language Models: A Survey》论文阅读笔记

概述 背景信息 近年来&#xff0c;基于大型语言模型&#xff08;LLMs&#xff09;的工具学习成为增强LLMs应对复杂任务能力的有力范式。尽管这一领域快速发展&#xff0c;现有文献的碎片化以及缺乏系统组织&#xff0c;给新入门者带来了阻碍。因此&#xff0c;本论文旨在对现…
阅读更多...
Chrome DevTools 二： Performance 性能面板

Chrome DevTools 二： Performance 性能面板

Chrome DevTools 第二篇 Performance 主要介绍performance在我们日常开发中所起到的作用&#xff0c;以及如何利用performance 面板进行性能分析和相关优化建议。 性能面板 Performance 记录和分析页面运行中的所有活动&#xff0c;是解决前端性能问题的重要工具。 1. 控制栏…
阅读更多...
分布式链路追踪-01初步认识SkyWalking

分布式链路追踪-01初步认识SkyWalking

一 SkyWaling是什么&#xff1f; Skywalking是分布式系统的应用程序性能监视工具&#xff0c;专为微服务、云原生架构和基于容器&#xff08;Docker、K8s、Mesos&#xff09;架构而设计。SkyWalking 是观察性分析平台和应用性能管理系统&#xff0c;提供分布式追踪、服务网格遥…
阅读更多...
idea 无法输入中文 快速解决

idea 无法输入中文 快速解决

idea在某些情况会出现无法输入中文的情况&#xff0c;我们不去深究内部原因&#xff0c;直接上解决方案&#xff1a; 1、点击菜单help->Edit Custom VM Options 2、最后一行&#xff0c;追加&#xff1a; -Drecreate.x11.input.methodtrue 、 3、重启
阅读更多...
软件分享丨PDF Shaper

软件分享丨PDF Shaper

【资源名】PDF Shaper 【地址】https://www.pdfshaper.com/ 【资源介绍】 PDF Shaper Professional是一款功能强大的PDF文档编辑与转换工具&#xff0c;使用它可以对PDF文件进行各种转换、提取、合并、旋转、加密、解密等编辑操作&#xff0c;主要功能有分割和合并PDF文件&…
阅读更多...
无人机飞手执照培训为什么需要脱产学习？

无人机飞手执照培训为什么需要脱产学习？

无人机飞手执照培训需要脱产学习的原因主要基于以下几个方面&#xff1a; 一、知识体系的系统性与复杂性 无人机飞手培训涵盖的内容广泛且深入&#xff0c;包括无人机基础知识、飞行原理、气象学、法律法规等多个方面。这些知识体系相互关联&#xff0c;需要学员进行系统的学…
阅读更多...
排序算法 —— 计数排序

排序算法 —— 计数排序

目录 1.计数排序的思想 2.计数排序的实现 3.计数排序的分析 时间复杂度 空间复杂度 稳定性 优点 缺点 1.计数排序的思想 顾名思义&#xff0c;计数排序就是通过计数的方式来排序&#xff0c;其基本思想为&#xff1a; 开辟一个计数数组&#xff0c;统计每个数出现的次…
阅读更多...
Windows 10、Office 2016/2019 和 PPTP 和 L2TP协议即将退役，企业应尽早做好准备

Windows 10、Office 2016/2019 和 PPTP 和 L2TP协议即将退役，企业应尽早做好准备

关心微软技术和产品的朋友一定对这个网站很熟悉&#xff1a;https://microsoftgraveyard.com/&#xff0c;这里静静的躺着很多微软技术和产品。近日&#xff0c;微软又在准备一场新的“告别仪式”了&#xff0c;这次是 Windows 10、Office 2016/2019 和一些老旧的协议与技术。让…
阅读更多...
最新文章

Copyright @ 2022~2023