algorithm - Θ(n lg n) 中的快速排序

标签 algorithm sorting code-analysis quicksort

<分区>

这是一个以程序员为生的人的问题 -
我刚刚证明(使用主定理)如果我们使用快速排序并且我们选择枢轴作为我们正在分区的子数组的中位数(使用具有 Θ(n) 最坏情况运行时间的中位数算法)那么最坏的case quicksort 的运行时间是 Θ(n lg n) - 所以基本上这意味着这个版本的 quicksort 已经尽可能好了。

我现在的问题是 - 有没有人在实践中实现这样的快速排序？或者它只是那些在现实生活中实际上并不好的理论中的一个？

PS - 我不需要证明我所说的内容，我只想知道这是否广为人知/有用

最佳答案

这是已知的(参见 wikipedia 条目)，但由于在实践中最坏的情况相对较少，因此通常认为 O(N) 选择算法在一般情况下增加的开销是 Not Acceptable 。

关于algorithm - Θ(n lg n) 中的快速排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16385550/