快速排序：非递归的优势与性能详解

🎬 鸽芷咕：个人主页
?🔥 个人专栏: 《数据结构&算法》《粉丝福利》

??生活的理想，就是为了理想的生活!

---

📋 前言

快排的性能和各个综合性能都是排序梯队里面最顶尖的，虽然我们掌握递归的方法来快速实现快排，但是递归堆栈的消耗太大了为此我们专门还优化了快排。

一、为什么要掌握非递归

递归来实现快排虽然很简单但是堆栈的消耗很大，所以掌握非递归不仅可以避免递归调用的开销。还能来以此来检验我们的递归能力

在有些场景限制递归深度的时候，例如在嵌入式系统或对递归深度有限制的环境中，非递归就是我们必须掌握的了使得我们的算法可以应用于各种场景

二、栈区和堆区的大小对比

为什么我们一直在说要避免栈区开调用开销，来节省栈的空间呢？其实是因为在操作系统的概念中栈是一快用来快速存储的区域

• 在32位操作系统中栈一般的内存只有 10M
• 而堆的内存划分却达到了 2G

三、非递归实现快排的思想

非递归其实就是利用迭代的思想来替换递归的过程，我们主要考虑的就是 每次 递归的区间怎么控制：

其实我们这里可以考虑使用人工栈的思想来存放每次的区间栈的特点是后进先出而我们递归也是每次先递归 跟 和左子树之后再来进行递归右边的算法

3.1 利用人工栈来实现递归

🔥 注：这里是吧 POP 栈也录入进去了是方便观察实际上是右边 POP 完了之后再 Push 右边。

既然是利用人工栈那么我们首先肯定是先来创建一个栈来把第一个区间录入进去：

• 然后进行循环当栈位空的时候说明我们的数组就递归完了

3.2 实现代码

🍸 代码演示：

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);
		int right = STTop(&st);
		STPop(&st);

		int keyi = PartSort3(a, left, right);
		// [left, keyi-1] [keyi+1, right]

		if (keyi + 1 < right)
		{	
			STPush(&st, right);
			STPush(&st, keyi + 1);
		}
		
		if (left < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, left);
		}
 	}

	STDestory(&st);
}

四、快速排序总结

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN)

4. 稳定性：不稳定