快速排序中枢轴的选择

Question

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

(A)清单的第一要素 (B)清单的最后一项内容 (C)名单中随机选择的元素 (D)名单的中位数

答案是(A)，但我认为应该是(D)。我哪里错了？

Answer 1

答：(D)名单的中位数

每次如果我们以中位数作为枢轴元素，using partition algorithm it takes O(n) time .then将中间值替换为最后一个元素(算法的a/c表示您在这里选择的枢轴，我假设最后一个元素为枢轴)。它将使用O(1) constant time to replace last element with median，每次它将问题分成2半

T(n) = O(n) + 2T(n/2)用主定理求解，得到复杂度为O(nlogn)

在上述方程中，O(n) is in case of Partition algorithm。

Answer 2

选择(A)或(B)将导致快速排序出现最糟糕的情况，时间复杂度为O(n平方)。

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

选择中间元素仍足以防止算法性能不佳。问题是，它是一个常数因子，每次迭代速度较慢。

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

来自维基百科

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