八大排序算法之希尔排序算法

发表于 | 更新于 | 分类于 | 阅读次数：

前言

希尔排序算法也叫做递减增量排序算法，是插入排序算法的一种更高效的改进版本，但是这是一种不稳定的排序算法。插入排序算法是对所有数据进行依次插入排序，而希尔排序是把这些数据分块来进行处理，对其中的每一块都进行插入排序，在好的情况下希尔排序能达到线性的效率，但是差的情况下和直接插入排序的效率是一样的。那么怎么对这些数据进行分块处理呢？希尔排序的每次分块都是取原数组长度的一半来进行分块的，直到最后分块的长度为1的时候，也就是最后一次循环操作的时候，就是和普通的直接插入排序是一样的操作了。

历史

希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根据Metzner本人的说法，“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”来自维基百科

具体思路

首先来看维基百科上的一个例子，假设现在有一个数组a,数组元素分别为13，14，94，33，82，25，59，94，65，23，45，27，73，25，39，10，现在把这个数组分成几个部分每个部分最多为5个数，就是以步长为5进行划分排序。

1
2
3
4
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后对以上数据的每列进行排序，排完后变成以下这种情况了

1
2
3
4
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

把以上的4排数字连接起来展开得到10，14，73，25，23，13，27，94，33，39，25，59，94，65 ，82，45
然后再把这些数字以步长为3进行划分排序

1
2
3
4
5
6
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

对每一列进行排序之后得到

1
2
3
4
5
6
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

再把以上的数字按排进行连接展开，得到10，14，13，25，23，33，27，25，59，39，65，73，45，94，82，94 可以看到数组已经基本上有序了
然后再以步长为1进行排序，步长为1排序，就是简单的插入排序，最后得到10，13，14，23，25，25，27，33，39，45，59，65，73，82，94，94
以上实现思路是把这些数，也就是这个数组划分成多个分块，然后折叠来对每一列的数进行排序，可能有点难理解，所以可以横着看

1
(13) 14 94 33 82 (25) 59 94 65 23 (45) 27 73 25 39 (10)

其实和上面第一步一样，其实就是对原数组中以第一个数开始每隔5个找出一个数，然后把这些数（上面括号中的这些数）进行排序，那么具体要怎么做呢？
1.首先根据数组的长度算出步长，假设步长为n
2.根据步长n，找到步长+1的那个数，也就是n+1为第一个数（这里是第二个括号中25这个数）
3.然后根据第一个数（25）的index找到这个数的第前n个数（这里是13这个数）进行比较，如果比13小，那么进行交换，如果比13大则不交换
4.接着继续找index的前面的第n个数的前n个数，也就是index的前面第2n个数，同时index设置为index-=n，重复步骤3，直到index<0的时候停止。（这样做的意义就是为了防止假如交换了一次数，前面的第2n个数还是比这个数要大，这样排序就失败了，所以每一次都要以步长为n一直往前找，直到第1个数为止）
5.第二轮开始位置是25的后面那个数59了，第一个数以59为准，然后根据步骤4一样操作，直到步骤5到最后一个数结束
6.然后根据增量序列的选择方式进一步设置步长，重复步骤2-5,直到步长为1执行完结束排序
以上例子和部分思路来自维基百科

每次划分的步长应该怎么来计算呢？步长计算很重要，步长的选择决定排序算法的效率，Donald Shell最初建议步长选择为 n/2,并且对步长取半直到步长达到1。虽然这样取可以比O(n^2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。现在很多地方介绍的都是以n/2^i这种方式计算步长，虽然比较方便收敛也比较快，但是效率并不是最优的。
维基百科中提出了三种不同的步长计算方式

步长序列 最坏情况下复杂度
n/2^i O(n^2)
2^k-1 O(n^(3/2))
2^i3^j O(n(logn)^2)

显然最后一种步长序列是最好的，但是步长序列会很密集，排序的外循环会做很多轮，但是每一轮都会很快，而且这种步长序列生成比较麻烦，所以以下代码实现采用了3*n+1这种形式，这样收敛会比较快。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#define N 1000
using namespace std;
int shellSort(int *a,int len)
{
	int temp;
	int n=1;
	while(len/3>n)//计算步长序列（每次步长的变化所形成的数列就是一个步长序列） 
	{
		n=n*3+1;//根据这个通项找到这个序列的最大的值，最大值小于len/3。然后每次循环按着这个通项逐步减小这个步长 
	}
	while(n>=1)//判断步长是否大于等于1，如果小于1了则完成排序，对应步骤6 
	{
		for(int i=n;i<len;i++)//对应步骤5 
		{
			for(int j=i;j>=0;j-=n)//对应步骤3和4，以步长为n从后往前进行比较判断 
			{
				if(a[j-n]>a[j])//如果前面的数要大则与后面第n个数，进行交换（这里是从小到大排序） 
				{
					temp=a[j];
					a[j]=a[j-n];
					a[j-n]=temp;
				}
				else
				{
					break;
				}
			}	
		}	
		n=(n-1)/3;//重新设置步长，更加前面第一循环生成的步长序列的通项，倒序输出步长 
	} 
}
int main()
{
	int a[N],len;
	cin>>len;
	for(int i=0;i<len;i++)
		cin>>a[i];
	shellSort(a,len);
	for(int i=0;i<len;i++)
		cout<<a[i]<<" ";
	cout<<"\n";	 
	return 0;	
}

Sorting Algorithms