插入排序 Insertion Sort

概述

寻找该元素的适当位置并插入
特点：

1. 如果input是已排序完的，消耗时间很少，只需要查看当前数字前一位。
2. 如果input为倒序，则耗费大量时间，遍历数组
3. 时间n^2

   图解过程

   

public void sort(int arr[])
    {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
 
            /* Move elements of arr[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }