制作不易，三连支持一下吧！！！

---

前言

前两篇博客介绍了插入和选择排序，这篇博客我们将会介绍一个非常重要的排序算法——快速排序，它的实践价值要大远远于前两种排序。

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

---

一、快速排序Hoare版本实现

动图展示如下：

这里再简单解释一下：

我们一般选取最左或最后边的值作为基准值（key），如果我们选择最左边的值为key，且我们要排成升序序列，那我们就让最右边先走（为了保证相遇位置的值一定比key小），找到比key小的位置停下来，然后左边再走，找到比key大的位置停下来，两者交换，循环上述操作，直至left和right相遇，再将相遇位置的值与key交换，这样就完成了单趟排序。

key位置的元素就排到了合适的位置。 

之后递归左右区间即可。

代码实现：

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void QuickSort(int* a, int begin, int end)
{
	//最小子问题，返回条件
	if (begin >= end)
		return;

	int key = begin;
	int left = begin;
	int right = end;

	while (left<right)
	{
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		while (left < right && a[left] <= a[key])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}
	Swap(&a[key], &a[left]);
	key = left;

	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);

}

 二.快速排序挖坑法版本实现

挖坑法是在hoare大佬版本的基础上为了好让大家理解而改进的一种思路，因为hoare版本如果以最左边的值做key，则必须要让右边先走，让最右边的值做key，则必须要让左边先走，否则会出现错误。 而如果是挖坑法，则无需关心这个问题。大家自然而然会按正确的方式实现。

动图演示如下: 

通俗一点解释：

我们将key位置的值保存下来，将那个位置视为一个坑位，右边先走，找到比key小的值就填到坑位中，坑位就更新到新的位置，左边再找大，再更新坑位的位置，直到left和right相遇，将原来key中的值放到坑位中就完成了单趟排序。

这样我们就避免了考虑哪边先走的问题，因为如果左边为坑，我们自然而然的就会让右边先走！

代码实现如下：

QuickSort2(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int left = begin, right = end;
	int key = a[begin];
	int hole = begin;

	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}

		a[hole] = a[right];
		hole = right;

		while (left < right && a[left] <= key)
		{
			left++;
		}

		a[hole] = a[left];
		hole = left;
	}

	a[hole] = key;
	int keyi = hole;

	QuickSort2(a, begin, keyi - 1);
	QuickSort2(a, keyi + 1, end);

}

三.快速排序前后指针版本实现 

前后指针版本是这三种方法里面最值得推荐的一种，因为它实现出来非常的简单。

动图演示如下：

 

 简单解释一下：

定义两个指针prev和cur，如果啊a[cur]比key位置的值小，就让prev前进一步，并交换cur和prev位置的值，如果a[cur]比key位置的值大，就只++cur。

最后，prev和cur之间的值就是整个序列中比key位置的值大的值。prev之前的值就是比key位置的值小的值。

代码实现如下： 

QuickSort3(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int prev = begin, cur = begin + 1;
	int keyi = begin;
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}

		cur++;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;

	QuickSort3(a, begin, keyi - 1);
	QuickSort3(a, keyi + 1, end);

}

 

四.快速排序非递归法实现 

之前的三种方法虽然思路略有不同，但本质都是分治递归的思想，这种思想比较容易理解，但是递归深度过深可能会导致栈溢出，因此，我们必须掌握非递归的实现，以适用于所有场景。 

从递归改成非递归的方法一般有两种：

• 直接改成循环——例如：斐波那契数列
• 借助于栈或队列的结构。

我们这里就是要借助于栈的数据结构。

整体思路就是压栈，每次取出一个区间进行单趟排序，然后再入栈，如果区间不存在或只有一个元素就不再入栈，直至栈为空时，排序就完成了。 

代码实现如下： 

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int prev = begin;
		int cur = begin + 1;
		int keyi = begin;
		while (cur <= end)
		{
			if (a[cur] < a[keyi] && ++prev != cur)
			{
				Swap(&a[prev], &a[cur]);
			}
			cur++;
		}
		Swap(&a[keyi], &a[prev]);
		keyi = prev;

		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi+1);
		}
		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);
}

 

五 两种优化（小区间优化和三数取中）

1.小区间优化

从分治的角度看，快速排序是一种二叉树结构的排序，有些大佬觉得最后几层占了整个递归次数的百分之八九十，消耗有些大，所以当区间长度小于一定数量（一般是10）时就直接用直接插入排序就好了。

也就是说最小子问题不再是区间不存在或只有一个值了，而是区间长度小于10.

if (end - begin + 1 <= 10)
InsertSort(a, end - begin + 1);

2.三数取中 

快速排序在序列有序时，效率是不高的，时间复杂度不再是O（N*logN），而是O（N^2）。

为了尽量避免出现最坏的情况，我们可以采用三数取中的方法，防止key是最大或最小的值。

//三数取中
int GetMid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[right] > a[mid])
		{
			return mid;
		}
		else if (a[right] < a[left])
		{
			return left;
		}
		else {
			return right;
		}

	}
	else {
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else {
			return right;
		}
	}
}

 

以hoare版本为例，加入三数取中后，就是这样： 

//快速排序Hoare版本
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int begin = left, end = right;

	//随机数作key
	//int randi=rand()%(right-left+1);
	//randi += left;
	//Swap(&a[randi], &a[left]);

	//三数取中
	int mid = GetMid(a, left, right);
	Swap(&a[mid], &a[left]);


	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}

		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);

}

 

---

总结

快速排序是实践中运用非常多的一种排序，它的价值非常高，我们应该熟练掌握快速排序的思想。