希尔排序

算法思想

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

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

假设有这样一组数[ 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); 
 
}