在O（n log n）中位的QuickSort
我真的不明白为什么我们不总是选择中值元素作为枢轴。这可以在 O(n) 内完成，因此总运行时间为 O(n log n)。
我只是假设中值搜索的 O(n) 中可能隐藏着一个大常数。
I don't really understand why we don't just always select the median element as the pivot. This can be done in O(n) and thus results in a total run time of O(n log n).
I just assume that probably there is a large constant hidden in the O(n) for the median search.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
从维基百科快速排序页面：
换句话说，强制其保证 O(n log n) 的成本一般来说是不值得付出的。该页面以及选择算法页面上有更多信息。
From the Wikipedia Quicksort page:
In other words, the cost of forcing it to be guaranteed O(n log n) is generally not worth paying. There's more information on that page, as well as on the selection algorithms page.
使用随机快速排序，最坏情况下的运行时间为 O(n log n) 的概率非常高。
use randomized quicksort and you have worstcase run time of O(n log n) with very high probability.
显然，使用随机版本的分区，查找中位数的运行时间似乎是 O(n)，但实际上，当分区再次达到极端不平衡时，运行时间将变为 O(n2 ）。所以从这里你无法做出任何改进。
但仍然有希望。如果您浏览“CORMEN”，那么您会发现即使在最坏的情况下，查找第 i 阶统计量也可以在线性时间内完成。使用的技术是使用中位数的中位数作为枢轴元素，然后找到在任何情况下都保证线性运行时间的尼德安。
所以我们可以在快速排序中使用该技术来获得 O(nlgn) 运行时间
Apparently it seems that the running time of finding the median is O(n) using randomized version of partition, but actually when the partition is again unbalanced at its extreme then the running time goes to O(n2). So you can make no improvement right from here.
But still there's a hope. If you go through "CORMEN" then you will find that finding ith order statistic can be done in linear time even in worst case scenario. The technique that is used is to use the median of median as the pivot element and then find the nedian which guarantees the linear running time in any case.
So we can use that technique in quicksort also to get O(nlgn) running time