希尔排序（Shell Sort）

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

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

我们来看看希尔是如何解决上面的问题， 从而提高排序效率的。希尔通过增加一个 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