实现外壳排序

//来 自 N o w  J a v a  .   c o m



class Shell {


  public static void sort(Comparable[] a) {

    int N = a.length;

    int h = 1; // boundary subarray


    while (h < N / 3)

      h = 3 * h + 1; // 1, 4, 13, 40 ...


    while (h >= 1) {
    /* 
    *来 自
     时代Java公众号 - N o w J a  v a . c o m
    */

      for (int i = h; i < N; i++) {

        // insertion sort

        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 swap = a[i];

    a[i] = a[j];

    a[j] = swap;

  }


  public static void main(String[] args) {

    Integer[] data = new Integer[] { 9