快排(非递归)及计数排序算法

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

都学了递归版的快速排序为何还要再学非递归实现?由于在递归过程中,如果数据量过大,那么实现时容易导致栈溢出,虽然代码没有问题,但是就是会崩,因此要将其改为非递归来实现


一、快速排序(非递归)

如何做到将递归算法改为非递归算法?

简单的递归可以直接将其改为循环(如斐波那契),但是如果是复杂的递归算法,再直接改为循环十分复杂,而一般选用栈辅助将其改为非递归

再来回顾一下快速排序的思想。

思想:在区间范围内选出一个关键字,经过单趟排序之后关键字位置左边的数据全小于或者等于它,关键字右边的数据全大于或者等于它。一趟排序将这个关键字排好了,同样也分隔出了它的左区间和右区间,再以同样的方法排它的左区间和右区间,直至区间范围为1或者不存在为止

而递归实现快速排序是每次控制的是区间,每次递归调用栈都是将区间压栈,每递归一次,区间都在变化。因此用栈实现快速排序时,入栈的是区间,而由于每次递归都是先排的左区间,而栈是一种后进先出的数据结构,所以在将区间入栈时要先将右区间压栈,然后再将左区间压栈,保证每次单趟排先将左区间排好再排右区间
快排(非递归)及计数排序算法

单趟排。排出keyi此时分隔出keyi的左右区间,然后把他的左、右区间压栈,此时又对它的左右区间进行单趟排,排出keyi,分隔左右区间,每次单趟排完后会分隔出左右区间,然后左右区间入栈,直至最后区间为1或者不存在时,就不用再入栈了。总体是:

  1. 从栈中取一段区间,进行单趟排。
  2. 单趟排序后分隔子区间(左、右区间)入栈。
  3. 子区间只有一个值或者不存在就不入栈了
    快排(非递归)及计数排序算法

每一次单趟排是如何排的,这里用前后指针法实现,每次单趟排好后,返回关键字所在下标

那么用栈辅助改递归,这个栈从和而来,我这里是以前写好了,保存下来的,在vs中只需要选中源文件
快排(非递归)及计数排序算法
然后点击鼠标右键找到
快排(非递归)及计数排序算法
找到以前保存栈实现的文件,将其拷贝
之后再点击源文件
快排(非递归)及计数排序算法
再点击快排(非递归)及计数排序算法

快排(非递归)及计数排序算法
以前是新建但是现在是点击现有,然后找到当前程序所在目录,将刚才拷贝的栈实现的文件拷贝到当前程序中即可。

前后指针法排单趟

//前后指针法
int QuickSort3(int* a, int left, int right)
{
	
	int begin = left;
	int end = right;
	

	//随机选数,主要针对已经有序的情况,提高性能
	int randi = left + (rand() % (right - left));
	if (randi != left)
	{
		Swap(&a[randi], &a[left]);
	}

	int key = left;
	int cur = left + 1;
	int prev = left;

	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}

	Swap(&a[key], &a[prev]);
	key = prev;
	return key;
	
}

//取区间入栈然后对其单趟排,单趟排好keyi之后分割出它的子区间,将分割出的子区间入栈,再进行单趟排,再分割子区间入栈,每次单趟排排好一个数,直至区间范围为一或者不存在
//
void QuicksortNone(int* a, int begin, int end)
{
	St st;
	STInit(&st);
	STPush(&st, end);
	STPush(&st, begin);

	while (!STEmpty(&st))
	{
		int begin1 = STTop(&st);
		STPop(&st);
		int end1 = STTop(&st);
		STPop(&st);
		int keyi = QuickSort3(a, begin1, end1);

		if (keyi + 1 < end1)
		{
			STPush(&st, end1);
			STPush(&st, keyi+1);
		}

		if (keyi > begin1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin1);
		}
	}
	STDestroy(&st);
}

快排(非递归)及计数排序算法
非递归快速排序时间复杂度O(nlogn),空间复杂度o(1)

二、计数排序

适用于数组存在大量重复数据且最大值和最小值之差不是特别大的情况
思想:统计数组中每个数据出现的次数,怎么统计?用一个新数组存储原数组数据出现的次数 。 这个数组如何来?当然是向内存动态申请开辟
新数组开辟多大空间合适?
由于存的是原数组数据出现次数,那么只需要数组数据值出现一次,那么它对应值作为下标的值就加一(开辟的数组内容全部初始化为0)
只要数组中的值出现一次,那么它对应的值作为新数组下标所对应的值就加一,那么新数组范围如何确定?
其实也就是原数组最大值与最小值之差,由于用原数组值作为下标 所以先遍历一遍找出数组中的最大值和最小值,这时确定新数组开辟大小
快排(非递归)及计数排序算法

由于存储从0开始,所以需要原数组值减去它的最小值 最后将新开辟数组的下标再加上原数组最小值就可以直接覆盖原数组,如何覆盖的?
快排(非递归)及计数排序算法

