本篇文章来聊一聊希尔排序。

基本思想

上篇文章我们学习了折半插入排序，该排序算法的原理是在顺序插入查找插入过程中使用折半查找法从而提高插入效率，为此，我们可以思考一下是否还有办法能够使插入的效率更高呢？

基于此，希尔排序诞生了，希尔排序的基本思想为：

先将整个待排序序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行一次直接插入排序。

图解排序过程

现有如下的一个序列：

我们以5为间隔，将原序列分成若干个子序列：

此时81、35、41就组成了一个子序列，我们对该子序列进行插入排序，结果如下：

因为81数值比较大，若按顺序插入或者折半插入，需要经过多次的比较才能够到达指定的插入位置，而通过希尔排序，只进行了两次比较，就让35和81非常接近最终的插入位置，这样的效率无疑是很高的。

此时35、41、81已经有序，我们再以5为间隔，得到一个子序列：

此时得到94、17、75组成的子序列，对其进行插入排序，结果如下：

再以同样的方式得到一个子序列：

对11、95、15进行插入排序，结果如下：

同样的，再以5为间隔得到子序列：

此时子序列中只有两个元素96、28，这并不影响，继续进行插入排序即可：

最后一次排序，结果为：

经过了一系列的操作之后，序列中比较大的元素基本都往后靠了，比较小的元素基本都往前靠了，但是序列仍然是无序的，接下来我们以3为间隔，继续划分序列：

此时得到一个子序列：35、28、75、58、95，对该序列进行插入排序：

以同样的方式执行上述过程，最终结果为：

现在的序列虽然还是无序的，但已经非常接近有序的结果了，我们最后以1为间隔对其进行插入排序，也就是进行直接插入排序，因为这些元素已经基本有序，所以在进行直接插入排序的时候效率是非常高的，最终结果为：

这个划分子序列的间隔是随意的，但一定要逐次递减，最后为1(增量序列应该是互质的)。

代码实现

先构建出待排序序列：

typedef struct {
	int key;
}ElemType;

typedef struct{
	ElemType *n;
	int length;
}SSTable;

SSTable CreateTable(){
	SSTable st;
	st.n = (ElemType*) malloc(sizeof(ElemType) * 14);
	st.length = 13;
	st.n[1].key = 81;
	st.n[2].key = 94;
	st.n[3].key = 11;
	st.n[4].key = 96;
	st.n[5].key = 12;
	st.n[6].key = 35;
	st.n[7].key = 17;
	st.n[8].key = 95;
	st.n[9].key = 28;
	st.n[10].key = 58;
	st.n[11].key = 41;
	st.n[12].key = 75;
	st.n[13].key = 15;
	return st;
}

希尔排序算法实现如下：

void ShellInsert(SSTable t,int dk){
	int i,j;
	for(i = dk + 1;i <= t.length;++i){
		if(t.n[i].key < t.n[i - dk].key){
			//将当前元素存入哨兵位置
			t.n[0] = t.n[i];
			for(j = i - dk;j > 0 && t.n[0].key < t.n[j].key;j = j - dk){
				t.n[j + dk] = t.n[j];
			}
			t.n[j + dk] = t.n[0];
		}
	}
}

void ShellSort(SSTable t,int dlta[],int n){
	int i;
	//以增量序列为间隔，进行t趟排序
	for(i = 0;i < n;++i){
		ShellInsert(t,dlta[i]);
	}
}

希尔排序算法其实和直接插入排序算法没啥区别，只是间隔变为了dk，其它的都一样，所以注释就不写了，如果你掌握了直接插入排序，并且搞懂了上面的图解，这个算法对你而言就没有难度。

测试代码：

int main(int argc, char const *argv[]){
	SSTable t = CreateTable();
	//定义增量序列
	int dlta[] = {5,3,1};
	Traverse(t);
	ShellSort(t,dlta,3);
	Traverse(t);
	return 0;
}

前面也说了，这个增量序列是随意的，但最后必须为1，且其它增量值无除1之外的公因子，所以，你也可以定义增量序列为：int dlta[] = {7,5,3,1};，或者定义为：int dlta[] = {4,3,2,1};，还可以定义为：int dlta[] = {10,7,4,1};，都是没有任何问题的。

性能分析

不难发现，希尔排序的效率是由增量序列决定的，其时间复杂度的计算过程难度较高，这里就直接给出了。在最坏情况下，希尔排序的时间复杂度为O(n²)；最好情况下，其时间复杂度为O(n)，所以，其平均时间复杂度约为O(n^1.3)。

对于空间复杂度，因为其只使用了一个空的元素空间用于做哨兵位置，所以其空间复杂度为O(1)。