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

1、霍尔版本

单趟实现逻辑： 选定第一个元素为key，第二元素设定left，最后一个元素设定为 right。right从右往左遍历找比 key小的数字，left从左向右找比key大的数字（注：右边先开始找，这样做的目的是为了让相遇点的值一直会小于key）。当两边都找到了之后，交换值。然后开始下一轮的寻找，直到 left 和 right 相遇，把key点的值和相遇点的值交换。

代码：

int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		//先从右边找小
		//目的是为了保证交换的时候数字小于key
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		//从左边找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		if (left < right)
		{
			Swap(&a[left], &a[right]);
		}
	}

	int meeti = left;
	Swap(&a[meeti], &a[keyi]);
	return meeti;
}

递归实现整趟：设置好停顿条件，如果 begin >= end ，就返回。先整体用单趟排一遍，再分为两部分，分为相遇点的左边和相遇点的右边两部分，再进行递归排序。

代码：

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	//先整体排
	int keyi = PartSort1(a, begin, end);

	//再分部分
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

分析

但是如果每次都分成的两部分是一个和一个x-1呢？如下所示：

这样是大大影响了排序的效率的，递归的时候也有可能栈溢出。

优化

我们在上面分析中说到，最好的情况：每一次都分成平均的两部分。这样的的效率可以达到最高。

因此，为了每次都能分成平均的两部分，我们就要加以改良单趟排序。

我们可以采取三值取中的方法：我们可以取下标 left 和 right 的平均值取到中间下标 mid ，取到比较三者下标对应的值，取到中间值来作为我们的 key 对应的值。

代码：

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

//快排的单趟
int PartSort1(int* a, int left, int right)
{
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);

	int keyi = left;
	while (left < right)
	{
		//先从右边找小
		//目的是为了保证交换的时候数字小于key
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		//从左边找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		if (left < right)
		{
			Swap(&a[left], &a[right]);
		}
	}

	int meeti = left;
	Swap(&a[meeti], &a[keyi]);
	return meeti;
}

2、挖坑法

单趟实现逻辑：key 记录 left 下标所代表的数字，在 left 下标上挖坑 hole 。右边 right 开始找小，找到之后把 right 下标所指的数字填到 hole 中，right 的位置形成一个坑 hole。接着，左边 left 开始找大，找到之后把 left 所指的数字填到 hole 中，left 的位置形成一个坑。循环往复，直到 left 和right 相遇。

代码：

//挖坑法
int PartSort2(int* a, int left, int right)
{
	int mid = GetMidIndex(a, left, right);
	//a[left]放中间值
	Swap(&a[left], &a[mid]);

	int key = a[left];
	int hole = left;
	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;
	}
	//最后把key放入坑中
	a[hole] = key;
	return hole;
}

递归实现整轮：注意，三种方法的整轮递归实现都是一样的。下文就不再给出。

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	if (end - begin <= 8)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		//先整体排
		int keyi = PartSort3(a, begin, end);

		//再分部分
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	
}

分析

值得注意的是，在10000000个数据的测试下，挖坑法相比于霍尔法，效率要高上一些。

但是仍然是不稳定的。

3、前后指针法

单趟实现思路： cur 每次都会自增，而 prev 会停在大于 key 下标所指的数字前面，直到 cur 再遇到小于的数字， prev 和 cur 两者交换下标所值数字。

创建两个下标 prev 和 cur ， prev 和 left 一样大小， cur 则在 prev 前面一格。设定循环，结束条件为 cur 小于等于 right 。每走一次循环， cur 都会自增加1。而只有 cur 下标所指的数字小于key所指的数字的时候，prev 才会自增加1，并且交换 prev 和 cur 两个下标所指的值。

代码：

//前后指针法
int PartSort3(int* a, int left, int right)
{
	int mid = GetMidIndex(a, left, right);
	//a[left]放中间值
	Swap(&a[left], &a[mid]);
	int key = left;
	int prev = left, cur = left + 1;

	while (cur <= right)
	{
		//如果差距大于一格说明prev停在了大于a[keyi]的数字的前面
		if (a[cur] < a[key] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[key], &a[prev]);
	return prev;
}

再优化

前面我们已经根据取值做出了三值取中的优化，那么还能不能在此基础上进行优化呢？

我们能够知道，最后一层递归展开差不多占了总排序的一半之多，倒数第二层则占了25%左右，倒数第三层则占了12.5%，最后三层总共占了87.5%。经过初期的排序，到最后三层的时候已经变得大致有序了，而最后三层的性能消耗占比太多。如果我们能够用另一种更优的排序替代最后三层的排序，那么性能就又能得到更大的提升。

在大致有序的时候，排序最好的是插入排序。因为希尔排序还要分组，堆排序还要建堆，冒泡排序也不如插入排序。所以，我们最后剩下八个元素的时候，我们开始用插入排序，效率就会变得更高。

代码：

//用递归思路
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	if (end - begin <= 8)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		//先整体排
		int keyi = PartSort2(a, begin, end);

		//再分部分
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	
}

非递归方法

讲完了快排的递归方法，我们再来探讨一下非递归方法。其实，我们之前也看过斐波那契数列的非递归写法，究其根本，其实还是用着非递归的方法模拟着递归。

非递归方法实现的思想：将 left 和 right 的下标存入栈中，然后再从栈中取出下标，再用取出的下标进行单趟排序。排完之后的分为两部分，再分别把两部分的 left 和 right 下标存入栈中，在进行排序，直到最后排序完成。

在此之前，我们需要把栈的代码拷贝过来，不然无法调用栈。

关于栈的代码，可以前往gitee中提取：数据结构: 学习数据结构的代码存放 (gitee.com)

代码：

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

	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);

		int left = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort3(a, left, right);
		
		//右半部分先入栈
		if (keyi + 1 < right)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}

		//左半部分后入栈
		if (keyi - 1 > left)
		{
			StackPush(&st, left);
			StackPush(&st, keyi - 1);
		}
	}

	StackDestroy(&st);
}

注：我们第一次进行排序的时候需要在循环外面手动入栈 left 和 right 。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-10-06，如有侵权请联系 cloudcommunity@tencent.com 删除

递归