实施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(n 2)性能的机会(始终选择第一个或最后一个将对几乎排序或几乎反向排序的数据造成最坏情况的性能)。在大多数情况下,选择中间元素也是可以接受的。
另外,如果您自己实现此功能,则有一些算法可以就地运行(即,无需创建两个新列表然后将它们串联在一起)。