试题详情
简答题已知下列各种初始状态（长度为n）的元素，试问当利用直接插入排序进行排序时，至少需要进行多少次比较（要求排序后的记录由小到大顺序排列）？ ⑴关键码从小到大有序（key1< key2< …< keyn）。 ⑵关键码从大到小有序（key1> key2 >…> keyn）。 ⑶奇数关键码顺序有序，偶数关键码顺序有序（key1< key3< …，key2key4…）。 ⑷前半部分元素按关键码顺序有序，后半部分元素按关键码顺序有序，即：（key1< key2< …< keym，keym+1< keym+2 <…）
  • 依题意，最好情况下的比较次数即为最少比较次数。
    ⑴插入第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

  • 关注下方微信公众号，在线模考后查看

热门试题