​​快速排序（四）——挖坑法，前后指针法与非递归

fe594ea5bf754ddbb223a54d8fb1e7bc.gif

目录

​一.前言

二.挖坑法

三.前后指针法

四.递归优化

五.非递归

六.结语

 

8fb442646f144d8daecdd2b61ec78ecd.png一.前言

本文我们接着上篇文章的重点快排，现在继续讲解对快排优化的挖坑法，前后指针法以及非递归方法，下面是上篇文章快排链接：https://mp.csdn.net/mp_blog/creation/editor/135719674。

码字不易，希望大家多多支持我呀！（三连＋关注，你是我滴神！）

二.挖坑法

其实挖坑法很简单，因为它只是在hoare的基础上优化了一部分，就比如不用去纠结为什么key在右边时，右边先走。这里因为坑设定在第一位，所以自然要从右边找数去填坑。

因此这里面的循环逻辑就变得很简单，右找小（填左边坑），自己变成新坑，左找大（填右边坑），自己变新坑，就这样以此类推最后一定会相遇，而这个相遇的位置一般就是我们的居中值（三数取中法），最后把key放入即可。

int PartSort2(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);
	//通过三数取中把位于最左边的居中数给key
	int key = a[left];
	//保存key值后，左边形成第一个坑位
	int hotel = left;
	//left与right不断相遇
	while (left < right)
	{
		//右边先走，找小；找到后把值放到左边坑位中，右边形成新的坑位
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hotel] = a[right];
		hotel = right;
		//左边开始走，找大；找到后把值放到右边坑位中，左边形成新的坑位
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hotel] = a[left];
		hotel = left;
	}
	//最后二者相遇，并且其中一个必定是坑位
	//将key放入坑位中
	a[hotel] = key;
	return hotel;


}

挖坑法由于有了前面hoare的铺垫，所以我们可以更简洁明了地写出代码，也更通俗易懂，但这些前提都是要理解hoare的核心，这样才能写出优化的挖坑法。

三.前后指针法

前后指针法写起来甚至比挖坑法更简单，因为它就只有一个核心点：

cur找比key小的数，prev++，交换prev与cur的值

而prev只有两者情况：

  1. 在cur没遇到比key大的值的时候，prev紧紧跟着cur（重合）
  2. 在cur遇到比key大的值的时候，prev在比key大的一组值的前面

这样就会出现一种情况，比key大的值会阻扰prev的前进，但只要cur再次找到比key小的值两者就会交换，prev就像是不断地推着比key大的值往后排。

3与7交换 

9与4交换

就这样持续到cur走出数组，这时可以看到prev的指向数是比key小的，最后prev与key进行交换。

写代码我们要注意一个地方，就是记得要在cur找小的时候添加一个条件，如果该趟找不到小的已经越界了就及时退出，否则prev就会继续++，打乱了key的正确位置。

int PartSort3(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);
	int key = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		//找小
		while (cur<=right&&a[cur] >= a[key])
		{
			cur++;
		}
		//当找不到小时
		if (cur > right)
		{
			break;
		}
		else
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
	}
	Swap(&a[key], &a[prev]);
	return key;


}

还有一种写法，我们可以观察到cur无论是找小还是找不到小都会++，那不妨可以这样写：

int PartSort3(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);
	int key = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[key], &a[prev]);
	return key;


}

注意！这两个优化的方法并不能提高快排的算法效率，只是思想上的优化，便于我们更好理解而已。

四.递归优化

我们再来处理优化递归的问题：

满二叉树最后一层节点会占总节点的50%，因为一共有2^h-1个节点，最后一层有2^(h-1)个

对比到快排的递归而言，为了让这10个数有序而走了那么多次递归有点不划算。

那如果10个数我们不用递归而采用直接插入法的话可以效率可以提高80%-90%，因为递归最后三层的消耗占据很多，在处理数量级小的情况下会很浪费。

