单选题 在最好和最坏情况下的时间复杂度均为O(nlogn)，但不稳定的排序算法是{{U}} {{U}} {{/U}} {{/U}}。
  • A.堆排序
  • B.快速排序
  • C.归并排序
  • D.基数排序
【正确答案】 A
【答案解析】[解析] 各种排序算法最好时间复杂度、平均时间复杂度、最坏时间复杂度、辅助空间复杂度和稳定性比较如表3-6所示。
{{B}}表3-6 各种排序算法比较表{{/B}}
排序算法
最好时间复杂度
平均时间复杂度
最坏时间复杂度
辅助空间复杂度
稳定性
直接插入
O(n)
O(n2)
O(n2)
O(1)
稳定
直接选择
O(n2)
O(n2)
O(n2)
O(1)
不稳定
冒泡
O(n)
O(n2)
O(n2)
O(1)
稳定
希尔
—
O(n1.25)
—
O(1)
不稳定
堆
O(nlogn)
O(nlogn)
O(nlogn)
O(1)
不稳定
快速
O(nlogn)
O(nlogn)
O(n2)
O(logn)
不稳定
归并
O(nlogn)
O(nlogn)
O(nlogn)
O(n)
稳定
基数
O(d(n+rd))
O(d(n+rd))
O(d(n+rd))
O(n+rd)
稳定
由表3-6可知，堆排序在最好和最坏情况下的时间复杂度均为O(nlogn)但不稳定。
快速排序在最好和最坏情况下的时间复杂度分别为O(n2)和O(nlogn)但不稳定。
归并排序在最好和最坏情况下的时间复杂度均为O(nlogn)但稳定。
基数排序在最好和最坏情况下的时间复杂度均为O(d(n+rd)。