​​快速排序(四)——挖坑法,前后指针法与非递归

这篇具有很好参考价值的文章主要介绍了​​快速排序(四)——挖坑法,前后指针法与非递归。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

目录

​一.前言

二.挖坑法

三.前后指针法

四.递归优化

五.非递归

六.结语


 

一.前言

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

码字不易,希望大家多多支持我呀!(三连+关注,你是我滴神!)

二.挖坑法

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

其实挖坑法很简单,因为它只是在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的核心,这样才能写出优化的挖坑法。

三.前后指针法

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

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

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

而prev只有两者情况:

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

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

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

3与7交换 

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

9与4交换

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

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

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

写代码我们要注意一个地方,就是记得要在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;


}

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

四.递归优化

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

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

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

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

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

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

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

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

代码部分: 

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);
	}
}

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言 

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

五.非递归

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

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

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

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

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

再把左区间0-4录入

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

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

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

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

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

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

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言 我们可以发现这就是递归的过程,只不过我们需要用栈以非递归的形式实现

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

​​快速排序(四)——挖坑法,前后指针法与非递归,数据结构,排序算法,算法,数据结构,c语言

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

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;
}

六.结语

本文整体上是对快排进行的优化,让它的性能更加强大,另外也帮助我们在掌握好递归的同时也能运用好非递归。最后感谢大家的观看,友友们能够学习到新的知识是额滴荣幸,期待我们下次相见~文章来源地址https://www.toymoban.com/news/detail-819802.html

到了这里,关于​​快速排序(四)——挖坑法,前后指针法与非递归的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • c语言快速排序(霍尔法、挖坑法、双指针法)图文详解

      快速排序是一种非常常用的排序方法,它在1962由C. A. R. Hoare(霍尔)提的一种二叉树结构的交换排序方法,故因此它又被称为 霍尔划分 ,它基于分治的思想,所以整体思路是递归进行的。 1.先选取一个key,关于key值的选取,一般是选数组第一个元素,数组中间元素,数组

    2024年02月02日
    浏览(35)
  • [C/C++]排序算法 快速排序 (递归与非递归)

    目录 🚩概念: 🚩实现: ⚡1.hoare ⚡2.挖坑法 ⚡3.双指针法 🚩快速排序递归实现 🚩快速排序非递归实现           通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据要小,再按这种方法对这两部分数据分别进行快速排序,整

    2024年02月03日
    浏览(45)
  • 快速排序详解(递归实现与非递归实现)

    目录 一、快速排序的基本思想 二、将序列划分成左右区间的常见方法 2.1hoare版本(动图+解释+代码实现) 2.2挖坑法 2.3前后指针法 三、快速排序的初步实现 四、快速排序的优化实现 4.1快排的特殊情况 4.2对区间划分代码的优化 4.3小区间优化 五、快速排序的非递归实现 六、总

    2024年02月07日
    浏览(38)
  • 数据结构进阶篇 之 【并归排序】(递归与非递归实现)详细讲解

    都说贪小便宜吃大亏,但吃亏是福,那不就是贪小便宜吃大福了吗 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀– 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序

    2024年04月09日
    浏览(49)
  • 【五一创作】排序篇:冒泡排序,快速排序的递归与非递归实现(C语言)

    目录 前言: 一:冒泡排序 基础思路 完整排序 时间复杂度分析 二:递归实现快速排序 基础思路 单趟排序 (1)双向扫描法 (2)挖坑法 (3)前后指针法(推荐这种) 完整排序 时间复杂度分析 优化 (1)三数取中 (2)小区间优化(递归的完整代码在这里!!!) 三:非递归实现快速排序 基础

    2024年02月04日
    浏览(39)
  • 全网最全的快速排序方法--Hoare快排 挖坑法快排 二路快排 三路快排 非递归快排

    目录 一.快速排序 1.基本介绍 2.基本思想 二.Hoare快排 0.前情知识 1.交换数组中的两个元素 2.指定范围的插入排序 1.基本思路 2.代码实现 3.优化思路 三.挖坑法快排(校招中适用) 1.基本思路 2.代码实现 四.二路快排 1.基本思路 2.代码实现 3.优化思路 五.三路快排 1.基本思路 2.代码

    2023年04月21日
    浏览(44)
  • 数据结构进阶篇 之 【交换排序】(冒泡排序,快速排序递归、非递归实现)详细讲解

    当你觉的自己不行时,你就走到斑马线上,这样你就会成为一个行人 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 冒泡排序的特性总结 2.1 基本思想 2.2 递归实现 2.2.1 hoare版 2.2.2 前后指针版本 2.3 快速排序优化 2.3.1 随机数选key 2.3.2 三数取中选key 2.3.3 递归到小的子区间使用插入排

    2024年04月10日
    浏览(68)
  • 【数据结构】非递归实现快速排序与归并排序

    递归是可以向非递归进行变化的: 比如很经典的 斐波那契数列 可以用 递归 实现也可以用 循环 实现 但是有些复杂的递归仅仅依靠循环是很难控制的, 所以我们需要借助数据结构中的 栈与队列 帮助我们用非递归模拟递归, 故有的时候我们说非递归不是递归却胜似递归 通过

    2024年01月21日
    浏览(51)
  • 【数据结构与算法】:非递归实现快速排序、归并排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序,本篇我们来探究非递归实现快速排序和归并排序 快速排序的非递归实现主要依赖于栈(stack)来模拟递归过程中的函数调用栈。递归版本的快速排序通过递归调用自身来处理子

    2024年03月24日
    浏览(55)
  • 【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?

    君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C++ 游戏开发 Hello,米娜桑们,这里是君兮_,国庆长假结束了,无论是工作还是学习都该回到正轨上来了,从今天开始恢复正常的更新频率,今天为大家带来的内容是快速排序的两大优化和非递归实现 好了废话不多说,开

    2024年02月08日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包