当前位置： 首页 > news >正文

快速排序的三种单趟排序思想的实现与优化 - 递归与非递归

news 来源：原创 2024/5/3 3:58:13

目录

  • 前言
  • 1. 递归实现
    • 1.1 hoare版本
      • 1.1.1 基本思想
      • 1.1.2 代码实现
      • 1.1.3 快排优化
    • 1.2 挖坑法
    • 1.3 前后指针版本
    • 1.4 希尔 堆排与快排的效率对比
  • 2. 非递归实现
  • 总结

前言

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，大厂也喜欢考，所以快排必须理解并掌握。

1. 递归实现

1.1 hoare版本

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

1.1.1 基本思想

其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

简单说就是：选取key(一般为最左边或者最右边的位置)为基准值，第一趟排序结束后，左边都比key小，右边都比key大，这样该序列就被key分割为左子序列和右子序列，然后分别递归左子序列和右子序列让其有序，就完成了排序。

在这里插入图片描述
根据上图可知：
选取key下标位置的值作为基准值，然后R先动，找到比key小的就停下，这时L开始行动，寻找比key大的就停下，停下后交换两个位置的值，继续寻找，直到L和R相遇，然后把相遇位置的值与key进行交换，这是一趟排序的思路。

这里会有一个问题：相遇点的值有没有可能会比key位置的值大？

答案是不会出现这种情况，因为是R先走，所以保证了相遇位置的值一定是比key位置的值要小。

为什么R先走就可以保证上面的情况？可以来分析，有两种情况：

  1. R停下来了，L遇到R
    因为R只有在遇到比key小的时候会停下来，所以L遇到R的位置一定是比key小的。

  2. L停下来了，R遇到L
    当R一直找不到比key大的就会遇到L，此时L的位置是已经交换过了，因此相遇位置也比key小。

同样的道理如果是最右边的位置做了key，要让L先走。这两种情况的谁先走的顺序错了大概率会出现错误。

单趟排序的意义：

  1. key已经到了应该到的位置。
  2. key分割出两个子区间，两个子区间有序那么就整体有序了 - 子问题递归

1.1.2 代码实现

//[left, right]
int PartSort1(int* a, int left, int right)
{
	//先选择左右两边其中的一个位置的下标作为keyi
	//假设选左，把小于keyi的值都放在keyi的左边
	//把大于keyi的值放在keyi的右边
	int keyi = left;
	//[left,right]
	while (left < right)
	{
		//R找小
		//1. 虽然外层循环判断了left<right
		//但是内层还是要判断，如果都比它大
		//一直--就会越界
		//2. 要把相等的过滤掉，否则会出现死循环的问题
		//例如[6,6,6,6,6,6]
		//不判断相等一直死循环了。
		while (left < right && a[right] >= a[keyi])
			--right;
		//L找大
		//同样的道理 
		while (left < right && a[left] <= a[keyi])
			++left;
		if (left < right)
			Swap(&a[left], &a[right]);
	}
	//把keyi位置与相遇位置交换
	Swap(&a[left], &a[keyi]);
	//最后返回相遇位置作为递归参数
	return left;
}
//这里的是左闭右闭区间[left, right]
void QuickSort(int* a, int left, int right)
{
	//当区间只有一个值或者没有区间就返回
	//返回时区间已经有序了
	if (left >= right)
		return;
	int keyi = PartSort1(a, left, right);
	//此时a被keyi分割为两个子区间
	//左子区间都小于keyi
	//右子区间都大于keyi
	//此时递归左右两个子区间来让区间有序
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

大致模拟递归过程，可以发现结构和二叉树十分相似。
在这里插入图片描述

上图是比较好的情况，每次选取的key都是中间值，然后不断二分，此时的时间复杂度为O(N*logN)，但是最坏的情况呢？

最坏的情况是接近有序或者有序, 此时的递归过程大致为：
在这里插入图片描述
在这种最坏的情况下，需要递归调用大概N次，快排的时间复杂度就成了O(N²)，并且数据量大的情况下递归深度太深还会导致栈溢出。

1.1.3 快排优化

不难看出导致这种情况最明显的一个原因就是选择的keyi是在最左边也就是最小的位置上，右边基本上都比它大。

因此基于这种情况可以对选数也就是对keyi的位置进行优化选择，优化方法中比较被认可的一种方法是：三数取中。

三数取中：即知道这组数列的首和尾后，便可以求出这个数列的中间位置的数，只需要在首，中，尾这三个数据中，选择一个排在中间的数据作为基准值，进行快速排序，即可进一步提高快速排序的效率。

三数取中不管数据有序与否都可以达到最佳效率。

单趟代码实现：

//三数取中
int GetMidIndex(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	//相等的情况无需单独判断
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[left] > a[right])
			return right;
		else
			return left;
	}
	else    //[left] <= a[mid]
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left] > a[right])
			return left;
		else
			return right;

	}
}
int PartSort1(int* a, int left, int right)
{
	//选出中位数的位置
	int mid = GetMidIndex(a, left, right);
	//交换开头和中位数的位置
	Swap(&a[left], &a[mid]);
	//此时left为中位数
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		if (left < right)
		{
			Swap(&a[left], &a[right]);
		}
	}
	Swap(&a[left], &a[keyi]);
	return left;
}

