对有n个元素的顺序表进行直接插入排序,在最坏情况下需比较______ 次关键字。
A. n-1
B. n+1
C. n/2
D. n(n-1)/2
若是默认情况下需要排序得到递增的一个序列,那么初始序列为递减序列时,直接插入排序比较次数最多的一种情况,即最坏情况。
n个元素,第一个元素往往是不需要进行比较的(因为它前面没有可以给它进行比较的元素了),直接占据第一个位置。
到了第二个及以后的元素时,需要与前面相邻的元素依次进行比较(直到找到一个小于或等于它的元素时候停止,然后占据该元素的后一个位置,后面的元素再往后挪一位;或是比较完了最前面的元素还没有找到小于等于它的元素,那么它就占据第一个位置,使得之后的元素往后挪一个位置)。
第二个元素前面只有一个,那么无论如何仅需要比较1次即可;
第三个元素前面有2个元素,那么在最坏情况下(初始序列递减),前面是找不到小于等于它的(如果能找到就不是最坏的了,别想着存在相等元素的这种情况),这样就需要比较2次即可;
到了这里,那么你聪明的脑袋瓜子应该能感受到规律了吧,又是一个等差数列求和。
第四个元素前面有3个,最多比较3次;
依次类推......那么第i个元素所需要比较的次数是不是i-1。
即总数Sn = 0 + 1 + 2 + ... + n-1 = ( n / 2 ) * ( 0 + n - 1 )。
整理一下即可得到D选项。
(希望对你有所帮助~~)
D
用户登录可进行刷题及查看答案
登录后提交答案