插入排序：构建有序序列，对于未排序数据，在已排序序列中从后（右）往前（左）扫描，找到相应位置并插入

实现

1
2
3
4
5
6
7
8
9
10
public class Insertion {
    public static void sort(Comparable[] c) {
        int l = c.length;
        for (int i = 1; i < l; i++) {
            for (int j = i; j > 0 && less(c[j], c[j - 1]); j--) {
                exch(c, j, j - 1);
            }
        }
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String[] args) {
    Comparable[] random = new Comparable[20];
    for (int i = 0; i < 20; i++) {
        random[i] = RandomUtils.nextInt(1, 100);
    }
    sort(random);
    for (int i = 0; i < 20; i++) {
        System.out.print(random[i]);
        if (i != random.length - 1) {
            System.out.print(" | ");
        }
    }
    isSorted(random);
}