当所有元素相同时，Quicksort的复杂性？
我有一个N个数字的数组是相同的。我正在应用快速排序。 在这种情况下，排序的时间复杂度应该是多少。
我盯着这个问题，但没有得到确切的解释。
任何帮助，将不胜感激。
这取决于Quicksort的实现。 分成2（ <和>= ）部分的传统实现将在相同的输入上具有O(n*n) 。 虽然不会发生交换 ，但它会导致n递归调用 - 每个调用都需要与pivot和n-recursionDepth元素进行比较。 即需要进行O(n*n)比较
但是有一个简单的变体，它分为3组（ < ， =和> ）。 在这种情况下，此变体具有O(n)性能 - 而不是选择枢轴，交换然后在0到pivotIndex-1和pivotIndex+1到n pivotIndex+1 ，它将把所有东西等于枢轴的交换放到'中间'分区（在所有相同输入的情况下总是意味着与自身进行交换，即无操作）意味着在这种特定情况下调用堆栈仅为1深度n比较并且不发生交换。 我相信这个变种至少已经进入linux上的标准库。
快速排序的性能取决于枢轴选择。 选择的枢轴越接近中间元素，quicksort的性能越好。
在这种特殊情况下，您很幸运 – 您选择的轴将始终为中位数，因为所有值都相同。 因此，快速排序的分区步骤将永远不必交换元素，并且两个指针将恰好在中间相遇。 因此，这两个子问题的大小只有一半 – 给你一个完美的O(n log n) 。
更具体一点，这取决于分区步骤的实现情况。 循环不变只需要确保较小的元素在左侧子问题中，而较大的元素在右侧子问题中。 无法保证分区实现永远不会交换相等的元素。 但它总是不必要的工作，所以没有聪明的实现应该这样做： right指针永远不会检测到相应的枢轴反转（即你永远不会遇到*left > pivot && *right < pivot ）的情况，所以left指针将递增， right指针将逐步递减，它们最终会在中间相遇，产生大小为n/2子问题。
这取决于具体的实施。
如果只有一种比较（≤或<）来确定其他元素相对于枢轴的位置，它们将全部进入其中一个分区，并且您将获得O（ n 2 ）性能，因为问题大小每步只减少1个。
此处列出的算法是一个示例（附图说明了不同的算法）。
如果有两种比较，例如
上面链接中的插图使用的算法不会在步骤中移动指针，因此您仍然会获得较差的性能（请参阅“少数独特”案例）。
因此，在实施算法时，这取决于您是否考虑到这种特殊情况。
实际实现通常处理更广泛的特殊情况：如果分区步骤中没有交换，则它们假设数据几乎已经排序，并使用插入排序，在所有相等元素的情况下，它提供更好的O（ n ）。
tobyodavies提供了正确的解决方案。 当所有键都相等时，它会处理大小写并在O（n）时间内完成。 它和我们在荷兰国旗问题上的划分是一样的
http://en.wikipedia.org/wiki/Dutch_national_flag_problem
分享来自普林斯顿的代码
http://algs4.cs.princeton.edu/23quicksort/Quick3way.java.html
如果实现双向分区算法，那么在每一步都将数组减半。 这是因为当遇到相同的键时，扫描停止。 结果，在每个步骤中，分区元素将位于子arrays的中心，从而在每个后续递归调用中将arrays减半。 现在，这种情况类似于mergesort情况，它使用~N lg N比较来排序N个元素的数组。 对于重复键，Erikort的传统双向分区算法使用~N lg N比较，从而遵循线性方法。