快速排序（Quick Sort）

快速排序是 C.R.A.Hoare 于1962 年提出的一种排序算法，该算法如其名一样确实很快。快速排序采用了一种 “汾治策略” 来对序列进行排序。

算法基本思想是：通过一次遍历将序列分成两部分，其中一部分元素比基准元素（序列中的某一元素）小，另一部分都比基准元素值大。然后再按此方法递归对两部分进行排序操作，直到整个序列变得有序。

具体算法流程如下：

首先选择一个元素作为基准值；
将大于或等于基准值的元素集交换到基准值的右侧，小于基准值的元素交换到基准值的左边；
对左右两部分元素递归进行 1-2 步的操作；
直到分组中只有一个元素，算法收敛，此时序列已经有序。

举个例子，假设序列如下，我们就选择第一个元素 5 作为基准数，当然也可以选择其他值，关于基准数的问题我们一会再说。

通过对元素的遍历、比较、交换，将小于 5 的元素都放到基准元素的左侧，将大于等于基准值的元素放到基准元素的右侧，如下图所示：

此时，大家应该发现了元素 5 已经放到它最合适的位置上了，它不用再进行任何操作了。接下来，递归对左半部分、右半部分的元素进行上面的操作，直到每个部分只有一个元素时停止。

关于基准数的选择是会影响到排序效率的因素，其也是快速排序优化的重点。基准数如何影响到算法效率呢？假设：我们选择的基准数正好是序列中最小的值，那么序列的分割就会呈现如下图所示：

每一层将会有 n 个元素，每个元素又要比较 n 次，此时算法的时间复杂为 \(O(n^2)\)。那么，如果你每次选择的基准元素正好是中位元素时，那么情形就变成下面这样：

那么算法将会分裂 \(log_{2}n\) 次，每次比较和交换 n 个元素，其算法时间复杂就为 \(nlogn\)。由此可以看到基准数选择的越接近中位元素，则算法的效率就越好。

这也是个难点，因为我们无法知道那个元素是中位。所以，就有很多策略，最简单就是机械选择第一个元素，或者随机选择，再或者… 感兴趣的大家可以自己去查一查。

最后，快速排序是不稳定的排序算法。

接下来，给出快速排序的实现代码：

#include <iostream>
using namespace std;

// 升序
void quick_sort(int arr[], int start, int end)
{
	if (start >= end)
	{
		return;
	}

	//选取基准数
	int pivot = arr[start];
	int i = start;
	int j = end;

	while (i < j)
	{
		while (i < j && (arr[j] > pivot))
		{
			j--;
		}

		if (i < j)
		{
			arr[i] = arr[j];
			++i;
		}

		while (i < j && (arr[i] < pivot))
		{
			++i;
		}

		if (i < j)
		{
			arr[j] = arr[i];
			--j;
		}
	}

	//将基准数放到最合适位置(i或者j位置)
	arr[i] = pivot;

	//对i左侧序列进行快速排序
	quick_sort(arr, start, i - 1);
	//对i右侧序列进行快排
	quick_sort(arr, i + 1, end);
}

int main()
{
	int arr[] = { 6, 8, 5, 7, 4 };
	quick_sort(arr, 0, sizeof(arr) / sizeof(int) - 1);

	for (auto v : arr) cout << v << " ";
	cout << endl;

	return 0;
}

程序执行结果：

4 5 6 7 8

快速排序（Quick Sort）

取消回复