void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}

		if (a[i] < min)
		{
			min = a[i];
		}
	}

	int range = max - min + 1;//要包含0,所以这个存储数组大小要开最大值和最小值之差再加一

	//开一个数组用来统计数组数据出现的次数
	int* countA = (int*)malloc(sizeof(int) * range);
	if (countA == NULL)
	{
		perror("ocuntA fail\n");
		return;
	}
	//将新开的这个数组内容全部都初始化为0
	//由于它存储的内容是原数组数据出现的次数
	memset(countA, 0, sizeof(int) * range);//c语言内置库函数将每个字节都初始化为0

	//以原数组中的数据作为新开数组的下标,然后统计它出现的次数
	//由于原数组最小值很可能不是从0开始
	//而新数组要从0开始存储
	//所以新数组下标是a[i] - min这个表达式
	for (int i = 0; i < n; i++)
	{
		//将原数组内容它对应的数字为countA下标加加,即数组对应数据在数组中出现的次数
		countA[a[i]-min]++;
	}

	int j = 0;
	for (int i = 0; i < n; )//i<n后面的调整不可再加,原因是下面加了,如果再加会造成越界
	{
		//可以在这里做出调整,将其i--,但是这里多此一举
		while (countA[j]--)
		{
			a[i++] = j + min;
		}
		j++;
	}

	free(countA);
}

快排(非递归)及计数排序算法


计数排序时间复杂度为O(n+range)当range<n时,时间复杂度为O(n),空间复杂度为O(range),但是它的条件十分苛刻,需要很多重复数据且这些数据最大值和最小值之差不可过大,所以在现实生活中很少用到,但是在有些场景下会用到,所以还是值得一学,毕竟时间复杂度为线性的嘛。文章来源地址https://www.toymoban.com/news/detail-416386.html

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

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

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

相关文章

  • 全网最全的快速排序方法--Hoare快排 挖坑法快排 二路快排 三路快排 非递归快排

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

    2023年04月21日
    浏览(41)
  • 十大排序算法(冒泡排序、插入排序、选择排序、希尔排序、堆排序、快排、归并排序、桶排序、计数排序、基数排序)

    目录 一、冒泡排序: 二、插入排序: 三、选择排序: 四、希尔排序: 五、堆排序: 六、快速排序: 6.1挖坑法: 6.2左右指针法 6.3前后指针法: 七、归并排序: 八、桶排序: 九、计数排序: 9.1绝对映射: 9.2现对映射: 十、基数排序:  1、思路: 通过对待排序序列从前

    2024年03月11日
    浏览(54)
  • “掌握更多的快速排序技巧:三路划分、双路快排和非递归的深入理解”

    快速排序是一种基于分治思想的排序算法,它能够以极快的速度将一个乱序的数组重新排列成有序的序列。不仅如此,快速排序还具有简洁的实现代码和良好的可扩展性,成为最受欢迎的排序算法之一。接下来,让我带你了解一下它的魅力吧!💫 快速排序是Hoare于1962年提出

    2024年02月16日
    浏览(39)
  • 【数据结构与算法篇】手撕八大排序算法之快排的非递归实现及递归版本优化(三路划分)

    ​👻内容专栏: 《数据结构与算法篇》 🐨本文概括: 利用数据结构栈(Stack)来模拟递归,实现快排的非递归版本;递归版本测试OJ题时,有大量重复元素样例不能通过,导致性能下降,优化快速排序通过将数组划分为三个区域,可以更有效地处理重复元素。 🐼本文作者:

    2024年02月11日
    浏览(81)
  • 【排序算法】 快速排序(快排)!图解+实现详解!

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 算法—排序篇 🌄 莫道桑榆晚,为霞尚满天! 什么是快排?快排的速度到底有多快呢?它们的思想和实现是什么样的? 本文会对这快速排序进行详解,绝对细致入微!让你彻底搞懂快排! 英国计算机科学家Tony Hoare在1960年为了解决计算

    2024年02月05日
    浏览(38)
  • 算法:分治思想处理快排递归以及快速选择/最小K个数问题

    分治的原理就是分而治之,从原理上讲,就是把一个复杂的问题划分成子问题,再将子问题继续划分,直到可以解决 基于分治的原理进行快速排序,区别于传统的快速排序,这里对快速排序进行改良,成为更优先的三路划分算法,可以处理一些极端场景,使快速排序的适用性

    2024年02月10日
    浏览(52)
  • 八大排序算法之快速排序(上篇)(未经优化的快排)

    目录 一.关于快速排序的总体算法思想 1.冒泡排序(交换排序) (以排升序为例) 2.快速排序的总体思想简介(以排升序为例)  二.快速排序单趟排序的算法接口设计(以排升序为例) 单趟排序实现的方法一:hoare版本(左右指针法) 代码实现:  单趟排序实现的方法二:挖坑法  代码实现

    2023年04月08日
    浏览(38)
  • 图解快排——快速排序算法(quick sort)

    算法思想 快速排序算法是对冒泡排序算法的一种改进算法,在当前所有内部排序算法中,快速排序算法被认为是最好的排序算法之一。 快速排序的基本思想: 通过一趟排序将待排序的序列分割为左右两个子序列,左边的子序列中所有数据都比右边子序列中的数据小,然后对

    2024年01月16日
    浏览(36)
  • 【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 算法—排序篇 🌄 莫道桑榆晚,为霞尚满天! 什么是快排?快排的速度到底有多快呢?它们的思想和实现是什么样的? 本文会对这快速排序进行详解,绝对细致入微!让你彻底搞懂快排! 英国计算机科学家Tony Hoare在1960年为了解决计算

    2024年02月05日
    浏览(51)
  • 排序 | 冒泡插入希尔选择堆快排归并计数排序

    排序算法是一种将一组数据按照特定顺序排列的算法。数据结构排序算法的选择取决于数据的特征、规模和性能需求。 接下来我们就要实现排序~~ 我们需要实现的一些功能: 冒泡排序是一种基本的排序算法,其核心思想是通过多次交换相邻元素的位置,使得每一轮循环都将

    2024年02月04日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包