Quicksort:选择枢轴

实现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))

有人可以帮助我掌握选择枢轴的概念,以及不同的场景是否需要不同的策略.

1> Kip..：

---

选择随机数据可以最大限度地减少遇到最坏情况O(n ²)性能(总是选择第一个或最后一个会导致近似排序或接近反向排序的数据的最坏情况性能).在大多数情况下,选择中间元素也是可以接受的.

此外,如果您自己实现此功能,则有一些算法的版本可以就地工作(即不创建两个新列表然后连接它们).

---

我认为自己实施搜索可能不值得付出努力.另外,要小心你如何选择随机数,因为有时随机数生成器有点慢.

2> Jonathan Lef..：

---

这取决于您的要求.随机选择一个轴使得创建一个生成O(N ^ 2)性能的数据集变得更加困难."三个中间"(第一个,最后一个,中间个)也是一种避免问题的方法.但要注意比较的相对表现; 如果你的比较成本很高,那么Mo3比随机选择(单个枢轴值)做更多的比较.数据库记录的比较成本很高.

---

更新:将评论拉入答案.

mdkess断言:

'3中位数'不是第一个中间位置.选择三个随机索引,并取中间值.重点是确保您选择的枢轴不是确定性的 - 如果是,最坏情况下的数据可以很容易地生成.

我回复了:

分析具有三分区中心的Hoare的查找算法(1997)由P Kirschenhofer,H Prodinger,CMartínez支持你的论点('三个中值'是三个随机项).

在portal.acm.org上描述了一篇文章,该文章是关于HannuErkiö撰写的 "三个中心的最坏情况排列",发表在The Computer Journal,Vol 27,No 3,1984.[更新2012-02- 26:得到文章的文字.第2节'算法'开始:' 通过使用A [L:R]的第一个,中间和最后一个元素的中值,在大多数实际情况下,可以实现有效分区到相当大小的部分."因此,它正在讨论第一个中期的Mo3方法."

另一篇有趣的短篇文章是MD McIlroy,"Quicksort的杀手对手",发表于"软件实践与经验",Vol.29(0),1-4(0 1999).它解释了如何使几乎任何Quicksort表现为二次方.

AT&T贝尔实验室技术期刊,1984年10月"构建工作分拣程序的理论与实践"指出"Hoare建议在几条随机选择的线的中间值附近划分.Sedgewick建议选择第一条线的中位数[. ..]最后[...]和中间".这表明两种"三中值"技术在文献中是已知的.(更新2014-11-23:该文章似乎可在IEEE Xplore或Wiley上获得 - 如果您有会员资格或准备支付费用.)

由JL Bentley和MD McIlroy撰写的"设计排序函数",发表于1993年11月第23卷(11)的软件实践和经验,对这些问题进行了广泛的讨论,他们选择了一种自适应分区算法,部分基于数据集的大小.关于各种方法的权衡有很多讨论.

谷歌搜索"三个中位数"非常适合进一步跟踪.

谢谢你的信息; 我以前只遇到过确定性的"三个中位数".

---

3的中位数不是第一个中间位置.选择三个随机索引,并取中间值.重点是确保您选择的枢轴不是确定性的 - 如果是,最坏情况下的数据可以很容易地生成.

---

选择随机索引的问题在于随机数生成器非常昂贵.虽然它不会增加排序的大O成本,但它可能比你刚刚选择了第一个,最后一个和中间元素的速度慢.(在现实世界中,我敢打赌,没有人会做出假设的情况来减慢你的快速排序.)

3> Chris Cudmor..：

---

嘿,我刚刚教过这堂课.

有几种选择.
简单:选择范围的第一个或最后一个元素.(部分排序输入不好)更好:选择范围中间的项目.(部分排序输入更好)

但是,选择任意元素会冒大规模将n数组分成两个大小为1和n-1的数组的风险.如果你经常这样做,你的快速排序可能会成为O(n ^ 2).

我看到的一个改进是选择中位数(第一,最后,中期); 在最坏的情况下,它仍然可以转到O(n ^ 2),但概率上,这是一种罕见的情况.

对于大多数数据,选择第一个或最后一个就足够了.但是,如果您发现经常遇到最坏情况(部分排序输入),则第一个选择是选择中心值(对于部分排序的数据,这是一个统计上很好的支点).

如果您仍然遇到问题,那么请走中间路线.

4> mindvirus..：

---

永远不要选择一个固定的枢轴 - 这可能会被攻击以利用你的算法的最坏情况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)时间(并且会更快)比这个跛脚中位数快速排序).

中位数算法中位数的解释

5> paperhorse..：

---

不要试图变得过于聪明并结合旋转策略.如果你通过选择中间的第一个,最后一个和一个随机指数的中位数,将中位数3与随机支点相结合,那么你仍然会受到许多发送三次方的中位数的分布的影响(所以它实际上比普通随机枢轴)

例如,管风琴分布(1,2,3 ... N/2..3,2,1)首先和最后都是1,随机指数将是一些大于1的数字,取中位数为1(无论是第一个还是最后一个)你得到一个完全不平衡的分区.