首页 > 试题广场 >

快速排序在已

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

  • O(nlogn)
  • O(n^2)
  • O(n^1.5)
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)
最差的时候就是冒泡法排序,选择B最好情况是A
发表于 2017-03-11 23:16:37 回复(0)