当待排序文件按关键字非递增有序逆序) 时 据结构 >记录r[j(=2,3,n)均要和前i-1个记录及r0进 行比较,整个排序过程共进行了 ∑i=(n+2)(n-1)/2次比较(最多); 移动记录次数:每个记录都要进行r订移动到 r0和r移动到r+1两次移动,另外当 内部排序 r[ i-key< rIil. key时,还将r移动到r+1, 所以,当初始文件为逆序时移动记录次数最 多,为 ∑(i-1)+2(n-1)=(n+4)(n-1)2次(最多) 13 数据结构 结论 直接插入排序的效率与待排文件的关 键字排列有关; >直接插入排序的时间复杂度为O(n2); 直接插入排序是稳定的这一点由过程 内部排序 中WHIE语句的条件“<”保证的)。 147 数 据 结 构 之 内 部 排 序 13 ¾当待排序文件按关键字非递增有序(逆序) 时 ¾记录r[i](i=2,3,...n)均要和前i-1个记录及r[0]进 行比较，整个排序过程共进行了 n ∑ i=(n+2)(n-1)/2次比较(最多)； i=2 ¾移动记录次数：每个记录都要进行r[i]移动到 r[0]和r[0]移动到r[j+1]两次移动，另外当 r[i].key＜r[j].key时，还将r[j]移动到r[j+1]， 所以，当初始文件为逆序时移动记录次数最 多, 为 n ∑ (i-1)+2(n-1)=(n+4)(n-1)/2次(最多)。 数 据 结 构 之 内 部 排 序 14 ¾结论 ¾直接插入排序的效率与待排文件的关 键字排列有关； ¾直接插入排序的时间复杂度为O(n2)； ¾直接插入排序是稳定的(这一点由过程 中WHILE语句的条件“＜”保证的)