Quicksort：选择枢轴

Question

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

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

Answer 1

选择随机数据会最大限度地减少您遇到最坏情况O（n 2）性能的可能性（总是选择第一个或最后一个会导致近似排序或接近反向排序的数据的最坏情况性能）。在大多数情况下，选择中间元素也是可以接受的。此外，如果您自己实现此功能，则有一些算法的版本可以就地工作（即不创建两个新列表然后连接它们）。

Answer 2

嘿，我刚刚教过这堂课。有几种选择。简单：选择范围的第一个或最后一个元素。（部分排序输入不好）更好：选择范围中间的项目。（部分排序输入更好）但是，选择任意元素会冒大规模将n数组分成两个大小为1和n-1的数组的风险。如果你经常这样做，你的快速排序可能会成为O（n ^ 2）。我看到的一个改进是选择中位数（第一，最后，中期）; 在最坏的情况下，它仍然可以转到O（n ^ 2），但概率上，这是一种罕见的情况。对于大多数数据，选择第一个或最后一个就足够了。但是，如果您发现经常遇到最坏情况（部分排序输入），则第一个选择是选择中心值（对于部分排序的数据，这是一个统计上很好的支点）。如果您仍然遇到问题，那么请走中间路线。