一尘不染

快速排序:选择枢纽

algorithm

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

有人可以帮助我掌握选择支点的概念,以及不同的情况是否需要不同的策略。


阅读 430

收藏
2020-07-28

共1个答案

一尘不染

选择一个随机轴可以最大程度地降低遇到最坏情况O(n
2)性能的机会(始终选择第一个或最后一个将对几乎排序或几乎反向排序的数据造成最坏情况的性能)。在大多数情况下,选择中间元素也是可以接受的。

另外,如果您自己实现此功能,则有一些算法可以就地运行(即,无需创建两个新列表然后将它们串联在一起)。

2020-07-28