插入排序

version 1

public static void sort(Comparable[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        // 寻找元素arr[i]合适的插入位置
        for (int j = i; j > 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) {
            swap(arr, j, j - 1);
        }
    }
}

插入排序和选择不排序不同的地方在于插入排序可以提前结束第二层循环，但是由于的每次执行一次交换(swap方法)都需要执行三次赋值，此时的插入排序性能会比选择排序略低

version 2

public static void sort(Comparable[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        Comparable e = arr[i];
        int j;
        for (j = i; j > 0 && arr[j - 1].compareTo(e) > 0; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = e;
    }
}

当数组更有序时，插入排序的性能更高

当数组为完全有序时，插入排序将进化为O(n)级别的算法

但是选择排序，不论什么情况，两层循环都必须要走完。

private static int partition(Comparable[] arr, int l, int r) {
    // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    swap(arr, l, (int)Math.random() * (r - l + 1) + l);
    Comparable v = arr[l];
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i].compareTo(v) < 0) {
            j++;
            swap(arr, j, i);
        }
    }
    swap(arr, l, j);
    return j;
}