92插入排序 2.当待排序文件按关键字非递增有序(逆序)时 ①记录r(i=2,3,n)均要和前i-1个记录及r进行比较,整个 排序过程共进行了 i=(n+2)(n-1)2次比较最多); ②移动记录次数:每个记录都要进行r移动到r0和r0移动 到rj+1两次移动,另外当 rl.key< rij- key时,还将rj移 动到r+1,所以,当初始文件为正序时,移动记录次数最 少为2(n-1)次,当初始文件为逆序时移动记录次数最多为 (-1)+2(m1)(n+4(m1/2次(最多9.2 插入排序 2/. 当待排序文件按关键字非递增有序(逆序)时 ① 记录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]，所以，当初始文件为正序时，移动记录次数最 少为2（n-1）次，当初始文件为逆序时移动记录次数最多为 n ∑ (i-1)+2(n-1)=(n+4)(n-1)/2次(最多)。 i=2