希尔排序

算法思想

它是对插入插入排序的改进

搜索维基百科可知
希尔排序，也称递减增量排序算法

假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]
，我们分别以步长为5，3，1进行排序（希尔排序最后的步长一定是1）

• 步长为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 13
  25 23 33
  27 25 59
  39 65 73
  45 94 82
  94
  -最后以1步长进行排序（此时就是简单的插入排序了）。

代码实现

public static void shellPass(Integer[] array, int d) {      for (int i = d; i < array.length; i++) {          int temp = array[i];          int j = i - d;          while (j >= 0 && array[j] > temp) {              array[j + d] = array[j];              j -= d;          }          array[j + d] = temp;      }  }    public static void shellSort(Integer[] data) {      int increment = 12;      do {          increment = increment / 3 + 1;          shellPass(data, increment);      } while (increment > 1);    }