quicksort - 使用随机枢轴的快速排序实现

Question

是否有任何广泛使用的使用随机选择的枢轴的快速排序实现？

我问，因为库C函数是qsort使用“ Tukey's 'ninther'，三个样本的中位数的中位数，每个三个元素的中位数”实现的，并且性能明显优于随机快速排序。

Answer 1

理论上，随机枢轴快速排序的预期时间确实是O(nlogn)。

但我认为，如果存在随机枢轴选择的实现，那将是很少见的，因为它不实用。原因：

• 真正随机性的成本在执行时间上很高。
• 使用伪随机性意味着可以构造一个输入来驱动排序O(n^2)

看看这个黑客新闻线程：https ://news.ycombinator.com/item?id=1442849

如果此信息不正确，请告诉我，以便我更新此答案。