实现Quicksort时，您需要做的一件事就是选择一个数据透视表。但是当我看下面的伪代码时，我不知道应该如何选择枢轴。列表的第一个要素？别的什么？
function quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))
有人可以帮助我掌握选择枢轴的概念，以及不同的场景是否需要不同的策略。
选择随机数据可以最大限度地减少遇到最坏情况O（n2）性能的可能性（总是选择第一个或最后一个会导致近乎排序或接近反向排序的数据的最坏情况性能）。在大多数情况下，选择中间元素也是可以接受的。
此外，如果您自己实现此功能，则有一些算法的版本可以就地工作（即不创建两个新列表然后连接它们）。
快速排序的复杂性随着枢轴值的选择而变化很大。例如，如果您始终选择第一个元素作为枢轴，算法的复杂性将变得与O（n ^ 2）一样最差。这是一种选择枢轴元素的智能方法 - 1.选择数组的第一个，中间，最后一个元素。 2.比较这三个数字，找出大于1且小于其他数字的数字，即中位数。 3.将此元素设为枢轴元素。
通过这种方法选择枢轴将阵列分成近两半，因此复杂度降低到O（nlog（n））。
平均而言，3的中位数适合小n。对于较大的n，5的中位数更好一些。 ninther，即“三个三个中位数的中位数”对于非常大的n更好。
随着n的增加，采样越高越好，但随着样本的增加，改善速度会急剧减慢。而且你会产生抽样和分类样本的开销。
我建议使用中间索引，因为它可以很容易地计算。
您可以通过舍入（array.length / 2）来计算它。
在真正优化的实现中，选择数据透视的方法应该取决于数组大小 - 对于大型数组，花费更多时间选择一个好的数据透镜是值得的。在没有进行全面分析的情况下，我猜测“O（log（n））元素的中间”是一个很好的开始，这有额外的好处，不需要任何额外的内存：在更大的分区上使用尾调用在分区中，我们在算法的几乎每个阶段使用相同的O（log（n））额外内存。
这取决于您的要求。随机选择一个轴使得创建一个生成O（N ^ 2）性能的数据集变得更加困难。 “三个中位数”（第一个，最后一个，中间个）也是一种避免问题的方法。但要注意比较的相对表现;如果你的比较成本很高，那么Mo3比随机选择（单个枢轴值）做更多的比较。数据库记录的比较成本很高。
更新：将评论拉入答案。
mdkess声称：
'3中位数'不是第一个中间位置。选择三个随机索引，并取中间值。重点是确保您选择的枢轴不是确定性的 - 如果是，最坏情况下的数据可以很容易地生成。
我回复了：
谢谢你的信息;我以前只遇到过确定性的“三个中位数”。
嘿，我刚刚教过这堂课。
有几种选择。 简单：选择范围的第一个或最后一个元素。 （部分排序输入不好）更好：选择范围中间的项目。 （部分排序输入更好）
但是，选择任意元素会冒大规模将n数组分成两个大小为1和n-1的数组的风险。如果你经常这样做，你的快速排序可能会成为O（n ^ 2）。
我看到的一个改进是选择中位数（第一，最后，中期）;在最坏的情况下，它仍然可以转到O（n ^ 2），但概率上，这是一种罕见的情况。
对于大多数数据，选择第一个或最后一个就足够了。但是，如果您发现经常遇到最坏情况（部分排序输入），则第一个选择是选择中心值（对于部分排序的数据，这是一个统计上很好的支点）。
如果您仍然遇到问题，那么请走中间路线。
永远不要选择一个固定的枢轴 - 这可能会被攻击以利用你的算法的最坏情况O（n ^ 2）运行时，这只是在寻找麻烦。 Quicksort的最坏情况运行时发生在分区导致一个1个元素的数组和一个n-1个元素的数组时。假设您选择第一个元素作为分区。如果有人向您的算法提供递减顺序的数组，则您的第一个数据透视图将是最大的，因此数组中的其他所有内容都将移动到其左侧。然后当你递归时，第一个元素将再次成为最大元素，所以再一次将所有内容放在它的左边，依此类推。
更好的技术是3的中位数方法，您可以随机选择三个元素，然后选择中间元素。你知道你选择的元素不是第一个或最后一个，而且，根据中心极限定理，中间元素的分布将是正常的，这意味着你将倾向于中间（因此，n lg n time）。
如果你绝对想要保证算法的O（nlgn）运行时间，那么用于查找数组中值的5列方法在O（n）时间内运行，这意味着在最坏的情况下快速排序的递归方程将是be T（n）= O（n）（求中位数）+ O（n）（分区）+ 2T（n / 2）（左右递归。）通过主定理，这是O（n lg n） 。但是，常数因素将是巨大的，如果最坏情况下性能是您的主要考虑因素，请使用合并排序，它平均比快速排序慢一点，并保证O（nlgn）时间（并且会更快）比这个跛脚中位数快速排序）。
不要试图变得过于聪明并结合旋转策略。如果你通过选择中间的第一个，最后一个和一个随机指数的中位数，将中位数3与随机支点相结合，那么你仍然会受到许多发送三次方的中位数的分布的影响（所以它实际上比普通随机枢轴）
例如，管风琴分布（1,2,3 ... N / 2..3,2,1）首先和最后都是1，随机指数将是一些大于1的数字，取中位数为1（无论是第一个还是最后一个）你得到一个完全不平衡的分区。
它完全取决于数据的排序方式。如果您认为它是伪随机的，那么您最好的选择是选择随机选择还是选择中间选择。
如果要对随机可访问的集合（如数组）进行排序，通常最好选择物理中间项。有了这个，如果数组已经准备好排序（或几乎排序），两个分区将接近均匀，你将获得最佳速度。
如果您只对线性访问（如链接列表）进行排序，那么最好选择第一项，因为它是访问速度最快的项目。然而，在这里，如果列表已经排序，你就搞砸了 - 一个分区总是为空，另一个分区拥有一切，产生最糟糕的时间。
但是，对于链接列表，选择除第一个之外的任何内容，只会使事情变得更糟。它选择列表列表中的中间项，你必须在每个分区步骤中逐步执行 - 添加一个O（N / 2）操作，该操作完成logN次，使总时间为O（1.5 N * log N）如果我们知道列表在我们开始之前已经有多长时间了 - 通常我们不会这样做，我们必须一步一步地计算它们，然后逐步找到中间位置，然后逐步完成第三次做实际分区：O（2.5N * log N）
这样做更容易将快速分析分为三个部分
它只比一个肺功能稍微有效，但更容易理解。
代码如下：
Explanation of the Median of Medians Algorithm
理想情况下，pivot应该是整个数组中的中间值。这将减少最坏情况下的表现。