算法-基本排序算法-04 希尔排序详解

1.要点

希尔排序就是多次不同增量（increment）的插入排序，是跳跃性的插入排序。 增量的理解是重点和难点

2.动图演示

2.1 先了解插入排序 InsertSort

插入排序的increment增量为1，就是说这是挨着的插入排序.

2.2 希尔排序ShellSort 就是在多次不同增量的插入排序

这里的增量依次为

21721 就是说希尔排序进行了4次插入排序。

3.（重点） 理解增量increment

举个例子，这里有一个数组. [9,1,5,8,3,7,4,6,2]

增量increment是如何计算的？ 计算的方法是自定义的，这里的计算方法是increment = increment /3 +1，increment 初始值的等于 数组长度 9 ,所以第一次循环是增量为 4 的时候。

3.1 增量increment = 4 的时候.

增量为 4 的第一次遍历

判断 3 小于 9 所以进行交换,一次插入排序的一个遍历. 因为增量为 4 ，所以这里只能这个长度只能判断一次( 下标 4 -4 =0-，还在范围内，4 -4 -4 = -4已经不在范围内了）。结束

增量为4的 第二次遍历.

判断1 < 7 所以不用交换值，进行一次判断，直接结束

增量为 4 的第三次遍历

同理增量为 4第一次遍历，长度不厚只能进行一次判断，结束.

增量为 4 的第四次遍历\

同理将比较小的放到前面，因为长度限制，只能比较遍历一次.

第五次遍历

因为长度足够，所以可以从2个位置中选择合适的位置插入. 插入步骤 1.下标为4,和 0 的元素依次右移 增量increment = 4 的位置，

arrays[8] = arrays[4]; arrays[4] = arrays[0];

2.将 记录好的 int temp = arrays [8]移动arrays[0]的位置

arrays 0 = temp;

3.2增量为 2的时候

类似增量为 4，我们跳跃式的插入排序就 OK

3.3 增量为 1 ，最后一次排序

增量为 1就是普通的插入排序。 请点击上方插入排序链接了解插入 排序.

4.算法步骤

1.选择不同的增量（增量的计算公式可以是自己定的，要求是最后要回归到1，最后一次增量为1的插入排序结束排序，也可以参考 代码中的增量计算公式 increment = increment / 3 ;） 2.以不同的增量进行插入排序，完成排序

5.代码

java 代码实现

public static int[] shellSort(int[] sourceArray) { int length = sourceArray.length; //给increment 赋值一个合适的初始值. int increment = length; //分而治之 do { //更新increment. increment = increment / 3 + 1; //第一层遍历 ++ for (int i = increment; i < length; i++) { int temp = sourceArray[i]; int j = i; while ( j-increment >=0 && temp < sourceArray[j-increment] ){ sourceArray[j] = sourceArray[j-increment]; j-=increment; } //如果之前有值移动，就形成插入条件，就执行最后的插入. if (j!=i){ sourceArray[j] = temp; } } }while (increment > 1); return sourceArray; } }

6 代码解释

do while{} 循环里面每一次循环都是不同的增量increment的一次插入排序，上面的例子的增量的值依次是4,2，1 ，(当增量为 1 的时候就是普通的插入排序)do while{} 循环中要保证最后运行一次 增量increment为 1 的插入排序就退出do while 循环。这里增量的计算公式是 increment = increment / 3 + 1，你可以设计自己的插入公式，不同的插入公式速度会有差别。

5. 优缺点

优点：

效率高：时间复杂度 O（n3/2)二分之三，优于冒泡排序，选择排序，插入排序 的 O(n2)

缺点：

不是稳定的算法，因为是跳跃式的。