[数据结构] 希尔排序

希尔排序法(缩小增量法) 属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。

把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

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

实现过程

先取一个正整数d1小于n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2小于d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

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

然后我们对每列进行排序：

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

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：

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

排序之后变为：

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

最后以1步长进行排序（此时就是简单的插入排序了）。

实现效率

希尔排序是一个不稳定的排序，其时间复杂度受步长（增量）的影响。

空间复杂度： Ｏ(1)

时间复杂度： 平均 O(n^1.3) 
最好 O(n) 
最坏 O(n^2)

Java实现

public static void shellSort(int[] a) {

 int gap = 1, i, j, len = a.length;

 int temp;//插入排序交换值的暂存

 //确定初始步长

 while (gap len / 3){

 gap = gap * 3 + 1;

 for (; gap 0; gap /= 3){//循环遍历步长，最后必为1

 for (i = gap; i len; i++) {//每一列依次向前做插入排序

 temp = a[i];

 //每一列中在a[i]上面且比a[i]大的元素依次向下移动

 for (j = i - gap; j = 0 a[j] temp; j -= gap){

 a[j + gap] = a[j];

 //a[i]填补空白，完成一列中的依次插入排序

 a[j + gap] = temp;

 }

版权声明：请尊重个人劳动成果，转载注明出处，谢谢！

http://blog.csdn.net/amazing7/article/details/51386145

跟着动画学 Go 数据结构之希尔排序 在插入排序中，在待排序序列的记录个数比较少，而且基本有序，则排序的效率较高。 1959 年，Donald Shell 从“减少记录个数” 和 “基本有序” 两个方面对直接插入排序进行了改进，提出了希尔排序算法。