实施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)性能的数据集变得更加困难。 "三位数中位数"(第一，最后，中间)也是避免问题的一种方法。但是要当心比较的相对性能；如果比较成本很高，那么Mo3所做的比较会比随机选择(单个枢轴值)更多。数据库记录的比较成本很高。

更新：将评论纳入答案。

mdkess断言：

'Median of 3' is NOT first last middle. Choose three random indexes, and take the middle value of this. The whole point is to make sure that your choice of pivots is not deterministic - if it is, worst case data can be quite easily generated.

我对此回应：

• P. Kirschenhofer，H.Prodinger，C Martnez对Hoare的具有三位数中位数的查找算法进行分析(1997年)，C Martnez支持争论("三位数中位数"是三个随机项)。
• 在portal.acm.org上有一篇文章，描述的是Hannu Erki？撰写的"三位数中位数的最差情况置换"，发表于1984年，计算机杂志，第27卷，第3号。 -26：获得了文章的文字。第2节"算法"开始："通过使用A [L：R]的第一个，中间和最后一个元素的中值，可以在大多数实际情况下将大小有效地划分为大小相等的部分。"因此，它正在讨论Mo3的倒数第一方法。]
• 另一篇有趣的短文是M. D. McIlroy撰写的" Quicksort的杀手Ad"，发表在《软件实践与经验》第一卷。 29(0)，14(0 1999)。它说明了如何使几乎所有Quicksort都具有二次行为。
• AT＆T贝尔实验室技术期刊，1984年10月，"构建工作排序例程的理论和实践"指出：" Hoare建议在几条随机选择的行的中值附近进行划分。Sedgewick建议选择第一个[。]的中值。 ..]末尾和中间"。这表明在文献中已知两种用于"三中位数"的技术。 (2014年11月23日更新：如果我们已经成为会员或者准备付费，则这篇文章似乎可以在IEEE Xplore或者从Wiley上获得。)
• JL Bentley和MD McIlroy于1993年11月在《软件实践与经验》第23(11)卷上发表的"设计排序函数"进行了广泛的讨论，他们选择了一种自适应分区算法，部分基于数据集的大小。关于各种方法的折衷方法有很多讨论。
• Google搜索" 3个中位数"的效果很好，可以进行进一步的跟踪。

谢谢提供信息;我之前只遇到过确定性的"三位数中位数"。

如果要对随机可访问的集合(如数组)进行排序，通常最好选择物理中间项。这样，如果阵列全部准备好排序(或者几乎排序)，则两个分区将接近偶数，并且我们将获得最佳速度。

如果我们仅对线性访问进行排序(例如链表)，那么最好选择第一项，因为这是访问速度最快的项。但是，在这里，如果列表已经排序，则很麻烦-一个分区将始终为空，另一个分区将具有所有内容，从而产生最差的时间。

但是，对于链接列表，选择除第一个列表之外的任何内容都会使情况变得更糟。它选择一个列表中的中间项目，我们必须在每个分区步骤中逐步完成它-添加一个O(N / 2)操作，该操作执行logN次，使总时间为O(1.5 N * log N)，并且那就是如果我们知道列表开始之前还有多长时间-通常我们不知道，所以我们必须一路走过去来对它们进行计数，然后中途走过去以找到中间位置，然后第三次走过去做实际的分区：O(2.5N * log N)

它完全取决于如何对数据进行排序。如果我们认为这将是伪随机的，那么最好的选择是选择一个随机选择或者选择中间选项。

呵呵，我刚教过这堂课。

有几种选择。
简单：选择范围的第一个或者最后一个元素。 (对部分排序的输入不利)
更好：在范围的中间选择项目。 (最好使用部分排序的输入)

但是，选择任意元素会冒将n大小的数组错误地划分为大小为1和n-1的两个数组的风险。如果我们经常这样做，则快速排序将面临变成O(n ^ 2)的风险。

我看到的一个改进是选择中位数(第一，最后，中间)；
在最坏的情况下，它仍然可以达到O(n ^ 2)，但是从概率上讲，这是一种罕见的情况。

对于大多数数据，选择第一个或者最后一个就足够了。但是，如果我们发现经常遇到最坏的情况(部分排序的输入)，则第一个选择是选择中心值(这是部分排序的数据在统计上的优势)。

如果我们仍然遇到问题，请选择中间路线。

永远不要选择固定的枢轴，可以利用它来攻击我们算法的最坏情况O(n ^ 2)运行时，这只是自找麻烦。 Quicksort最坏情况的运行时发生在分区结果为1个元素的一个数组和n-1个元素的一个数组时。假设我们选择第一个元素作为分区。如果有人以递减的顺序向算法提供数组，那么第一个枢轴将是最大的，因此数组中的所有其他元素都将移至它的左侧。然后，当我们递归时，第一个元素将再次成为最大元素，因此再次将所有元素都放在它的左边，依此类推。

更好的技术是3中位数方法，我们可以随机选择三个元素，然后选择中间元素。我们知道选择的元素不会是第一个或者最后一个，但根据中心极限定理，中间元素的分布将是正态的，这意味着我们将趋向于中间(因此，n lg n次)。

如果我们绝对要保证算法的运行时间为O(nlgn)，则用于查找数组中位数的5列方法将以O(n)时间运行，这意味着在最坏情况下快速排序的递归方程将是T(n)= O(n)(找到中位数)+ O(n)(分区)+ 2T(n / 2)(左右递归)。根据主定理，这是O(n lg n) 。但是，常数会很大，如果最主要的情况是最坏的情况，请改用合并排序，合并排序平均比快速排序慢一点，并且可以保证O(nlgn)时间(并且会更快)比这个la脚的中位数快速排序)。

中值算法中值的解释