依题意，最好情况下的比较次数即为最少比较次数。
⑴插入第i（2≤i≤n）个元素的比较次数为1，因此总的比较次数为：1+1+……+1=n-1
⑵插入第i（2≤i≤n）个元素的比较次数为i，因此总的比较次数为：2+3+……+n=（n-1）（n+2）/2
⑶比较次数最少的情况是所有记录关键码按升序排列，总的比较次数为：n-1
⑷在后半部分元素的关键码均大于前半部分元素的关键码时需要的比较次数最少，总的比较次数为：n-1
（简答题）
已知下列各种初始状态（长度为n）的元素，试问当利用直接插入排序进行排序时，至少需要进行多少次比较（要求排序后的记录由小到大顺序排列）？ ⑴关键码从小到大有序（key1< key2< …< keyn）。 ⑵关键码从大到小有序（key1> key2 >…> keyn）。 ⑶奇数关键码顺序有序，偶数关键码顺序有序（key1< key3< …，key2key4…）。 ⑷前半部分元素按关键码顺序有序，后半部分元素按关键码顺序有序，即：（key1< key2< …< keym，keym+1< keym+2 <…）
正确答案
答案解析
略
相似试题
（填空题）
对初始状态为递增有序的序列进行排序，最省时间的是（），最费时间的是（）。已知待排序序列中每个元素距其最终位置不远，则采用（）方法最节省时间。
（简答题）
已知长度为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。分两种情况编写函数： （1）线性表采用顺序存储； （2）线性表采用单链表存储。
（判断题）
为提高在外排序过程中，对长度为N的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。
（单选题）
对长度为n的单有序表，若查找每元素的概率相等，则查找任一元素的平均查找长度为（）
（单选题）
若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为（）
（单选题）
删除长度为n的顺序表中的第i（1≤i≤n）个位置上的元素，元素的移动次数为：（）
（填空题）
向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动（）个元素。
（单选题）
在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为：（）
（单选题）
在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n＋1），元素的移动次数为（）。
