排序算法:快速排序(非递归)

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

!](https://img-blog.csdnimg.cn/direct/870dd101173d4522862e4459b32237a3.png)
排序算法:快速排序(非递归),排序算法,排序算法,算法
先赞后看,养成习惯!!!^ _ ^<3 ❤️ ❤️ ❤️
码字不易,大家的支持就是我坚持下去的动力。点赞后不要忘了关注我哦!
所属专栏:排序算法

思路如下:

一、先建立一个栈

为什么要建立栈呢?
建立栈是为了让每次排序的区间进去,然后后面便于取出

排序算法:快速排序(非递归),排序算法,排序算法,算法

二、代码编写

这里用了之前的快速排序的一个格式(前后指针法)
注意事项
1.每次判断key-1和key+1是否符合要求(keyi-1>left ,keyi+1<right)这样才能入栈
2.前后指针法排序时必须记住当cur走到right的时候,prev所在的位置一定小于或者等于key,此时出了循环一定要和left位置的值交换,这样可以使得key的位置已经排好了

void Swap(int* p1, int* p2)
{
	int tmp = *p2;
	*p2 = *p1;
	*p1 = tmp;
}

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


void TestQuickSort(int begin,int end,int* a)
{
	ST stack;
	StackInit(&stack);
	StackPush(&stack, end);
	StackPush(&stack, begin);
	while (!StackEmpty(&stack))
	{
		int left = StackTop(&stack);
		StackPop(&stack);
		int right = StackTop(&stack);
		StackPop(&stack);

		int keyi = QuickSort(left, right, a);

		if (keyi + 1 < right)
		{
			StackPush(&stack, right);
			StackPush(&stack, keyi + 1);
		}
		if (keyi - 1 > left)
		{
			StackPush(&stack, keyi - 1);
			StackPush(&stack, left);
		}
	}


	StackDestroy(&stack);


}

int main()
{
	int a[10] = { 3,5,6,7,2,1,8,10,9,4 };
	TestQuickSort(0,9,a);
	for (int i = 0; i < 10; i++)
		printf("%d ",a[i]);
	return 0;
}

排序算法:快速排序(非递归),排序算法,排序算法,算法文章来源地址https://www.toymoban.com/news/detail-843545.html

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

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

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

相关文章

  • 排序算法-----快速排序(非递归实现)

    目录 前言 快速排序  基本思路  非递归代码实现 算法分析 空间复杂度 时间复杂度 稳定性         很久没跟新数据结构与算法这一栏了,因为数据结构与算法基本上都发布完了,哈哈,那今天我就把前面排序算法那一块的快速排序完善一下,前面只发布了快速排序递归算法

    2024年01月21日
    浏览(7)
  • 十大排序算法(中):冒泡排序,快速排序(递归和非递归)、归并排序(递归和非递归)

    这篇文章,我们接着来讲剩下的排序算法:冒泡排序,快速排序(递归和非递归)、归并排序(递归和非递归) 中心思想: 交换就是指根据序列中的两个元素的比较结果来对换这两个元素在序列中的位置,特点就是:将值较大的元素向序列尾部移动,将值较小的元素向序列

    2024年02月05日
    浏览(21)
  • 排序算法之六:快速排序(非递归)

    快速排序是非常适合使用递归的,但是同时我们也要掌握非递归的算法 因为操作系统的栈空间很小,如果递归的深度太深,容易造成栈溢出 递归改非递归一般有两种改法: 改循环 借助栈(数据结构)   不是递归,我们模拟递归的过程 创建一个栈s,先入end,再入begin,先出

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

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

    2024年02月03日
    浏览(11)
  • 快速排序算法的递归和非递归

    基本思路 选择一个基准值,将数组划分三个区域,小于基准值的区域位于左侧,等于基准值的区域位于中间,大于基准值的区域位于右侧。将大于和小于区域继续进行分区,周而复始,不断进行分区和交换,直到排序完成 递归 思路: 步骤1: 在当前分区范围[l,r]中随机选中一

    2024年02月09日
    浏览(12)
  • 快速排序算法(递归非递归,三种方法实现,优化)

    快速排序 代码实现 ⚪单趟排序 版本一 ⚪快速排序 递归 关于快排优化 ⚪单趟排序 版本二 ⚪单趟排序 版本三 ⚪快速排序 非递归 特性总结 快速排序作为效率相对较高的排序,分别有递归与非递归两种写法,但都是 进行单趟排序,随后再解决其余问题。 快速排序的平均时间

    2024年02月05日
    浏览(13)
  • 快速排序:高效分割与递归,排序领域的王者算法

    🎬 鸽芷咕 :个人主页  🔥 个人专栏 : 《数据结构算法》《粉丝福利》 ⛺️生活的理想,就是为了理想的生活! 快速排序这个名词,快排之所以叫快排肯定是有点东西的。他在处理大规模数据集时表现及其出色。其思想是在Hoare于1962年提出的一种二叉树结构的交换排序方法

    2024年02月03日
    浏览(10)
  • 快速排序的非递归实现、归并排序的递归和非递归实现、基数排序、排序算法的时间复杂度

    我们使用一个栈来模拟函数的递归过程,这里就是在利用栈分区间。把一个区间分为 [left,keyi-1][key][keyi+1,right]递归下去,直至区间不存在或left right。 如图所示: 先把整体的区间压进去,然后出栈,处理完毕后找到keyi再分为左右两个区间。然后往栈里压有区间,压左区间,就

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

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

    2024年03月24日
    浏览(15)
  • C语言实现八大排序算法(详解插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序(递归和非递归)、归并排序(递归和非递归)和计数排序)

    本篇文章使用C语言实现了数据结构中常见的八大排序算法,它们分别是 插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序和计数排序 。在排序算法的实现过程中,每种算法都有其独特的特点和适用场景。插入排序通过逐步构建有序序列来排序,希尔

    2024年01月24日
    浏览(13)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包