问题
问答题
已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)。
前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序。
(key1＜key2＜……＜keym，keym+1＞keym+2＞……＞keyn，m为中间位置)。
答案
参考答案：在这种情况下，后半部分元素的关键字均大于前半部分元素的关键字时需要比较次数最少，此时前半部分的比较次数=m-1，后半部分的比较次数=(n-m-1)*(n-m+2)/2，因此，总的比较次数为m-1+(n-m-1)*(n-m+2)/2=(n-2)(n+8)/8(假设n偶数，m=n/2)。
解析： 本题主要考查直接插入法的算法思想及性能分析。