算法简洁、容易实现是直接插入排序的两大特点, 下面分析其时间效率 整个排序过程中只有比较关键字和移动记录两种运 算.当原始记录已按关键字非递减有序,即为正序时, 时间效率最高,因完成每趟排序仅需进行一次比较及两 次移动记录操作(即开始时将记录移至监视哨中和最后将 记录移入适当位置,整个排序过程总的比较次数为n-1, 记录总的移动次数为(m-1,故其时间复杂度为Omn); 反之,如果原始记录是按关键字非增减有序的,即为 逆序时,时间效率最低,因要插入的第个记录,均要与 前i-1个记录及监视哨的关键字进行比较,即每趟要进行 i次比较,总的比较次数为: ∑i=(n+2)(n-1)/2算法简洁﹑容易实现是直接插入排序的两大特点, 下面分析其时间效率. 整个排序过程中只有比较关键字和移动记录两种运 算. 当原始记录已按关键字非递减有序, 即为正序时, 时间效率最高, 因完成每趟排序仅需进行一次比较及两 次移动记录操作(即开始时将记录移至监视哨中和最后将 记录移入适当位置), 整个排序过程总的比较次数为n-1, 记录总的移动次数为2(n-1), 故其时间复杂度为O(n); 反之, 如果原始记录是按关键字非增减有序的,即为 逆序时, 时间效率最低, 因要插入的第i个记录, 均要与 前i –1个记录及监视哨的关键字进行比较, 即每趟要进行 i次比较, 总的比较次数为: ( 2)( 1)/ 2 2  = + − = i n n n i