【八大排序(六)】快排终极篇-快速排序非递归版

1. 前情回顾

在学习快排非递归版前
我们要先了解快排的思想和栈的结构
可以跳转快排初阶和栈详解复习一下

非递归版的快排只是优化了递归函数
然而单趟快排所用的思想还是不变的
只不过将递归过程转化为了循环

注:本章单趟快排使用最左边做为基准值

---

2. 快排非递归基本思路

我们先定义一个无序数组:

int a[]={6,1,2,7,9,3,4,5,10,8};

一共十个元素,下标范围:0 ~ 9

基本思路:

• 第一次快排要遍历下标0~9的元素
• 将 0 和 9入栈后使用完再出栈
• 假设第一趟快排分了两个子区间为
• 0~ 4和6~ 9.将6,9入栈后再将0,4入栈
• 栈顶为0,4,单趟快排就遍历下标为0~4
• 使用完后0,4出栈,并且将子区间入栈
• 以此类推直到栈中没有元素

画图理解:

---

3. 对非递归思路的解释

思考:

1. 非递归的优势是什么?
2. 为什么要用栈结构?
3. 为什么右子区间要先入栈?
4. 怎么判断左右子区间的小标范围?

解释:

非递归的优势是无论预排序数组多长
都不会产生栈溢出问题.
而递归层数太深,系统栈帧空间不足
就会发生栈溢出的错误

使用栈结构是由于栈的特殊性质:
栈后进先出的特性可以使数组:
左子区间全部排好序再排右子区间.
这和递归的过程保持一致.

如果入栈顺序乱来,也可以排好序
只不过代码和思想不容易被理解

我们设计每一次单趟排序返回
基准值所在位置对应的下标
而下标加一为右子区间的开始
下标减一为左子区间的截至

(注:单趟快排可以使用任意方法)
方法详解:
hoare办法
挖坑法,指针法

---

4. 单趟快排代码实现

我们假设这里使用指针法做单趟快排

前后指针法:

//单趟快排(前后指针版本)
int Partion3(int* a, int left, int right)
{
	//三数取中--面对有序的情况不会栈溢出(key不会选到最大或者最小的数)
	int mini = GetMidIndex(a, left, right);
	swap(&a[left], &a[mini]);
	int key = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		while (a[cur] >= a[key] && cur <= right)//cur指针找小于key的
		{
			++cur;
		}
		if (cur <= right)
		{
			swap(&a[++prev], &a[cur]);
			cur++;//交换完后,cur要再往后走一步
		}
	}
	swap(&a[key], &a[prev]);// 最后交换prev和key的值
	return prev;//返回基准值的位置,方便下次递归
}

---

5. 快排非递归代码实现

非递归代码:

//快速排序(非递归)
void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	StackInit(&st);
	StackPush(&st, left);
	StackPush(&st, right);

	while (!StackEmpty(&st))//当栈不为空时就继续
	{
		int end = StackTop(&st);//将栈顶元素赋值给下标遍历的尾
		StackPop(&st);//删除栈顶元素
		int begin = StackTop(&st);//再将新的栈顶元素给下标遍历的头
		StackPop(&st);//再把这个值删除
		int key = Partion3(a, begin, end);//单趟快排返回基准值对应位置下标
		if (key < end)
		{
			StackPush(&st, key + 1);
			StackPush(&st, end);
		}
		if (begin < key - 1)
		{
			StackPush(&st, begin);
			StackPush(&st, key);
		}
	}
	StackDestroy(&st);
}

---

6. 总结思考

总的来说,学计算机专业的同学
掌握快速排序是必须的.
但是大部分人都只会递归版本的快排
如果在面试的时候你现场给面试官
手撕一个非递归的快速排序
那么你一定会在人群中脱颖而出!

---

下期预告:归并排序初级篇