1.执行流程

先通过一个例子来体会一下插入排序的执行流程。例如，对原始序列{49，38，65，97，76，13，27，49}进行插入排序的具体流程如下（序列中有两个49，其中一个加下划线，加以区分）。

原始序列：49 38 65 97 76 13 27 49

1）一开始只看49，一个数当然是有序的。

49 38 65 97 76 13 27 49

2）插入38。38＜49，所以49向后移动一个位置，38插入到49原来的位置，这趟排序后的结果为：

38 49 65 97 76 13 27 49

3）插入65。65＞49，所以不需要移动，65就应该在49之后，这趟排序后的结果为：

38 49 65 97 76 13 27 49

4）插入97。97＞65，所以不需要移动，97就应该在65之后，这趟排序后的结果为：

38 49 65 97 76 13 27 49

5）插入76。76＜97，所以97向后移动一个位置；继续比较，76＞65，65不需要移动，76应该插入在65之后、97之前，这趟排序后的结果为：

38 49 65 76 97 13 27 49

6）插入13。13＜97，97后移；13＜76，76后移；这样逐个向前比较，发现13应该插入在最前面，这趟排序后的结果为：

13 38 49 65 76 97 27 49

7）插入27。还是从后向前进行比较，确定27应该插入在13之后、38之前，这趟排序后的结果为(www.daowen.com)

13 27 38 49 65 76 97 49

8）最后插入49，同样从后向前逐个比较，直到49=49＜65，它的位置确定，直接插入排序全过程完成。最后的排序结果为：

13 27 38 49 49 65 76 97

2.算法思想

根据上述例子可以总结出直接插入排序的算法思想：每趟将一个待排序的关键字按照其值的大小插入到已经排好的部分有序序列的适当位置上，直到所有待排关键字都被插入到有序序列中为止。

由此可以写出直接插入排序的算法代码：

3.算法性能分析

（1）时间复杂度分析

由插入排序算法代码，可以选取最内层循环中的R[j+1]=R[j]；这一句作为基本操作。

1）考虑最坏的情况，即整个序列是逆序的，则内层循环中temp＜R[j]这个条件是始终成立的。此时对于每一次外层循环，最内层循环的执行次数（也是基本操作的执行次数）达到最大值，为i次（如当外层循环进行到i等于5时，内层循环j取从4到0，执行5次）。i取值为1到n-1，由此可得基本操作总的执行次数为n（n-1）/2，可以看出时间复杂度为O（n²）。

2）考虑最好的情况，即整个序列已经有序，则对于内层循环中temp＜R[j]这个条件是始终不成立的。此时内层循环始终不执行，双层循环就变成了单层循环，循环内的操作皆为常量级，显然时间复杂度为O（n）。

综合上述两种情况，本算法的平均时间复杂度为O（n²）。

（2）空间复杂度分析

算法所需的辅助存储空间不随待排序列规模的变化而变化，是个常量，因此空间复杂度为O（1）。

说明：对于直接插入排序，一趟排序后并不能确保使一个关键字到达其最终位置。考虑这样的序列：1、2、3、4、5、0，对这个序列进行直接插入排序，在最后插入0时，前面5个数都要向后移动，所以在最后一趟排序前，这个序列没有任何一个关键字到达其最终位置。这是插入类排序算法的共同特点。