quicksort - 如果所有输入数字都相等，快速排序需要多少次比较

Question

我有一个相同的 N 个数字数组。我正在对其应用快速排序。在这种情况下，排序的时间复杂度应该是多少。

我仔细研究了这个问题，但没有得到确切的解释。

Answer 1

它总是会进行相同的比较计数（如果您使用纯快速排序），因为它必须检查所有数字（除非您添加一些特殊功能，它将检查像这样的特殊情况）。但它不必切换任何数字，所以这是最好的情况，因此它的复杂度应该是（n log n）。

Answer 2

一个天真的快速排序算法将是O(n^2). 即使它具有更智能的枢轴选择算法也是如此。为了避免O(n^2)，快速排序算法需要为每个主元（小于、等于、大于）将数字分成 3 个集合。

更智能的枢轴选择算法是：

• 一个基于启发式（例如，选择从第一个元素、中间元素和最后一个元素获得的候选枢轴的中位数）
• 一个用于O(n log n)保证 - 不会在这里讨论，但这样的算法可以保证枢轴来自，例如，排序数组的 25-75% 之间。

然而，大多数普通的快速排序算法将数字划分为小于或大于枢轴的数字。等于枢轴的那些与大于或小于枢轴的那些任意捆绑。

在所有数字相等的情况下，每个分区将只产生一个分区 - 因此每次仅将剩余分区的大小减少 1。

为了避免这种情况，快速排序算法需要将数字分成 3 组 - 小于、大于和等于主元。