首页 > 试题广场 >

以下哪个排序算法的时间复杂度在最差情况下是O(n2)

[单选题]
以下哪个排序算法的时间复杂度在最差情况下是O(n2)
  • 快速排序
  • 归并排序
  • 堆排序
  • 其他选项都是
排序方法     平均时间     最好时间     最坏时间
桶排序(不稳定)     O(n)     O(n)     O(n)
基数排序(稳定)     O(n)     O(n)     O(n)
归并排序(稳定)     O(nlogn)     O(nlogn)     O(nlogn)
快速排序(不稳定)     O(nlogn)     O(nlogn)     O(n^2)
堆排序(不稳定)     O(nlogn)     O(nlogn)     O(nlogn)
希尔排序(不稳定)     O(n^1.25)           
冒泡排序(稳定)     O(n^2)     O(n)     O(n^2)
选择排序(不稳定)     O(n^2)     O(n^2)     O(n^2)
直接插入排序(稳定)     O(n^2)     O(n)     O(n^2)
发表于 2018-12-04 21:08:52 回复(0)
快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
科学家数学证明,长期期望的时间复杂度为O(logN*N)。,最差情况下是O(n^2)
发表于 2018-11-15 15:36:41 回复(0)