快速排序：选择支点 [英] Quicksort: Choosing the pivot

问题描述

在实现快速排序，你必须做的事情之一就是选择一个支点。但是，当我看到伪code类似下面的，目前尚不清楚我应该如何选择支点。列表的第一个元素？别的东西？

When implementing Quicksort, one of the things you have to do is to choose a pivot. But when I look at pseudocode like the one below, it is not clear how I should choose the pivot. First element of list? Something else?

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

有人可以帮助我掌握选择一个支点的概念，不同的方案是否需要不同的策略。

Can someone help me grasp the concept of choosing a pivot and whether or not different scenarios call for different strategies.

推荐答案

选择一个随机的支点最小化的机会，你会遇到的最坏情况为O（n ² ）性能（总是选择第一个或最后一个将导致近排序或接近-反向排序的数据最坏情况下的性能）。选择中间元件也将在多数情况下可接受的

Choosing a random pivot minimizes the chance that you will encounter worst-case O(n²) performance (always choosing first or last would cause worst-case performance for nearly-sorted or nearly-reverse-sorted data). Choosing the middle element would also be acceptable in the majority of cases.

此外，如果要实现这个自己，也有工作，就地算法的版本（即没有建立两个新的列表，然后连接它们）。

Also, if you are implementing this yourself, there are versions of the algorithm that work in-place (i.e. without creating two new lists and then concatenating them).

这篇关于快速排序：选择支点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！