所有重复项的数组如何使快速排序 O(N^2)？

How does an array of all duplicates make quicksort O(N^2)?

在我的数据结构和算法中 class 我们了解了 3 次扫描和 Hoare 的分区算法。有人告诉我，我们在所有重复项的数组上得到 O(N^2) 的最坏情况。

但是，我不明白为什么所有重复项的数组给出 N^2 的最坏情况时间，我理解为什么选择 min/max 作为基准给出最坏情况但希望有人可以解释重复案例！

只有 Lomuto 分区或类似的分区方案存在所有重复导致时间复杂度为 O(n^2) 的问题。

使用 Hoare 分区方案，将有不必要的相等元素交换，但分区将是理想的 50% / 50% 分割，因此 O(log2(n))（常量 2 通常不包括在内）时间复杂度，但我在这里包括它以指示分区的理想分割）。一般来说，随着重复百分比的增加，基于霍尔分区的快速排序排序所需的时间会减少。