performance - 快速排序:枢轴元素的选择、输入和最坏情况下的性能有何关系？

Question

根据我的理解阅读关于 quicksort 的帖子是枢轴元素的选择极大地影响了它是否以给定输入的最坏情况性能运行。

我问自己

1. 做 randomized pivot 元素只是最小化(但不排除)在 n^2 中运行的机会

2. 什么条件必须input满足 deterministic pivot element例如，始终选择第一个元素作为枢轴，以便 n^2成为现实。

3. 我应该如何输入才能使最坏情况下的性能成为现实？

其他人给出了一个已经排序的数组的例子，无论是升序还是降序作为极端情况。

我认为这与 splitting procedure 有关, element < pivot 的指针(反之亦然)以及不利的枢轴元素使拆分过程成本更高的方式。

可能有人会展示一个简单的例子，比如 array与 [1,2,3]和枢轴[0]如何满足最坏情况下的性能，以便我可以了解所有这些相互之间的关系。

Answer 1

1. 是的，一个随机的主元元素只会让最坏的情况不太可能发生。

2. 一个充分条件是，给定一个长度为 n 的数组，枢轴的选择总是将其分成两个数组，其中一个的长度为 O(1).

3. 假设您有一些规则，在调用 i 时，算法选择 values 数组中位置 v(n, i) 的元素 作为枢轴元素(您给出的示例是 v(n, i) = 0 始终，即算法始终查看第一个元素)。然后设置:

   值_0[v(n, 0)] = 0

   值_1[v(n, 1)] = 1

   值_2(v(n, 2)] = 2

   ....

其中 values_i 是通过为 j < i 省略 v(n, j) 处的元素从原始数组形成的数组。

---

关于 [1, 2, 3] 和主元 0 的示例，据我所知，它没有明确定义。您无法使用固定的主元元素获得完整的最坏情况示例，因为递归永远不会结束。