数据结构与算法之希尔排序(一步一步带你学会希尔排序）

1. 希尔排序思想

希尔排序从原理上看是插入排序的升级版。

如上图所示，希尔排序首先选择一个步长（假设gap=4)。先把{9,5,10,1}这四个数按照插入排序排好位置，然后再将第二组{6，12，15，13}也按照插入排序排好，后面重复以4为步长组合的数组插入排序。
经过第一轮以4为间隔的组合数组排序后，这个数组就会变得基本有序了。但是也只是基本有序，所以还需要再次缩小步长继续重复上述插入排序，直到步长为1的时候就是插入排序了。

为什么希尔排序的效率比插入排序高？

1. 当数组很长的时候，当有一个1在数组最后,如果用插入排序，这个1就要移动n次才能到最前面。但是如果用希尔排序，这个1只用移动一次就能到最前面。总结：间隔大，移动次数少
2. 当数组间隔小的时候，由于在间隔大的时候已经将最小的数基本都排到最前面了，所以后面进行1个步长的插入排序时，移动的距离也少了。总结：间隔小，移动距离短

2.希尔排序算法实现

1. 先写出插入排序算法，固定一个步长的算法

public static void shellSort(int[] arrays) {

        int gap = 4;

        for (int i = gap; i < arrays.length; i++) {
            for (int j = i; j > gap-1; j-=gap) {
                if (arrays[j] < arrays[j - 1]) {
                    swap((arrays, j, j - 1);
                }
            }
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 逐渐缩短步长，直到步长等于1变成插入排序

public static void shellSort(int[] arrays) {
        for (int gap = 4; gap > 0; gap /= 2) {
            for (int i = gap; i < arrays.length; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (arrays[j] < arrays[j - 1]) {
                        swap((arrays, j, j - 1);
                    }
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11

3. 对于比较长的数组，比如亿级别的，4这个步长还是太小了。步长越小，移动的次数也就越多。所以可以用二分法来取它的步长

  public static void shellSort(int[] arrays) {
        for (int gap = arrays.length >> 1; gap > 0; gap /= 2) {
            for (int i = gap; i < arrays.length; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (arrays[j] < arrays[j - 1]) {
                        swap((arrays, j, j - 1);
                    }
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11

4. 修改gap 使得算法更快更高效，国际上对步长有一个公式，如下

继续优化算法为：

public static void shellSort(int[] arrays) {
        int h = 1;
        while (h <= arrays.length) {
            h = 3 * h + 1;
        }
        for (int gap = h; gap > 0; gap = (gap - 1)/ 3) {
            for (int i = gap; i < arrays.length; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (arrays[j] < arrays[j - 1]) {
                        swap((arrays, j, j - 1);
                    }
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3. 算法时间复杂度和稳定性

1. 希尔排序是跳着排序的，所以不稳定
2. 时间复杂度，目前国际上算出的最平均的复杂度是O(n^1.3)，证明略…