四、插入排序算法

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度。是稳定的排序方法。

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

  以上是百度百科对插入排序的定义，看得我云里雾里，直接忽略以上解释，下面用一张图表示插入排序。

简单了解插入排序

  这就是插入排序，用0表示初始位置，从第一位开始，往左边比较，把该元素放到合适的位置，其他元素后移，走完这个数组的时候，排序就完成了！举个完整的例子：

插入排序完整流程

  和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多

  上代码，由于《算法第4版》中的插入排序比较简陋，且性能不优，下面的代码是改造过的，有兴趣的可以对照看下有什么区别。

    //测试入口
    public static void main(String[] args) {
        Comparable[] arr = {3, 2, 1,-2,-9,4,8,2,9,4,-67,-12,12,67};
        System.out.print("初始数据：");
        show(arr);
        sort(arr);
    }

    /**
     * @param a 一个数组
     */
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 1; i < N; i++) {//从第二位开始比较，到i=n-1时排序完成
            //i表示当前需要排序的下标

            //插入位置标记
            int mark = i;
            //j表示左边数字的下标，依次比较
            for (int j = i-1; j >=0 && less(a[i], a[j]); j--)//如果比左边的数字小，就记录下这个位置
                //记录下需要插入的下标位置
                mark = j;

            Comparable num = a[i];
            //往左比较完毕后。将其他元素后移
            for (int m = i - 1; m >= mark; m--)//
                a[m + 1] = a[m];
            //将当前值插入到合适的地方
            a[mark] = num;
            System.out.print("第"+i+"次排序：");
            show(a);
        }
    }

    /**
     * 左边的数字比右边的小吗？
     *
     * @param v
     * @param w
     * @return
     */
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

     /**
     * 打印数组
     *
     * @param a
     */
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

运行程序：

打印结果

  总的来说，插入排序对于部分有序的数组十分高效，也很适合小规模数组。这很重要，因为这些类型的数组在实际应用中经常出现，而且它们也是高级排序算法的中间过程。我们会在学习高级排序算法时再次接触到插入排序。

---

  本系列所有的代码都会在github同步更新，立刻前往