直接插入排序：

什么是直接插入排序？

每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，直到全部插入完成。

通俗解释一波：

打牌为例：

先拿一张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。

算法稳定性：

直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。