《算法 第四版》算法5--希尔排序的实现

希尔排序

-自然语言描述：

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 d _t = 1(d_t < d_t-1…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

-Java语言实现：

  public static void sort(Comparable[] a){
    int N = a.length;
    int h = 1;
    while (h < N/3) h = 3*h + 1;
    while (h >= 1){
        for(int i = h; i < N; i++){
            for(int j = i; j>=h&&(a[j] <a[j-1]);j -=h){
                Comparable temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp; 
          }
      }
   h = h/3;
    }
  }

-验证代码：

  public class Shell {
    public static void sort(Comparable[] a){
        //升序
        int N = a.length;
        int h = 1;
        while (h < N/3) h = 3*h + 1;
        while (h >=1 ){
            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 = h/3;
        }
}
private static boolean less(Comparable v, Comparable w){ return v.compareTo(w) < 0; }


private static void exch(Comparable[] a, int i, int j){ 
    Comparable t = a[i]; a[i] = a[j]; a[j] = t; }
    private static void show(Comparable[] a){ // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
        System.out.print(a[i] + " ");
        System.out.println();
    }

    public static boolean isSorted(Comparable[] a){
        int length = a.length;
        for (int i = 1;i < length ;i++ ) {
            if (less(a[i],a[i -1])) {
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}