1、直接插入排序（时间复杂度O(n^2) 空间复杂度O(1)）
原理：1、假设有n个未排序的数，任选其中一个(一般是第一个)放入已排序集合，其余元素属于未排序集合。
2、从未排序集合中任选一个数N（一般是第一个），与已排序集合里的元素M比较 ，如果N小于M，则M向后移动一个位置，将N插在M前面，反之，将N插在M后面
3、此时已排序集合里已经有多个数(大于等于2)，此时从未排序集合中再取一个数，从右往左依次与已排序集合中的元素比较，比较后的操作参见2.
4、依次类推，直到未排序集合中没有元素。
2、
原文：http://www.cnblogs.com/wshyj/p/6341647.html