插入排序

介绍

插入排序的工作方式像排序一手扑克牌，开始时，我们的左手为空并且桌子上的牌向下，然后我们我们每次从桌子上拿走一张牌并且插入到正确的位置，我们从右往左将它与手中的牌进行比较
如图：

插入排序扑克

原理

插入排序将数列分为有序和无序两个部分，每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中

简略图

简单的来说，蓝色是手中已经排好序的牌，黑色是盖在桌子上的牌， i 是刚从桌子上拿起的牌准备插入手中，依次右往左将它与手中的牌进行比较

Example of insertion sort

python描述

array = [1, 3, 4, 5, 2, 8, 6, 7]
for i in range(1, len(array)):
   tmp = array[i]
   while i > 0 and array[i-1] > tmp:
       array[i] = array[i-1]
       i -= 1
   array[i] = tmp

java 描述

public class Insertion {
    
    // 实现了Comparable接口的都可以比较
    public static void sort(Comparable[] a){
        int N = a.length;
        for (int i = 1; i < N; i++){
            Comparable temp = a[i];
            while( i > 0 && less(temp, a[i-1])){
                a[i] = a[i-1];
                i--;
            }
            a[i] = temp;
        }
    }
    
    public static void main(String[] args) {
        Integer[] a = {2, 3, 1, 3, 4, 8, 6, 10};
        sort(a);
        assert isSorted(a);
        show(a);
    }
    
    public static boolean less(Comparable V , Comparable W){
        return V.compareTo(W) < 0;
    }
    
    public static void exch(Comparable[] a, int i, int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    public static void show(Comparable[] a){
        for (int i = 0; i < a.length; i++){
            System.out.print(a[i] + " ");   
        }
        System.out.println();
    }
    
    // 测试数组元素是否有序
    public static boolean isSorted(Comparable[] a){
        for (int i = 1; i < a.length; i++){
            if(less(a[i], a[i-1])){
                return false;
            }
        }
        return true;
    }
}

选出当前要排序的牌，从右往左比较，如果手中的牌的序号大于0（i > 0）并且手中的牌比当前要插入的牌更大，就把当前的牌像右挪一个位置，最后再把这张牌插入其中

算法分析

(n-1) + (n-2) + ... + 1 = n(n-1)/2 平均来说插入排序算法的时间复杂度为O(n²)

稳定性

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的