主函数的逻辑不变，只是针对选数进行了优化。

那么主函数是否还可以优化呢？
上面提到过快排是二叉树结构的交换排序，而二叉树的每一层结点都是呈等比数列增长，最后一层占了总数的一半，倒第二层占了四分之一等。化
如上图，最后三层的递归调用次数就占了总调用次数的百分之八十多，而最后三层的数据量又很小，没必要继续递归来让这点数据有序。那么就有人想出了一种办法：把最后三层(左右)的递归调用给干掉，采用其它的排序来提高部分效率，也称之为小区间优化。
小区间优化采用插入排序，插排这里最合适。

主函数代码实现：

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//数据量在8基本上就是最后三层了，大一点也是可以的
	//大了无非就是再少几层递归调用，更快的进行插排
	else if (right - left <= 8)
	{
		//注意这里并不是从头开始排
		//而是从a+left地址位置的数据开始排序
		//而数据个数则为 right - left + 1
		InsertSort(a + left, right - left + 1);
	}
	else
	{
		int keyi = PartSort1(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}

1.2 挖坑法

该方法本质不变，只是单趟排序与hoare法的思路有些许差别，是hoare方法的改造版本。
在这里插入图片描述
简单说就是：左边做坑，保存最开始坑位的值key，右边先走，找小与key的值填左边的坑，然后右边为新的坑，左边再走找大与key的值填右边的坑，直到两者相遇。
思路比较简单，直接上代码解释：

int PartSort2(int* a, int left, int right)
{
	//三数取中
	int mid = GetMidIndex(a, left, right);
	//交换开头和中位数的位置
	Swap(&a[left], &a[mid]);
	
	//保存坑位的值
	int key = a[left];
	//坑位
	int hole = left;
	while (left < right)
	{
		//R先走找小
		while (left < right && a[right] >= key)
		{
			--right;
		}
		//找到小的填到左边的坑
		//因为左边坑位的值保存了
		//因此可以直接覆盖
		a[hole] = a[right];
		//此时right为新的坑
		hole = right;

		//L再走找大
		while (left < right && a[left] <= key)
		{
			++left;
		}
		//找到大的填到右边的坑
		a[hole] = a[left];
		//此时left为新的坑
		hole = left;
	}
	//相遇的位置一定是个坑
	//直接把最开始保存的值填到相遇位置的坑
	a[left] = key;
	//返回坑位
	return hole;
}

相比于hoare法，挖坑法的思路更加易于理解。
比如说hoare法中：

  1. 为什么左边为基准值时，要让右边先走？
  2. 为什么相遇位置的值一定比key小？

而挖坑法则不需要考虑，因为：

  1. 左边是坑，自然是右边先走找小值填左边的坑。
  2. 左右总会有一个是坑，两者相遇那么一定是在坑位上相遇，直接把最开始坑位的值填到相遇位置。

如此看来挖坑法的思路更具天然性。

1.3 前后指针版本

同样该方法的本质不变，主要是单趟排序的思路有点差别，也是hoare版本的改造。
在这里插入图片描述
从上图可以发现该方法的大体思路：无论怎样指针cur都再不断向前走，而指针prev只有当cur找到了比key位置小的值prev才会向前走一步，然后交换cur位置的值，当cur出了范围，prev位置为小于key的值，交换prev与key位置的值，prev位置为新的key。

具体地，指针prev有两种状态。

  1. prev紧跟着cur，
    在这里插入图片描述
    这种情况为：cur指针还没有遇到大于key的值，因此其实prev也在不断的向前走然后与cur交换，只不过prev走一步就遇到了cur，然后自己与自己交换，待会在实现的时候可以做一个判断：当cur与prev之间还没有距离的时候不交换，因为和自己交换没有意义。
  2. prev与cur有段距离
    在这里插入图片描述
    这种情况为：cur一直遇到大于key位置的值，因此prev无法向前走，所以中间就隔了段距离，而隔了的这段距离中的值都是大于key位置的值，因此当cur遇到了比key位置小的值停下来，先让prev走一步，让其指向大于key位置的值，然后在进行交换，直到cur到达末尾。

代码实现：

int PartSort3(int* a, int left, int right)
{
	//选出中间位置的数据
	int mid = GetMidIndex(a, left, right);
	//交换开头和中位数的位置
	Swap(&a[left], &a[mid]);

	int keyi = left;
	//两个指针一前一后
	int prev = left;
	int cur = prev + 1;
	//闭区间，right位置也要判断
	while (cur <= right)
	{
		//cur找到小的了，并且先让prve+1不等于cur就进行交换
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		//cur一直往前走
		++cur;
	}
	//交换key与prev位置的值
	Swap(&a[keyi], &a[prev]);
	return prev;
}

双指针法的代码实现要比前两种方法简洁很多。

1.4 希尔 堆排与快排的效率对比

直接上图：
在这里插入图片描述
很快啊
在这里插入图片描述
在这里插入图片描述
数据量在非常大的时候，快排不及希尔排序，可以说明在超大量数据下希尔的预排序效果非常显著，效率甚至要优于快排不少。

虽然堆排与快排都是O(N*logN)的排序，但是堆排为三个排序种效率最低是因为，在排序之间要进行建堆，而建堆的时间复杂度为O(N)，当N很小两者的效率差不多，而N很大，就比较影响效率了，

2. 非递归实现

既然有了快速排序的递归，那为什么还要非递归呢？

主要原因是递归不排除很小的几率会栈溢出，其次就是多掌握一种快排的实现方式。

在二叉树的层序遍历用到了非递归，但是需要借助数据结构栈来辅助实现，同样的快速排序的非递归实现也需要栈来辅助。

非递归就是模拟递归的过程，非常简单，那么如何模拟？

这就需要知道递归是如何走的，很明显是按照区间进行划分，知道它的左右区间，然后进行单趟排序，单趟排序后又会根据keyi的位置来分割左子区间和右子区间，然后分别递归继续走，然后不断分割左右区间知道区间只剩一个或两个值结束递归。

因此只需要把最开始和后面依次分割的左右子区间的起始和结束位置分别入栈，当栈不为空就一直进行单趟排序，当栈为空就完成了整个数列的排序。

代码实现：

#include "Stack.h"
void QuickSortNonR(int* a, int left, int right)
{
	Stack st;
	//初始化栈
	InintStack(&st);
	//把最开始的起始和结束位置入栈
	PushStack(&st, left);
	PushStack(&st, right);
	//当栈不为空就继续迭代
	while (!StackEmpty(&st))
	{
		//栈是后进先出
		//所以先出结束位置
		int end = StackTop(&st);
		PopStack(&st);
		//在出起始位置
		int begin = StackTop(&st);
		PopStack(&st);

		//经过一次单趟排序被keyi分割出了左右两个子区间
		int keyi = PartSort2(a, begin, end);
		//当右子区间大于两个数据就入栈
		if (keyi + 1 < end)
		{
			PushStack(&st, keyi + 1);
			PushStack(&st, end);
		}
		//同样的当左子区间大于两个数据就入栈
		if (begin < keyi - 1)
		{
			PushStack(&st, begin);
			PushStack(&st, keyi - 1); 
		}
		//通过单趟排序不断迭代两个区间的起始和结束位置就完成了整体排序
	}
}

相较于递归，非递归的优势在于：非递归消耗的是在内存中堆上申请的空间，堆相比较于栈而言大太多了，基本上就不用再考虑堆空间不够用的情况。

总结

快速排序yyds，它的三种递归和非递归的思想都要理解并可以手撕其中一种思想的代码实现。

相关文章：

  • MATLAB系统辨识工具箱-System Identification Toolbox
  • Android 10 应用层如何操作设备节点/sys/devices
  • 使用 TensorFlow.js 在浏览器中进行自定义对象检测
  • CopyOnWriteArrayList是如何保证线程安全的？
  • Synopsys新思科技2023“向新力”秋季校园招聘内推
  • 硬盘分区误删数据如何恢复呢?
  • 基于Java毕业设计智能超市导购系统源码+系统+mysql+lw文档+部署软件
  • python数据分析—删除value=0的行
  • 计算机毕业设计Java物流信息管理系统（源码+系统+mysql数据库+Lw文档）
  • [CSS]CSS 的背景
  • 大数据ClickHouse进阶（六）：Distributed引擎深入了解
  • PyTorch、TensorFlow和Jax构建神经网络模型的标准化流程
  • 【最详细demo】雪花算法详细解释
  • 基于JavaSwing开发扫雷小游戏（不同版本） 课程设计 大作业
  • 【云原生 | Kubernetes 系列】---Ceph集群安装部署
  • IE9 : DOM Exception: INVALID_CHARACTER_ERR (5)
  • 「面试题」如何实现一个圣杯布局？
  • 〔开发系列〕一次关于小程序开发的深度总结
  • IIS 10 PHP CGI 设置 PHP_INI_SCAN_DIR
  • leetcode388. Longest Absolute File Path
  • Next.js之基础概念（二）
  • node学习系列之简单文件上传
  • Redash本地开发环境搭建
  • Spring框架之我见（三）——IOC、AOP
  • uni-app项目数字滚动
  • 工作踩坑系列——https访问遇到“已阻止载入混合活动内容”
  • 好的网址，关于.net 4.0 ,vs 2010
  • 基于Dubbo+ZooKeeper的分布式服务的实现
  • 入门到放弃node系列之Hello Word篇
  • 使用前端开发工具包WijmoJS - 创建自定义DropDownTree控件（包含源代码）
  • 想使用 MongoDB ，你应该了解这8个方面！
  • 小程序开发中的那些坑
  • 一加3T解锁OEM、刷入TWRP、第三方ROM以及ROOT
  • elasticsearch-head插件安装
  • LevelDB 入门 —— 全面了解 LevelDB 的功能特性
  • ​Distil-Whisper：比Whisper快6倍，体积小50%的语音识别模型
  • ​无人机石油管道巡检方案新亮点：灵活准确又高效
  • #Linux（帮助手册）
  • #WEB前端（HTML属性）
  • （02）vite环境变量配置
  • (pojstep1.1.2)2654(直叙式模拟)
  • （PWM呼吸灯）合泰开发板HT66F2390-----点灯大师
  • （八）Spring源码解析：Spring MVC
  • （超简单）构建高可用网络应用：使用Nginx进行负载均衡与健康检查
  • （二）换源+apt-get基础配置+搜狗拼音
  • （附源码）ssm失物招领系统 毕业设计 182317
  • (五)IO流之ByteArrayInput/OutputStream
  • （转）PlayerPrefs在Windows下存到哪里去了？
  • (转)菜鸟学数据库（三）——存储过程
  • .gitignore文件---让git自动忽略指定文件
  • .NET Framework .NET Core与 .NET 的区别
  • .NET 事件模型教程（二）
  • .NET 中 GetHashCode 的哈希值有多大概率会相同（哈希碰撞）
  • .NET/C# 的字符串暂存池
  • .NET/C# 异常处理：写一个空的 try 块代码，而把重要代码写到 finally 中（Constrained Execution Regions）