已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?
问答题
关键字自小到大有序(key
1
＜kye
2
＜…＜key
n
)；
【正确答案】正确答案：本题主要考查直接插入法的算法思想及性能分析。 根据题目所给出的条件，最好情况下的比较次数即为最少比较次数。 在关键字自小到大有序的情况下，插入第i个(2≤i≤n)元素的比较次数为1，因此，总的比较次数为1+1+1+…+1=n—1。
【答案解析】
问答题
关键字自大到小逆序(key
1
＞key
2
＞…＞key
n
)；
【正确答案】正确答案：在关键字自大到小有序的情况下，插入第i个(2≤i≤n)元素的比较次数为i，因此，总的比较次数为2+3+4+…+n=[n(n+1)／2]一1=(n—1)(n+2)／2。
【答案解析】
问答题
奇数关键字顺序有序，偶数关键字顺序有序(key
1
＜key
3
＜…，key
2
＜key
4
＜…)；
【正确答案】正确答案：在奇数关键字顺序有序和偶数关键字顺序有序的情况下，比较次数最少的情况是所有记录关键字均按升序排列，这时，总的比较次数为n一1。
【答案解析】
问答题
前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key
1
＜key
2
＜…＜key
m
，key
m+1
＞key
m+2
＞…＞key
n
，m为中间位置)。
【正确答案】正确答案：在前半部分元素按关键字有序，后半部分按关键字逆序的情况下，后半部分元素的关键字均大于前半部分元素的关键字较次数最少，此时前半部分的比较次数为m一1，后半部分的比较次数为(n一m一1)(n—m+2)／2，因此，总的比较次数为m一1+(n一m一1)(n一m，m+2)／2=(n-1)(n+8)／8(假设n为偶数，m=n／2)。
【答案解析】