直接插入排序：
什么是直接插入排序？
每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，直到全部插入完成。
通俗解释一波：
打牌为例：
先拿一张5在手里，
再摸到一张4，比5小，插到5前面，
摸到一张6，嗯，比5大，插到5后面，
摸到一张8，比6大，插到6后面，
。。。
嗯，等你最后一张牌插完，你发现所有牌都有顺序了（这个只对按顺序插牌的同学有效~~~~）
图片解释一波：
代码基本思路：
待排序记录 R1，R2，… ，Rn–1, Rn
第一步:R1
第二步:(R1 ), R2
第三步:(R1 , R2), R3
……
第 j 步:(R1，R2，… ，Rj–1), Rj
……
第 n 步: (R1，R2，… ，Rn–1), Rn.
例:j=5
原有序表中关键词比Rj大的记录数:dj
比较次数:dj+1 移动次数: dj+2
Java代码实现：
public class SortTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] sort = { 4, 5, 6, 7, 9 };
insertSort(sort);
}
public static void insertSort(int[] list) {
// 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
for (int i = 1; i < list.length; i++) {
int j = 0;
int temp = list[i]; // 取出第i个数，和前i-1个数比较后，插入合适位置
// 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
for (j = i - 1; j >= 0 && temp < list[j]; j--) {
list[j + 1] = list[j];
}
list[j + 1] = temp;
}
//处处排序后的结果
for (int i : list) {
System.out.println(i);
}
}
}
输入序列：
sort = { 4, 3, 6, 1, 9 };
输出结果：
1
3
4
6
9
算法性能分析：
时间复杂度：
当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。
当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N2)。
所以，数据越接近正序，直接插入排序的算法性能越好。
空间复杂度：
由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为1。
算法稳定性：
直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。
