algorithm - 快速排序中的枢轴选择

Question

快速排序中分区元素的理想选择是

(A) First element of the list

(B) Last element of the list

(C) Randomly chosen element of the list

(D) Median of the list

给出的答案是 (A)，但根据我的说法，应该是 (D)。我哪里错了？

Answer 1

选择 (A) 或 (B) 将导致 Quicksort 遇到最坏情况，时间复杂度为 O(n²)。

随机选择会偏离这个糟糕的性能，算法会有效运行。

选择中值元素仍然足以防止算法表现不佳。问题是它是每次迭代速度较慢的常数因子。

所以 (C) 或 (D) 都可以。

---

来自 Wikipedia :

在快速排序的早期版本中，分区的最左边的元素通常会被选为基准元素。不幸的是，这会导致已经排序的数组出现最坏情况，这是一个相当常见的用例。通过为枢轴选择一个随机索引、选择分区的中间索引或(特别是对于较长的分区)为枢轴选择分区的第一个、中间和最后一个元素的中值，这个问题很容易解决。