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

Question

我有一个关于快速排序的小问题。在选择数组的最小值或最大值的情况下，分区的枢轴值非常低效，因为数组大小仅减少 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) 而不会显着降低性能。

希望这对您有所帮助!