algorithm - 在快速排序中使用中值选择？

Question

我有一个关于 Quicksort 的小问题。在选择数组的最小值或最大值的情况下，分区的枢轴值非常低效，因为数组大小仅减少 1。

但是，如果我添加选择该数组中位数的代码，我认为 Ii 会更有效率。由于分区算法已经是 O(N)，所以它会给出一个 O(N log N) 的算法。

这可以做到吗？

Answer 1

您绝对可以使用线性时间中值选择算法来计算快速排序中的枢轴。这为您提供了最坏情况的 O(n log n) 排序算法。

然而，线性时间选择的常数因子往往如此之高，以至于在实践中，所得到的算法将比在每次迭代中随机选择枢轴的快速排序要慢得多。因此，看到这样的实现并不常见。

避免 O(n ² ) 最坏情况的一种完全不同的方法是使用类似于introsort中的方法。该算法监控快速排序的递归深度。如果看起来算法开始退化，它会切换到不同的排序算法（通常是堆排序），保证最坏情况 O(n log n)。这使得整体算法 O(n log n) 不会显着降低性能。

希望这可以帮助！