Java 插入排序

Insertion.java

public class Insertion {
  public static void sort(Comparable[] a) {
    int N = a.length;
    // 从第二个元素开始操作
    for (int i = 1; i < N; i++) {
      // 索引之前的所有元素, 从右往左, 一个个进行比较, 如果后一个比前一个小, 则交换相邻的两个元素
      for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
        exch(a, j, j-1);
      }
    }
  }

  // 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 void main(String[] args) {
    Comparable[] a = Utils.generateRandomIntArray(100, 0, 100);
    sort(a);
    assert isSorted(a);
  }
}

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;
  }
}