代码部分： 

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if ((end - begin + 1) > 10)
	{
		int key = PartSort3(a, begin, end);
		QuickSort(a, begin, key - 1);
		QuickSort(a, key+1, end);

	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

 

这是最精妙的一步（小区间优化，小区间不再递归分割排序，降低递归次数），由于我们在不断递归的过程中那些后面被分割的许多个小组序列会占据大多数空间，所以我们统一划定一个标准，只要是小于10个的范围都直接插入法去解决，又因为我们划分的无数个子树都对应原数组不同的位置，那我们就分别用[begin,end]来规定它们，当我们用到直接插入排序时，只要在原数组地址加上begin就可以对应到自己的位置。

五.非递归

非递归的关键就是能够控制与保存区间——借助栈

我们先把数组的范围录入栈中

找到key的下标后把0-9取出，录入我们的右区间6-9 

再把左区间0-4录入

之所以先入右再入左是因为这样可以先把左区间给取出来（栈的特点），然后下一次循环栈不为空则取出左区间走，0-4走完单趟选出key后继续分割

0-4分割成0-1与3-4，我们再把它们分别录入栈中。 

再把0-1取出来选出key为1后分割成0-0与2-1（2-1说明这里已经没有数了，也可以参考范围[key+1,end]，）而这两个区间也不用继续入栈了（没啥好分的了）。

 我们可以发现这就是递归的过程，只不过我们需要用栈以非递归的形式实现

接着我们取出3-4进行分割，然后按照区间规则它分出的两区间不用再入栈了。

就这样以此类推直到栈为空结束。

void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	STInit(&st);
	//入栈，先入右，如9
	STPush(&st, end);
	//再入左，如0
	STPush(&st, begin);
	while (!STEmpty(&st))
	{
		//准备出栈,获取栈顶元素，如0
		int left = STTop(&st);
		//出栈，如0
		STPop(&st);
		//准备出栈,获取栈顶元素，如9
		int right = STTop(&st);
		//出栈，如9
		STPop(&st);
		//通过获取的元素构成范围来寻找key，【0-9】
		int key = PartSort3(a, left, right);
		//[left,key-1]key[key+1,right]
		//对范围如【0-9】进行分割，先入栈右区间再入栈左区间
        //准备入6-9
		//判断区间合理性，等于或大于不能放
		if (key + 1 < right)
		{
			STPush(&st, right);//如入9
			STPush(&st, key+1);//如入6
		}//6-9已经录入
		//同理把0-5录入
		if (left < key - 1)
		{
			STPush(&st, key-1);//如入5
			STPush(&st, left);//如入0
		}
        //现在第一层结束后栈顶由上到下就是0 5  6 9
		//至此由第一层分割的范围录入结束，后面就是判断栈里是否为空（还有没有范围）
		//如果栈不为空则继续执行这个循环，直到为空的时候，非递归也就完成了。

	}
}

 栈相关代码：对于栈功能还不熟悉的友友也可以移步我的这篇文章学习一下：https://mp.csdn.net/mp_blog/creation/editor/133249808

#include "Stack.h"

void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	// 11:40
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);

	// 
	assert(ps->top > 0);

	--ps->top;
}

