插入排序

核心代码

    public static void sort(Comparable[] a) {
        //将a[]按升序排列
        int N = a.length;
        for (int i = 1; i < N; i++) {
            //将a[i]刺插入到a[i-1]、a[i-2]······之中
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }
    }

Tips:

• 插入排序的运行时间是平方级别的，不需要额外的存储空间
• 插入排序的核心思想：对于1到N-1之前的每一个i,将a[i]与a[0]到a[i-1]中比它小的所有元素一次有序的交换，在索引i由左到右变化的过程中，它左侧的元素总是有序的，所以i到达数组的右端时排序就完成了，其实就是如同拿到一副牌，理牌的过程，但每次只能一张一张来
• 插入排序对于部分有序的数组十分高效，也很适合小规模数组