插入排序

相信扑克牌大家都玩过，当随机发给你一捋扑克牌，你会先将牌理好，然后再想一下这手牌的好坏。那你会怎样将这捋扑克牌理好呢？

这时你可以借助「插入排序」的算法思想：从最后一张牌开始看，看这张牌之前的牌比它大还是小，如果前面的牌比它大（假设进行升序排序），那就继续往前看一张，直到看到第一张比它小的牌。此时你就可以将它插在比它小的牌后边。如果发现看到这捋牌的第一张，发现每张都比它大，那说明它是最小的，直接插在第一张的位置就好了。插好这张牌的位置后，继续从后往前看下一张牌，重复上述步骤，直到最后一张牌看完为止。

public class InsertionSort {

    private InsertionSort() {
    }

    // 对 arr 数组使用 InsertionSort 排序
    public static void sort(Comparable[] arr) {
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            Comparable e = arr[i];
            int j = i;

            for (; j > 0 && arr[j - 1].compareTo(e) > 0; j--)
                arr[j] = arr[j - 1];
            arr[j] = e;
        }
    }

    // 对 arr[l...r] 的区间使用 InsertionSort 排序
    public static void sort(Comparable[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            Comparable e = arr[i];
            int j = i;

            for (; j > l && arr[j - 1].compareTo(e) > 0; j--)
                arr[j] = arr[j - 1];
            arr[j] = e;
        }
    }
}