寻找澄清快速排序的算法复杂

Question

有人能解释为什么快速排序的最好情况运行时不是线性的？有没有办法使quicksort linear的最佳运行时间？如果是这样，为什么他们通常不用于实践？

Answer 1

你应该至少通过维基链接已经消失了......他们都与图ñ动画这是很容易理解这种解释。

http://en.wikipedia.org/wiki/Quicksort

Answer 2

快速排序运行在为O（n 2 ）时间最坏的情况下，但最好/平均为O（n log n）的。尽管它的最坏情况更严重，但它在实践中表现优于排序和合并排序（最差情况下的O（nlogn）排序）。

排序只能在线性时间内运行，除非它们已经排序，并且这仅适用于排序的最好情况为O（n），如insertion sort。

Answer 3

当然，你可以先检查输入是否已排序，并立即返回，如果它是。这产生了具有线性最佳情况复杂度的算法。但是最后你会得到一个“Modified Quicksort”而不是“Quicksort”。

Answer 4

快速排序是直接比较分选方法。每个这样的方法在每个步骤上使用二元决策（即直接比较）以在分类的两个可能结果之间分支。所有可能的N个元素数组的排序都是N！并且因此能够输出这些结果中的每一个的二叉决策树的最低高度是log（N！），但可以证明，尽管O（log（N！））= O（N *日志（N））。所以没有直接比较排序算法可能比这个算法复杂得多。

因此，如快速排序是这样的算法的一个例子其可以从不具有比O（N *日志（N））的复杂性较低，所以它不能是线性的。