STDataType STTop(ST* ps)
{
	assert(ps);

	// 
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

4b12323f94834afd9ec146a3c10df229.jpeg六.结语

本文整体上是对快排进行的优化，让它的性能更加强大，另外也帮助我们在掌握好递归的同时也能运用好非递归。最后感谢大家的观看，友友们能够学习到新的知识是额滴荣幸，期待我们下次相见~

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

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

相关文章

小程序系列--9.生命周期

小程序系列--9.生命周期

1. 什么是生命周期&#xff1f; 2. 生命周期的分类 3. 什么是生命周期函数 4. 生命周期函数的分类 5. 应用的生命周期函数 6. 页面的生命周期函数
阅读更多...
Android反编译第一神器JADX，超40k star

Android反编译第一神器JADX，超40k star

Android反编译第一神器JADX&#xff0c;超40k star 引言 jadx是一个非常强大的工具&#xff0c;可以将Android应用程序反编译为可读的Java代码。它可以帮助开发人员和安全专家分析应用程序&#xff0c;并了解其中的工作原理和实现细节。 jadx主要包含2款工具jadx及jadx-gui&a…
阅读更多...
spring-framework6.x版本源码构建

spring-framework6.x版本源码构建

6.x.修改gradle仓库构建 IDEA版本及gradle构建设置 在gradle指定仓库地址/wrapper/dists/找到与gradle wrapper相对应的gradle版本&#xff0c;在gradle的init.d/目录下新建init.gradle文件&#xff0c;内容如下&#xff1a; allprojects{repositories {mavenLocal()maven { …
阅读更多...
Pytorch自动求导机制

Pytorch自动求导机制

PyTorch框架可以帮我们计算好反向传播&#xff0c;需要求导的&#xff0c;可以手动定义 示例&#xff1a; #先构造一个随机的三行四列矩阵&#xff0c;两种方法都可以#方法1 x torch.randn(3,4,requires_gradTrue) x#方法2 x torch.randn(3,4) x.requires_gradTrue x #再构…
阅读更多...
数据的存储

数据的存储

目录 1 -> 数据类型的介绍 1.1 -> 类型的基本归类 2 -> 整型在内存中的存储 2.1 -> 原码、反码、补码 2.2 -> 大小端介绍 3 -> 浮点型在内存中的存储 3.1 -> 浮点数存储规则 1 -> 数据类型的介绍 基本内置类型有&#xff1a; char /…
阅读更多...
函数默认参数：更优雅的函数设计与调用技巧

函数默认参数：更优雅的函数设计与调用技巧

C中一个强大而优雅的特性——函数默认参数。它为我们提供了更灵活、简洁的函数设计与调用方式&#xff0c;让我们一起揭开这个令人惊叹的编程技巧的神秘面纱吧&#xff01; 1. 默认参数是什么&#xff1f; 首先&#xff0c;让我们了解一下什么是默认参数。在C中&#xff0c;函…
阅读更多...
【JAVA】我和我的第一个“对象”相遇

【JAVA】我和我的第一个“对象”相遇

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-zAjv1fTLGQmnqncy {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…
阅读更多...
开源图床LightPicture搭建本地图片管理系统并实现无公网IP远程访问

开源图床LightPicture搭建本地图片管理系统并实现无公网IP远程访问

文章目录 1.前言2. Lightpicture网站搭建2.1. Lightpicture下载和安装2.2. Lightpicture网页测试2.3.cpolar的安装和注册 3.本地网页发布3.1.Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 1.前言 现在的手机越来越先进&#xff0c;功能也越来越多&#xff0c;而手机…
阅读更多...
Redis常见类型及常用命令

Redis常见类型及常用命令

目录 常见的数据类型 一、String类型 1、简介 2、常用命令 &#xff08;1&#xff09;新建key &#xff08;2&#xff09;设值取值 ​编辑 &#xff08;3&#xff09;批量操作 &#xff08;4&#xff09;递增递减 3、原子性操作 4、数据结构 二、list类型 1、list常…
阅读更多...
【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记

【深蓝学院】移动机器人运动规划--第2章 基于搜索的路径规划--笔记

0. Outline 1. Graph Search Basis Configuration Space等概念 机器人配置: 指机器人位置和所有点的表示。 DOF: 指用于表示机器人配置所需的最小的实数坐标的数量n。 C-space: 包含机器人n维所有配置的空间。 在C-space中机器人的pose是一个点。 机器人在C-space中被表示为一…
阅读更多...
[MySQL]关于表的增删改查

[MySQL]关于表的增删改查

目录 1.插入 1.1单行数据全列插入 1.2多行插入&#xff0c;指定列插入 ​编辑2.查询 2.1全列查询 2.2指定列查询 3.3查询字段为表达式 2.4别名 ​编辑2.5去重 2.6排序 2.7条件查询 2.7.1基本查询: 2.7.2 AND 和OR 2.7.3范围查询 2.7.4模糊查询 2.7.5分页查询 limit …
阅读更多...
谈谈对测试技术的一些看法~

谈谈对测试技术的一些看法~

最近没前面那样一天更几篇文章了&#xff0c;挺丧的&#xff0c; 可能是之前弦绷的有点紧&#xff0c;现在有点受不了了。 所以突然就泄了气&#xff0c;每天忙完工作的事后就躺在家里打游戏。其实感觉每年都有一段时间是这样丧的。所以我自己其实并不是特别努力的类型&#xf…
阅读更多...
STM32入门教程-2023版【4-2】OLED显示屏简介

STM32入门教程-2023版【4-2】OLED显示屏简介

关注 点赞 不错过精彩内容 大家好&#xff0c;我是硬核王同学&#xff0c;最近在做免费的嵌入式知识分享&#xff0c;帮助对嵌入式感兴趣的同学学习嵌入式、做项目、找工作! 本小结学习一下如何使用OLED显示屏的函数驱动模块 一、OLED显示屏简介 &#xff08;1&#xff09;…
阅读更多...
汽车网络架构与常用总线汇总

汽车网络架构与常用总线汇总

汽车CAN总线简述 CAN 是控制器局域网Controller Area Network 的缩写&#xff0c;1986年&#xff0c;由德国Bosch公司为汽车开发的网络技术&#xff0c;主要用于汽车的监测与控制&#xff0c;目的为适应汽车“减少线束的数量”“通过多个网络进行大量数据的高速传输”的需求。…
阅读更多...
栈--顺序栈的基本操作（对小白友好）

栈--顺序栈的基本操作（对小白友好）

文章目录 栈的基本操作栈的定义栈的初始化栈的判空进栈出栈读取栈顶元素销毁栈全部源码 栈的基本操作 以下代码中,默认初始化的top为-1。 栈的定义 #define MaxSize 50 //定义栈中元素最大个数typedef struct {int data[MaxSize]; //存放栈中元素int top; //栈顶指针…
阅读更多...
Linux基本常用命令大全（二）

Linux基本常用命令大全（二）

五、查找命令 5.1 grep grep命令是一种强大的文本搜索工具 使用实例&#xff1a; ps -ef | grep sshd 查找指定ssh服务进程 ps -ef | grep sshd | grep -v grep 查找指定服务进程&#xff0c;排除gerp身 ps -ef | grep sshd -c 查找指定进程个数 5.2 find find命令在目录…
阅读更多...
IOS-生命周期-Swift

IOS-生命周期-Swift

目录 App生命周期应用状态未运行——Not running未激活——Inactive激活——Active后台——Backgroud挂起——Suspended 关系图生命周期方法相关方法注意在其他地方监听 ViewController生命周期UIView生命周期 App生命周期 应用状态 App主要有五种状态&#xff0c;分别是&…
阅读更多...
从CNN ,LSTM 到Transformer的综述

从CNN ,LSTM 到Transformer的综述

前情提要&#xff1a;文本大量参照了以下的博客&#xff0c;本文创作的初衷是为了分享博主自己的学习和理解。对于刚开始接触NLP的同学来说&#xff0c;可以结合唐宇迪老师的B站视频【【NLP精华版教程】强推&#xff01;不愧是的最完整的NLP教程和学习路线图从原理构成开始学&a…
阅读更多...
【C++杂货铺】三分钟彻底搞懂函数重载

【C++杂货铺】三分钟彻底搞懂函数重载

目录 &#x1f308;前言 &#x1f4c1; 缺省参数 &#x1f4c2;概念 &#x1f4c2;分类 &#x1f4c2; 注意事项 &#x1f4c1; 函数重载 &#x1f4c2;概念 &#x1f4c2;实现原理 &#x1f4c1; 总结 &#x1f308;前言 欢迎收看本期【C杂货铺】&#xff0c;这期内容…
阅读更多...
[亲测有效]CentOS7下安装mysql5.7

[亲测有效]CentOS7下安装mysql5.7

前言 近期项目需要搭配mysql一起存储相关数据&#xff0c;但对mysql的版本有要求&#xff0c;于是在服务器搭建了mysql5.7&#xff0c;顺便记录一下搭建步骤和踩坑解决步骤。 目录 前言 一、清除旧安装包 二、安装YUM 三、使用yum命令即可完成安装 四、重新设置密码 五、…
阅读更多...
最新文章

Copyright @ 2022~2023