希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

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

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

下面看一下图示

上代码

  private static void sort(int[] array) {
    int gap = (int) Math.floor(array.length / 3) + 1;

    while (gap > 0) {
      for (int i = gap; i < array.length; i++) {
        int tmp = array[i];
        int j = i - gap;
        while (j >= 0 && array[j] > tmp) {
          array[j + gap] = array[j];
          j -= gap;
        }
        array[j + gap] = tmp;
      }
      if (gap == 1) {
        gap = 0;
      } else {
        gap = (int) Math.floor(gap / 3) + 1;
      }
    }
  }

希尔排序与选择排序最主要的差别在于引入了一个step变量(指步长，一些书上喜欢用gap或h来表示)，这使得每次交换元素位置，都可以使该元素向其最终位置跨一大步。随着排序的进行，数组越来越接近有序，步长也越来越小，直到step=1，此时希尔排序就变得跟插入排序一模一样了，但此时数组已经几乎完全有序了。

增量的选择

希尔排序的效率取决于gap的选择

Shell增量

N/2,N/4,N/8...1

即初始步长选择N/2，后面每次取半直到步长为1，然而在一些特定输入下它非常低效，它在最坏情形的时间复杂度仍是O(N^2)。事实上除了这个序列，后面列出的序列在最坏情形的性能差距都不会很大。

Hibbard增量

1,3,7,15...,2^k-1

最坏情形O(N3/2)),平均复杂度大概是O(N5/4)，它的重要改进是相邻的增量之间没有公因子。而Shell增量之所以不好，因为它的增量之间并非互素

Knuth增量

1,4,13,40,...,(3^k - 1)/2

同为O(N3/2)，但貌似这个序列使用最广泛，即便现在已经证实了有更好的步长序列。

Sedgewick增量

1,5,19,41,109...

最坏情形O(N4/3)，这是已知复杂度(还有一些实践起来效果很好的序列至今没有算出复杂度)的最佳序列，通过 1,19,109,505,...,9x4^k − 9x2^k + 1 5,41,209,929,...,4^k − 3x2^i + 1 两个算式综合而来，依据基偶性交叉选择两个算式的结果即可。

参考资料

https://www.kancloud.cn/maliming/leetcode/740190

https://www.baeldung.com/java-shell-sort

希尔排序

最后更新：2019-06-17