直接插入排序的时间复杂度
从上述排序过程可见，排序中的两个基本操作是：（关键字间的）比较和（记录的）移动。因此排序的时间性能取决于排序过程中这两个操作的次数。从直接插入排序的算法可见，这两个操作的次数取决于待排记录序列的状态，当待排记录处于"正序"(即记录按关键字从小到大的顺序排列)的情况时，所需进行的关键字比较和记录移动的次数最少，反之，当待排记录处于"逆序"(即记录按关键字从大到小的顺序排列)的情况时，所需进行的关键字比较和记录移动的次数最多，如下表所列。
|
待排记录序列状态
|
"比较"次数
|
"移动"次数
|
|
正序
|
n-1
|
0
|
|
逆序
|
 |
 |
若待排记录序列处于随机状态，则可以最坏和最好的情况的平均值作为插入排序的时间性能的量度。一般情况下，直接插入排序的时间复杂度为O (n2)。
"移动记录"的次数包括监视哨的设置。
先分析一趟直接插入排序的情况：
若 L.r[i].key≥L.r[i-1].key，只进行"1"次比较，不移动记录；
若 L.r[i].key＜L.r[1].key，需进行"i"次比较，i+1次移动。
整个插入排序的过程中，i从2至 n，则得
