希尔排序

一、基本思想

希尔排序（Shell Sort）的基本思想是使数组中任意间隔为h的元素都是有序的。
换句话说，一个h有序数组就是h个相互独立的有序数组编织在一起组成的数组。
希尔排序基于插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

1-1 希尔排序示意图

具体步骤：

1. 产生一个从大到小的递增序列：h=M，N，J，Q，…，1；
2. 对于每个递增序列，对其所有元素进行插入排序；

3. 当h=1排序完成后，整个数组即有序。

   
   1-2 希尔排序用例图

二、算法实现

public static void sort(Comparable[] a) {
    int n = a.length;
 
    // 产生一个递增序列:  1, 4, 13, 40, 121, 364, 1093, ... 
    int h = 1;
    while (h < n/3) h = 3*h + 1; 
   
   
    while (h >= 1) {
        // h-sort the array
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                exch(a, j, j-h);
            }
        }
        h /= 3;
    }
    assert isSorted(a);
}

三、性能分析

• 特点
  希尔排序是插入排序的变形应用，最优时间复杂度目前仍无法证明；
  对于一般大小的数组，可以采用希尔排序解决；
  希尔排序的困难之处在于递增序列h的选择，目前尚未有证明某个序列是最好的。
• 时间复杂度
  最坏情况：O( N^(3/2) )，无法确认其平均时间复杂度