经典排序算法 - 希尔排序Shell Sort

简单介绍

希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本，本质上是一种分组插入排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1、插入排序在对几乎已经排好序的数据操作时，效率高，可以达到线性排序的效率

2、但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

算法原理

将序列分组为较小的子序列，然后再利用直接插入排序进行组内排序，继而逐步增大组的大小，直到与原序列相同大小。

注意：不要与归并排序相混淆，看到网上有网友把归并排序与希尔排序的细节搞错了。尽管归并排序看起来也是从小到大合并，但是本质上是不一样的：归并排序的分是将相邻的元素化为一组，而希尔排序则是按照步长来分组的。打个比方，军训的时候，教官从第一个人数到第八个人然后说“你们一组”，这是归并排序；而希尔排序则是，教官说“从一个人开始，依次报数，奇数的是一组”。我想，大家应该能明白了吧。

希尔排序演示（来自维基）

具体实例演示

下面用希尔排序来对数组 {13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10} 排序（按照2i的分组序列）

Step 1

首先，我打算分为两个一组，共有16个数，就是八组，步长为8。

{13, 65} {14, 23} {94, 45} {33, 27} {82, 73} {25, 25} {59, 39} {94, 10}

组内用直接插入排序，得到

{13, 65} {14, 23} {45, 94} {27, 33} {73, 82} {25, 25} {39, 59} {10, 94}

Step 2

第二步，将新序列分为四个一组，共有四组，步长为4

{13, 45, 73, 39} {65, 94, 82, 59} {14, 27, 25, 10} {23, 33, 25, 94}

组内用直接插入排序，得到

{13, 39, 45, 73} {59, 65, 82, 94} {10, 14, 25, 27} {23, 25, 33, 94}

Step 3

第三步，八个一组，共两组，步长为2

{13, 45, 59, 82, 10, 25, 23, 33} {39, 73, 65, 94, 14, 27, 25, 94}

组内用直接插入排序，得到

{10, 13, 23, 25, 33, 45, 59, 82} {14, 25, 27, 39, 65, 73, 94, 94}

Step 4

第四步，16个一组，共一组，得到

{10, 13, 23, 25, 33, 45, 59, 82, 14, 25, 27, 39, 65, 73, 94, 94}

组内用直接插入排序，得到

{10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94}

排序完成。

太原理工大学也有动态的演示，可以看看。网址：http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/shell_sort.asp

示例代码

void shellSort2(int *src, int size)
{
	int step = size / 2;
	int j,tmp;

	while(step >= 1)
	{
		for(int i=0; i<size; i+=step)
		{
			//从第一个元素开始，每次取出一个加入到有序序列中 
			j = i; 
			tmp = src[i]; 
			while(j>0 && tmp<src[j-step]){
				//找到新元素在有序序列中的位置
				src[j] = src[j-step];
				j-=step;
			}
			src[j]=tmp;
		}
	step/=2;
	}
}

详细代码请点击这里查看。

算法复杂度及稳定性

首先说稳定性。由于希尔排序分组是具有跳跃性的，故不稳定。

（以下主要参考自维基百科）

复杂度方面，shell算法的性能与所选取的分区长度序列有很大关系。前面的实例是最简单的分组长度序列，及n/2i ，最坏情况下时间复杂度是O(n^2)。

已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,…)，该序列的项来自9*4^i - 9 *2^i + 1和2^{i+2} * (2^{i+2} - 3) + 1这两个算式。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

尽管看起来，用了好多次直接插入排序，但是每次都是对基本有序（或者数量少）的序列进行排序，充分发挥了直接插入排序的优势，故希尔排序一般是优于直接插入排序的。

另一个在大数组中表现优异的步长序列是（斐波那契数列除去0和1将剩余的数以黄金分区比的两倍的幂进行运算得到的数列）：(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)

对了，突然想到上次说自底向上的归并排序跟希尔排序很像，这次得出结论了，正如我在上文中提到的，它们在细节上是有差别的。