开发者社区 问答 正文

如果所有关键字都相等,那么插入排序算法的时间复杂度为

A. O(1) B.O(n) C. O(nlogn) D.O(n2)

展开
收起
知与谁同 2018-07-20 15:47:00 1869 分享 版权
1 条回答
写回答
取消 提交回答
  • 阿里云开发者社区运营负责人。原云栖社区负责人。
    B
    插入排序的核心思想是把第i个数插入前i-1个有序序列中。第i个数在和第i-1个数比较时,发现自己比前一个数要大(或相等),则自己是前i-1个数中的最大值。此时,前i个数是有序序列。
    所以,依此比较需要比较n-1次,即时间复杂度为O(n).
    2019-07-17 22:49:26
    赞同 展开评论
问答分类:
问答地址: