algorithm - 快速排序算法中枢轴的选择

Question

我正在学习快速排序。我知道快速排序在枢轴值执行不平衡分区时表现不佳，因此第一个元素或最后一个元素不是一个好的选择，因为如果列表几乎已排序，则分区将不平衡。

当我搜索时，我发现了 2 个选项：

一种是在低（最低指数）和向上（最高指数）之间随机选择一个支点。这似乎是一个安全的选择，但随机数生成器很耗时。

其次是取所有元素的中位数。此选项成本高，因此第一个、最后一个和中间元素的中值可以用作枢轴元素。

哪种方法被证明对快速排序最有效？.. 还有其他方法可用于选择枢轴元素吗？

Answer 1

是的，如果您担心数组已排序或接近排序，您可以按照您的建议，连续付出更多努力来选择一个好的枢轴，但如果您的数据未排序，则会以减慢算法为代价。Skienna 在The Algorithm Design Manual中对枢轴选择进行了很好的讨论，他建议您可以在应用快速排序之前对数组进行随机化，但我猜如果您担心的话，另一种排序算法会表现得更好。

哪种方法被证明对快速排序最有效？

这里的关键点是对您的数据执行性能测量。

Answer 2

快速排序没有单一的“最有效”选择。要么通过花费额外时间选择每个枢轴来减慢某些（许多？）案例的排序，要么您对某些输入有病态（O（N ²））行为。花更多的时间选择枢轴会减慢某些输入的排序速度，同时加快其他情况。这总是一个权衡。您选择一种权衡，以提高您期望的输入类型的速度。

在现实世界中，我们可以使用introsort相当便宜地预防病理病例。病态案例的一个特征是深度递归，因此 introsort 检测到深度递归并切换到不同的（但保证为 O(N log N)）算法。

Answer 3

如果您真的担心更坏的情况，请在每个递归调用中随机化子数组，这应该可以保护您免受最坏情况的影响。