今天我们来学习一下插入排序，言简意赅的来说就是，每一步都将一个待排数据按照其大小插入到已经排序的数据中的适当位置，算法导论里是用扑克牌来举例的，你每抓起一张牌都会放到适当的位置，也就是从摸牌开始到最后，你手里的牌是排好序的（大多数情况。）

wikipedia上是这样介绍的，插入排序都采用in-place在数组上实现的。具体算法描述如下：

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

如果比较操作的代价比交换操作大的话，可以采用二分法搜索算法来减少比较操作的数目，该算法可以认为是插入排序的一个变种，称为二分查找插入排序。

java代码实现：

1
2
3
4
5
6
7
8
9
10
11
public static void insertionSort( int[] arr ) {
    for( int i=0; i<arr.length-1; i++ ) {	
        for( int j=i+1; j>0; j-- ) {
            if( arr[j-1] <= arr[j] )
                break;
            int temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
        }
    }
}