import java.util.Date;

public class Shell {
  public static void sort(Comparable[] a) {
    // 希尔排序:
    // 是基于插入排序的,
    // 使数组中, *任意* 每隔 h 是有序的,
    // 当 h=1 时, 整个数组都是有序的
    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;
    }
  }

  // v 是否比 w 小 ? 如果返回 true: v < w
  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) {
    for (int i = 1; i < a.length; i++) {
      if (less(a[i], a[i - 1])) {
        return false;
      }
    }
    return true;
  }

  public static long timeRandomInput(int len, int count) {
    long total = 0;
    Comparable[] a;
    for (int i = 0; i < count; i++) {
      a = Utils.generateRandomIntArray(len, 0, len - 1);
      long start = (new Date()).getTime();
      sort(a);
      total += ((new Date()).getTime()) - start;
    }
    return total;
  }

  public static void main(String[] args) {
  }
}