Java 实现希尔排序

Shell.java

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) {
  }
}

Utils.java

public class Utils {
  private static class A implements Comparable {
    private int val;

    A(int v) {
      val = v;
    }

    int getVal() {
      return val;
    }

    @Override
    public int compareTo(Object o) {
      return this.val - ((A) o).getVal();
    }

    @Override
    public String toString() {
      return val + "";
    }
  }

  // 产生随机大小的 int 数组
  public static Comparable[] generateRandomIntArray(int len, int min, int max) {
    Comparable[] arr = new Comparable[len];
    for (int i = 0; i < len; i++) {
      arr[i] = new A(min + (int) (Math.random() * (max - min) + 1));
    }
    return arr;
  }
}