pivot - 为什么以及如何选择不好的枢轴选择使快速排序 O(n^2)？

Question

例如，当枢轴是数组中的最高值或最低值时。

对于使用 2 个指针的快速排序，1 个从左端到右，另一个从右端到左，当指针发现一个元素相对于枢轴不合适时，指针停止，当两者都停止时，它们交换元素并继续从那个位置开始。但是，为什么一个糟糕的枢轴选择会导致快速排序 O(n^2)？

Answer 1

一个糟糕的枢轴选择如何使快速排序 O(n^2)？

假设您总是选择最小的元素作为您的支点。快速排序的顶级迭代将需要n-1比较，并将数组拆分为两个子数组：一个是 size 1，一个是 size n-1。第一个已经排序，您可以递归地将快速排序应用于第二个。拆分第二个将需要n-2比较。等等。

总的来说，你有(n-1) + (n-2) + ... + 1 = n * (n-1) / 2 = O(n^2)比较。

Answer 2

尝试一个具有 n 倍相同数字的列表。
选择任何方式来找到一个privot。
看看发生了什么。

（编辑：做一些提示：
枢轴不依赖于找到枢轴的方式，因为它总是相同的。
因此，在每次迭代中，对于具有 n 个元素的当前列表，您将需要 n 比较，并且您将拆分在两个具有 1 个和 n-1 个元素的子列表中包含 n 个当前元素的列表。
您可以快速计算总体操作数。您需要n, n-1, n-2, ..., 2, 1操作。
形式上，它是sum from i=1 to n over i，您应该知道一个公式才能看到它O(n*n)）

Answer 3

If your chosen pivot happened to be the maximal value in your subset on every recursion, the algorithm would simply move every record read into the subset below the pivot, and continue on with only one non-empty partition. This new subset's size would be only one less.

In that case, the quicksorts operation would be similar to a selection sort. I would find a maximal value, put it where it goes, and move on to the rest of the data in the next iteration. The difference being that the selection sort searches for the maximal (or minimal) data point, where the worst-case quicksort would happen to select the maximal value and then discover that it is, indeed, the maximum.

This is a quite rare case, to my knowledge.