当所有元素都相同时，Quicksort的复杂性如何？

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

我围绕这个问题进行了调查，但没有得到确切的解释。

任何帮助，将不胜感激。

这取决于Quicksort的实现。划分为两个（<和>=）部分的传统实现将具有O(n*n)相同的输入。尽管不一定会发生交换

，但它将导致进行n递归调用-每个调用都需要与数据透视图和n-recursionDepth元素进行比较。即O(n*n)需要进行比较

然而，有一个简单的变体，其分区分为3组（<，=和>）。O(n)在这种情况下，此变体具有性能-

与其选择枢轴，不进行交换，然后递归0到pivotIndex-1and pivotIndex+1to

n，它将将与枢轴相等的所有事物都放置到“中间”分区（在所有相同输入的情况下，总是意味着本身进行交换（即无操作）意味着在这种特殊情况下，n次比较调用堆栈的深度仅为1，并且不会发生交换。我相信这种变种至少已经进入了Linux上的标准库。