快速排序算法（递归非递归，三种方法实现，优化）-Toy模板网

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

快速排序
代码实现
⚪单趟排序版本一
⚪快速排序递归
关于快排优化
⚪单趟排序版本二
⚪单趟排序版本三
⚪快速排序非递归
特性总结

快速排序

快速排序作为效率相对较高的排序，分别有递归与非递归两种写法，但都是

进行单趟排序，随后再解决其余问题。

快速排序的平均时间复杂度为O(N*logN)，最坏情况下为O(N^2)，空间复杂度为O(logN)

先介绍单趟排序的版本一紧接着是快速排序递归法，快排后是单趟排序的另外两版本，最后是快速排序非递归

代码实现

单趟排序版本一

1.左右指针

在序列中定义一个key，一般选择序列首位或末尾。
分别在首位和末尾定义left和right，如果左作key则right先走，右作key则左先走，且右找小于key的，左找大于key的元素。
假设首位为key，则right先走，找到小的停下；后left走，找到大的停下；随后left,right下标元素交换。直到left与right相遇，把key与相遇位置交换。
则实现相遇位置左侧都小于key，右侧都大于key（单趟）。
下面代码中三数取中法两行是优化，非排序必需。

快速排序非递归算法,数据结构&&算法,排序算法,算法,数据结构,c语言

//O(N)
//左右指针
int Partion1(int* a, int left, int right)
{
	// 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况
	//将中间值作key，放到序列首位
	int mini = GetMidIndex(a, left, right);
	Swap(a[left], a[mini]);

	int keyi = left;
	while (left < right)
	{
		//右先走，找小
		//对于极端情况比如序列所有元素相同的情况，必须在内部while也写left<right，否则可能存在left或right超出序列范围
		while (left < right && a[right] >= a[keyi])
			right--;

		//左后走，找大
		while (left < right && a[left] <= a[keyi])
			left++;

		//交换将小于key的放到左边，大于key的放到右边
		Swap(&a[left], &a[right]);
	}

	//此时left与right相遇，将该位置元素与key元素交换
	Swap(&a[keyi], &a[left]);
	
	return left;
}

对于递归程序，若递归深度太深，容易造成栈溢出

这里解释一下三数取中，快速排序在不使用三数取中法的情况下，最坏情况下时间复杂度为O(N^2)，即当所有元素有序或接近有序。

快排的时间复杂度取决于选择的key，如果选择的key是序列的最大值/最小值，时间复杂度就是最坏；
而三数取中法就是选取任意三个数的中间大小值（我们选择left mid right），尽可能避免选到最坏情况下的key值。

快速排序递归

快速排序的核心思想是每次当单趟排序后；

序列都会被分为 [begin, keyi-1] keyi [keyi+1, end] 三部分，左侧均小于key，右侧均大于key；

此时将左侧/右侧再次进行单趟排序，循环往复直到当分出的序列中left>=right则此序列有序并返回，最后序列有序。
快速排序非递归算法,数据结构&&算法,排序算法,算法,数据结构,c语言

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

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

关于快排优化

在单趟排序中使用的三数取中是一种优化，前有进行讲述，这里不再过多赘述（主要用于选择合适的基准值，尽量减少时间复杂度最坏情况）
小区间优化：快排在遇到排序序列规模较小时，效率不及其他排序算法，可以自行判断当序列在某个范围内不再进行递归，直接将剩余元素排序(这里选择插入排序，相比于其他排序更适合)

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	// 小区间优化，当分割到小区间时，不再用递归分割思路让这段子区间有序
	// 对于递归快排，减少递归次数
	if (right - left + 1 < 10)
	{
		InsertSort(a + left, right - left + 1);
	}
	else
	{
		int keyi = Partion3(a, left, right);
		// [left, keyi-1] keyi [keyi+1, right]
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}	
}

单趟排序版本二

挖坑法

思路用图片大致解释
快速排序非递归算法,数据结构&&算法,排序算法,算法,数据结构,c语言

void Partion2(int* a, int left, int right)
{
	// 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况
	int mini = GetMidIndex(a, left, right);
	Swap(a[left], a[mini]);

	int key = a[left];//存储序列首位元素
	int hole = left;

	while (left < right)
	{
		//右先走，找小
		while (left < right && a[right] >= a[left])
			right--;

		//找到较小数放到a[hole]，此时right处留空（最后将key补充）
		a[hole] = a[right];
		//将空移到right
		hole = right;

		while (left < right && a[left] <= a[hole])
			left++;
		
		//同理将空转移到此时left
		a[hole] = a[left];
		hole = left;
	}
	//将最初元素补到空上
	a[hole] = a[key];

	return hole;
}

单趟排序版本三

版本三用前后两指针（下标），思路用图片解释

快速排序非递归算法,数据结构&&算法,排序算法,算法,数据结构,c语言

int Partion3(int* a, int left, int right)
{
	//三数取中选择合适的key
	int mini = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mini]);

	//定义下标
	int keyi = left;
	int prev = left;
	int cur = prev + 1;

	while (cur <= right)
	{
		//如果++prev == cur就没必要交换
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}

		++cur;
	}
	Swap(&a[keyi], &a[prev]);
	return prev;
}

快速排序非递归

快排非递归可以采用队列或者是栈的方式，前者类似二叉树

这里使用栈的方式文章来源地址https://www.toymoban.com/news/detail-755403.html

将原数组左右边界入栈。
循环弹出栈顶的左右边界，对该范围内元素进行快排，若左右边界相等或者左边界大于右边界，此时跳出循环。
有key将数组分为两部分，将小于key值放左边，大于key值放右边
左序列的左右边界入栈
右边界的左右边界入栈
重复第二步，直到栈为空停下

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 keyi = Partion3(a, begin, end);
		// [begin, keyi-1] keyi [keyi+1, end]
		if (keyi + 1 < end)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, end);
		}

		if (begin < keyi - 1)
		{
			StackPush(&st, begin);
			StackPush(&st, keyi - 1);
		}
	}
}