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

在我的数据结构和算法课上，我们学习了 3-scan 和 Hoare 的分区算法。有人告诉我，我们在所有重复项的数组上得到了 O(N^2) 的最坏情况。

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

标签： quicksort

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

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