【数据结构与算法】快速排序的非递归实现方法-Toy模板网

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

【数据结构与算法】快速排序的非递归实现方法

文章来源地址https://www.toymoban.com/news/detail-415992.html

一.前言

二.非递归实现

一.前言

如果数据量过大的话，不断递归就会出现栈溢出的现象，这个时候你的代码是没问题的，但就是跑不起来，这个时候就要把递归改成非递归。

一般有两种改法：

1.直接改，利用循环等；

2.借助栈的辅助。

而快速排序的非递归实现方法就需要借助栈的辅助。

二.非递归实现

【数据结构与算法】快速排序的非递归实现方法

通过观察我们发现，每次递归调用传过去的是一个数组和一个区间，数组自不用说，这个区间就是我们的突破点；

也就是说我们只要想办法在循环的时候拿到本次要排序的区间就行了，那要怎么做呢？

借助数据结构：栈，栈具有后进先出的特性，借助这个就能很好的解决问题。

1.首先要先把 left 和 right 入栈，这样栈此时就不为空，然后开始循环。

2.取出栈顶的两个数据，分别赋给 begin 和 end ，注意在这之后要pop掉取出的数据；

3.然后就是快排的逻辑，有三种方法，哪种都可以；

如果不清楚这三种方法的话，请点击：快速排序的三种实现方法

走完一趟后就得到了 keyi；

4.然后数组就被 keyi 分成了两个子区间，分别是：

左区间：[begin，keyi-1]

右区间：[keyi+1，end]

分别将左区间和右区间入栈，注意这里要判断：

a.keyi+1<end

b.keyi-1>begin

否则会出现数组访问越界或是死循环的情况。

5.因为栈是后进先出，所以要是想先排左区间的话，就要先入右区间进栈，反之；

6.循环结束后，销毁栈。

void QuickSortNonR(Sdatatype* arr, int left, int right)
{
	ST st;
	Stackinit(&st);
	
	Stackpush(&st, right);
	Stackpush(&st, left);
	while (!Stackempty(&st))   //栈为空时就结束循环
	{
		int begin = Stacktop(&st);   //出一个就要pop掉一个数据
		Stackpop(&st);
		int end = Stacktop(&st);
		Stackpop(&st);
		int keyi = begin;    //以下为快速排序的逻辑，这里用的是前后指针法实现
		int mid = GetMid(arr, begin, end);
		if (mid != keyi)
			Swap(&arr[mid], &arr[keyi]);
		int prev = begin, cur = begin + 1;
		while (cur <= end)
		{
			if (arr[cur] < arr[keyi])
			{
				prev++;
				Swap(&arr[cur], &arr[prev]);
				cur++;
			}
			else
				cur++;
		}
		Swap(&arr[keyi], &arr[prev]);
		keyi = prev;   
		if (keyi + 1 < end)    //不要忘记判断
		{
			Stackpush(&st, end);    //这里是先入的右区间，所以是先排序左区间
			Stackpush(&st, keyi + 1);
		}
		if (keyi - 1 > begin)
		{
			Stackpush(&st, keyi - 1);
			Stackpush(&st, begin);
		}
	}

	Stackdestroy(&st);   //销毁栈
}