要点

直接插入排序是一种最简单的插入排序。

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

在讲解直接插入排序之前，先让我们脑补一下我们打牌的过程。

先拿一张5在手里，

再摸到一张4，比5小，插到5前面，

摸到一张6，嗯，比5大，插到5后面，

摸到一张8，比6大，插到6后面，

。。。

最后一看，我靠，凑到全是同花顺，这下牛逼大了。

以上的过程，其实就是典型的直接插入排序，每次将一个新数据插入到有序队列中的合适位置里。

很简单吧，接下来，我们要将这个算法转化为编程语言。

假设有一组无序序列 R0, R1, ... , RN-1。

(1) 我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。

(2) 然后，我们要依次把 R1, R2, ... , RN-1 插入到这个有序序列中。所以，我们需要一个外部循环，从下标 1 扫描到 N-1 。

(3) 接下来描述插入过程。假设这是要将 Ri 插入到前面有序的序列中。由前面所述，我们可知，插入Ri时，前 i-1 个数肯定已经是有序了。

所以我们需要将Ri 和R0 ~ Ri-1 进行比较，确定要插入的合适位置。这就需要一个内部循环，我们一般是从后往前比较，即从下标 i-1 开始向 0 进行扫描。

核心代码

public voidinsertSort(int[]list){
 //打印第一个元素
 System.out.format("i=%d:	",0);
 printPart(list,0,0);
 
 //第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
  for(inti=1;i<list.length;i++){
 intj=0;
 inttemp=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;
 
 System.out.format("i=%d:	",i);
 printPart(list,0,i);
 }
 }

算法分析

直接插入排序的算法性能

时间复杂度

当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。

当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N2)。

所以，数据越接近正序，直接插入排序的算法性能越好。

空间复杂度

由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 1 。

算法稳定性

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

完整参考代码

JAVA版本

代码实现

1 packagenotes.javase.algorithm.sort;
 2 
 3 importjava.util.Random;
 4 
 5 public classInsertSort{
 6 
 7 public voidinsertSort(int[]list){
 8 //打印第一个元素
 9System.out.format("i=%d:	",0);
 10printPart(list,0,0);
 11 
 12 //第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
 13 for(inti=1;i<list.length;i++){
 14 intj=0;
 15 inttemp=list[i];//取出第i个数，和前i-1个数比较后，插入合适位置
 16  
 17  //因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
 18 for(j=i-1;j>=0&&temp<list[j];j--){
 19list[j+1]=list[j];
 20}
 21list[j+1]=temp;
 22 
 23System.out.format("i=%d:	",i);
 24printPart(list,0,i);
 25}
 26}
 27 
 28 //打印序列
 29 public voidprintPart(int[]list,intbegin,intend){
 30 for(inti=0;i<begin;i++){
 31System.out.print("	");
 32}
 33 for(inti=begin;i<=end;i++){
 34System.out.print(list[i]+"	");
 35}
 36System.out.println();
 37}
 38 
 39 public static voidmain(String[]args){
 40 //初始化一个随机序列
 41 final intMAX_SIZE=10;
 42 int[]array=new int[MAX_SIZE];
 43Randomrandom=newRandom();
 44 for(inti=0;i<MAX_SIZE;i++){
 45array[i]=random.nextInt(MAX_SIZE);
 46}
 47 
 48 //调用冒泡排序方法
 49InsertSortinsert=newInsertSort();
 50System.out.print("排序前:	");
 51insert.printPart(array,0,array.length-1);
 52insert.insertSort(array);
 53System.out.print("排序后:	");
 54insert.printPart(array,0,array.length-1);
 55}
 56}

运行结果

排序前:6335631064
 i=0:6
 i=1:36
 i=2:336
 i=3:3356
 i=4:33566
 i=5:333566
 i=6:1333566
 i=7:01333566
 i=8:013335666
 i=9:0133345666
 排序后:0133345666

参考资料

《数据结构习题与解析》（B级第3版）

http://www.cnblogs.com/huangxincheng/archive/2011/11/20/2255695.html

要点