首页 > 试题广场 > 快速排序在已
[单选题]
快速排序在已经有序的情况下效率最差,复杂度为()

  • O(nlogn)
  • O(n^2)
  • O(n^1.5)

2个回答

添加回答
  • b
    发表于 2017-01-11 23:53:12 回复(0)
  • 更多回答
  • 快速排序的递归分治,可以将一个大数组切分成两部分,并可以在一个函数栈中处理独立的这两部分。当切分元素每次都刚好能将数组切分成两部分时,递归函数栈是最浅的 lgN 层,当元素以有序时,切分元素每次都只能分解一个空子序和一个包含 n-1 个元素的子序列,此时我们需要n-1此分解,即函数调用深度为 n - 1 层而每一层都进行若干次独立的切分(partiton)算法,时间复杂度为O(N)。 这时整个排序的时间复杂度就为: O(n * n)。



    发表于 2017-01-12 11:21:15 回复(0)
牛客网,程序员必备求职神器
QQ群:169195721
微 信:www_nowcoder_com 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