本篇文章介绍片下希尔排序、快速排序、归并排序算法的思路以及实现，堆排序的内容请参考：堆排序（Heap Sort）

1. 希尔排序

希尔排序是 Donald Shell 在 1959 年所发表的论文《A high-speed sorting procedure》中所描述。希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序对基本有序的序列进行操作操作时，效率高，可达到线性排序的效率。
由于插入排序每次只能移动一个元素，所以其效率是较低的。

我们来看看希尔是如何解决上面的问题，从而提高排序效率的。希尔通过增加一个 gap 间隔参数，将原始的序列进行了分组，例如：gap=2 时，黑色球、绿色球、红色球三组。

然后在组内进行插入排序。这样的话，就带来一个好处，假设升序的话，就能把大部分的值小的元素大体放在了左侧，值较大的元素大体放在了右侧。你可能会想，这也最多达到了基本有序，还不是有序。

是的，接下来，希尔会减小间隔，比如间隔由 2 变成 1，此时希尔插入排序就等价于简单的插入排序。此时，在整个序列上进行一次插入排序，即可使得整个序列有序。这里需要大家理解的是，此时进行插入排序的前提是整个序列已经满足基本有序了。

这个间隔 gap 在算法里也叫做增量，减小增量时，并不是简单将减1. 这个增量的衰减本身也是一个策略，我们一般用：

当然这只是先人的经验给出的增量衰减策略。

所以，希尔排序就是通过分组、减小增量的方式实现排序。该算法又叫分组插入排序、或者减小增量排序。希尔排序是不稳定的排序算法，其算法时间复杂度为 \(O(nlogn)\).

接下来，看下希尔排序的算法实现：

#include <iostream>
using namespace std;


// 升序
void shell_sort(int arr[], int len)
{	
	// 初始增量
	int gap = len;

	do {
		// 衰减增量
		gap = gap / 3 + 1;

		for (int i = 0; i < gap; ++i)
		{
			// 分组插入排序
			for (int j = i + gap; j < len; j += gap)
			{
				if (arr[j] < arr[j - gap])
				{
					int temp = arr[j];
					int k = j - gap;
					for (; k >= 0 && (temp < arr[k]); k -= gap)
					{
						arr[k + gap] = arr[k];
					}

					arr[k + gap] = temp;
				}
			}
		}

	} while (gap > 1);
}

int main()
{
	int arr[] = { 6, 8, 5, 7, 4 };
	shell_sort(arr, sizeof(arr) / sizeof(int));

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

	return 0;
}

程序执行结果：

4 5 6 7 8

2. 快速排序

快速排序是 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

3. 归并排序

归并排序是建立在【归并】操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，它是稳定的排序算法，其时间复杂度为 \(nlogn\)。

归并操作可以将两个有序的序列合并为一个有序序列，也就是说，归并排序的基本思想就是不听的去合并两个有序序列。关键是我们如何去将无序序列构造成两个有序序列呢？

我们想到，如果一个序列只有一个元素的话，那么其就是有序的。所以，归并排序就是通过不停的将序列拆分直至只有 1 个元素，然后再合并，最终使得整个序列变得有序。

注意：这个拆分的过程就是递归的过程，递归到最后，就变成：

两个包含 1 个元素的序列合并成一个包含 2 个元素的有序序列；
两个包含 2 个元素的有序序列合并成一个包含 4 个元素的有序序列；
… 依次类推，直至整个序列变得有序。

算法实现时，要额外去实现下合并两个有序序列的操作函数 merge，当然也可以直接使用 STL 中的 merge 算法。下面为归并排序的实现代码：

#include <iostream>
using namespace std;


//合并两个有序序列
void merge(int arr[], int start, int mid, int end, int* tempSpace)
{
	int iStart = start;
	int iEnd = mid;

	int jStart = mid + 1;
	int jEnd = end;

	int length = 0;

	while (iStart <= iEnd && jStart <= jEnd)
	{

		if (arr[iStart] < arr[jStart])
		{
			tempSpace[length] = arr[iStart];
			iStart++;
			length++;
		}
		else
		{
			tempSpace[length] = arr[jStart];
			jStart++;
			length++;
		}

	}

	while (iStart <= iEnd)
	{
		tempSpace[length] = arr[iStart];
		length++;
		iStart++;
	}

	while (jStart <= jEnd)
	{
		tempSpace[length] = arr[jStart];
		length++;
		jStart++;
	}

	//将辅助空间中数据覆盖到原来空间
	for (int i = 0; i < length; ++i)
	{
		arr[start + i] = tempSpace[i];
	}

}


// 升序
void merge_sort(int arr[], int start, int end, int* tempSpace)
{
	if (start == end)
	{
		return;
	}

	//确定中间元素
	int mid = (start + end) / 2;
	//拆分左半部分
	merge_sort(arr, start, mid, tempSpace);
	//拆分右半部分
	merge_sort(arr, mid + 1, end, tempSpace);
	//合并两个有序序列
	merge(arr, start, mid, end, tempSpace);
}

int main()
{
	int arr[] = { 6, 8, 5, 7, 4 };
	int len = sizeof(arr) / sizeof(int);
	// 开辟辅助空间，空间大小等于数组大小
	int* tempSpace = new int[len];

	merge_sort(arr, 0, len - 1, tempSpace);

	delete[] tempSpace;

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

	return 0;
}

程序执行结果：

4 5 6 7 8

高级排序算法（Quick、Shell、Merge）

1. 希尔排序

2. 快速排序

3. 归并排序

文章目录

《十大排序算法》