数据结构 ——— 快速排序的实现（非递归）

目录

前言

快速排序非递归的思路

快速排序的实现（非递归）

前言

在前面几章学习了快速排序实现的不同版本，和三数取中法来规避最坏的情况
数据结构 ——— 快速排序的时间复杂度以及规避最坏情况的方法-CSDN博客

但是都是使用的递归，且递归是存在栈溢出的风险的，所以接下来要学习的是非递归实现快速排序

快速排序非递归的思路

先看递归的思路是控制数组的左右区间，再通过不同版本的单躺排序完成数组的排序

所以说只要能控制每次单躺排序的左右区间，就能用非递归排序，那么利用栈的后进先出结构来控制左右区间最合适

举例说明：

最开始数组的左右区间为：[0,9] ，那么就让 0 和 9 入栈，走完第一次单躺排序后，key 到了最终位置，把 [0,9] 出栈，再通过 key 的下标分割出左右区间：[0,4] 和 [6,9] ，再次入栈，重复以上过程

直到区间为 [0,0] 或者 [2,1] 时就停止，因为区间为 [0,0] 和 [2,1] 时就表示只有一个元素了，就不用入栈了，直到栈为空时，就完成了对数组的快速排序

快速排序的实现（非递归）

代码演示：

void QuickSortNonR(int* a, int begin, int end)
{
	ST st;

	// 初始化栈
	STInit(&st);

	// 左右区间进栈，先入左再入右
	STPush(&st, begin);
	STPush(&st, end);

	while (!STEmpty(&st))
	{
		// 先出右
		int right = STTop(&st);
		STPop(&st);

		// 再出左
		int left = STTop(&st);
		STPop(&st);

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

		// 再入子区间的左右
		if (keyi - 1 > left)
		{
			// 先入左再入右
			STPush(&st, left);
			STPush(&st, keyi - 1);
		}

		if (keyi + 1 < right)
		{
			// 先入左再入右
			STPush(&st, keyi + 1);
			STPush(&st, right);
		}
	}

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

代码解析：

关于栈的实现详情请见：数据结构 ——— C语言实现数组栈_c语言入栈和出栈,栈头栈尾-CSDN博客

需要注意先入左再入右的话，那么就要先出右再出左，因为栈是先进后出的结构

代码验证：