排序算法03：插入排序

算法介绍

步骤：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

排序演示：

插入排序

可视化效果：<a href="http://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html" >这里</a>

Javascript实现

/**
 * Created by YiYing on 2017/4/22.
 */
(function (W) {

    function Insertion(arr) {
        this.arr = arr;
    }

    /**
     * 插入排序算法实现
     */
    Insertion.prototype.sort = function () {
        var len = this.arr.length;
        for(var i=1;i<len;i++){
            //在已经有序之中，从后往前比对，依次交换，直到插入到正确的位置即可
            for(var j=i;j>0&&this.less(j,j-1);j--){
                this.exchange(j,j-1);
            }
        }
    };

    /**
     * 判断m是否小于n
     * @param m
     * @param n
     */
    Insertion.prototype.less = function (m,n) {
        //可根据不同的数据类型设置比对规则，比如json。这里适用于数字与字符串。
        return this.arr[m]<this.arr[n];
    };

    /**
     * 交换数组中m与n的位置
     * @param m
     * @param n
     */
    Insertion.prototype.exchange = function (m,n) {
        var swap    = this.arr[m];
        this.arr[m] = this.arr[n];
        this.arr[n] = swap;
    };

    /**
     * 打印排序后的数组
     */
    Insertion.prototype.show = function () {
        console.log(this.arr);
    };

    /**
     * 判断是否已排序
     * @returns {boolean}
     */
    Insertion.prototype.isSorted = function () {
        var len = this.arr.length;
        for(var i=1;i<len;i++){
            if(this.less(i,i-1)){
                return false;
            }
        }
        return true;
    };

    W.Insertion = Insertion;
})(window);

//测试代码
(function () {
    var arr = [4,5,6,0,3,5,21,7,9,0,1];
    var insertion = new Insertion(arr);
    console.log("排序前："+insertion.isSorted());
    insertion.sort();
    console.log("排序后："+insertion.isSorted());
    insertion.show();
})();

Java实现

package com.algs;

public class Insertion {

    /**
     * 插入排序实现逻辑
     * @param arr
     */
    public static void sort(int[] arr){
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            //在已经有序之中，从后往前比对，依次交换，直到插入到正确的位置即可
            for (int j = i; j>0&&less(arr[j], arr[j-1]); j--) {
                exchange(arr, j, j-1);
            }
        }
    }

    /**
     * 比较m是否小于n
     * @param m
     * @param n
     * @return
     */
    private static boolean less(int m,int n) {
        return m < n;
    }

    /**
     * 交换m与n的位置
     * @param a
     * @param m
     * @param n
     */
    private static void exchange(int[] a, int m, int n) {
        int swap = a[m];
        a[m] = a[n];
        a[n] = swap;
    }

    public static void show(int[] a){
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

    public static void main(String[] args) {
        int[] arr = {4,5,6,0,3,5,21,7,9,0,1};
        Insertion.sort(arr);
        Insertion.show(arr);
    }
}

总结

1. 稳定。相同元素排序后能保持排序前的相对顺序。
2. 原地排序。
3. 时间复杂度为：介于线性级别与平方级别之间。取决于输入元素的排列情况。
4. 空间复杂度为：常数级别。

GitHub：https://github.com/AlbertKnag/algs-practice

上一篇：<a href="http://muchstudy.com/2017/04/22/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%9502%EF%BC%9A%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F/">排序算法02：选择排序</a>
下一篇：<a href="http://muchstudy.com/2017/04/23/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%9504%EF%BC%9A%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/">排序算法04：希尔排序</a>