微信刷题,考证常用
  • 试题题型【选择题】
试题内容
下列排序法中,最坏情况下时间复杂度最小的是
  • A. 冒泡排序
  • B. 堆排序
  • C. 快速排序
  • D. 希尔排序
  • 参考答案:B
  • 解题思路:对长度为n的线性表,下表为常用排序算法最坏情况下比较次数:
    image.png
    上表中未包含希尔排序,因为希尔排序的时间效率与所取的增量序列有关,如果增量序列为d ₁=n /2,di+1= di/2,在最坏情况下,希尔排序所需要的比较次数为O(n1.5)。由表格可知,冒泡排序与快速排序比较次数相同,故最坏情况下时间复杂度最小的是堆排序。本题选B。