从移动记录的次数来看,每趟排序中除了上面提到的两 次移动外,还需将有序子序列中关键字值大于待排序记 录的关键字值的记录后移一个位置,总的移动次数为: ∑(+1)=(n+4)(n-1)/2 故其时间复杂度为O(n2) 若在随机情况下,设待排序记录序列可能出现的各 种排列的概率相同,则可取上述两种极端情况的平均值 作为比较和移动记录的平均次数,约为n2/4.由此,直 接插入排序的时间复杂度为Omn2) 直接插入排序是稳定的排序方法 对于直接插入排序,补充一C函数,其功能为:将 以带头结点的单链表存储的一组无序记录,排序成非递 减序列从移动记录的次数来看, 每趟排序中除了上面提到的两 次移动外, 还需将有序子序列中关键字值大于待排序记 录的关键字值的记录后移一个位置, 总的移动次数为: ( 1) ( 4)( 1)/ 2 2  + = + − = i n n n i 故其时间复杂度为 ( ). 2 O n 若在随机情况下, 设待排序记录序列可能出现的各 种排列的概率相同, 则可取上述两种极端情况的平均值 作为比较和移动记录的平均次数, 约为 /4 2 n . 由此, 直 接插入排序的时间复杂度为 ( ). 2 O n 直接插入排序是稳定的排序方法. 对于直接插入排序, 补充一C函数, 其功能为: 将 以带头结点的单链表存储的一组无序记录, 排序成非递 减序列