这取决于Quicksort的实现。划分为两个（<和>=）部分的传统实现将具有O(n*n)相同的输入。尽管不一定会发生 交换
，但它将导致进行n递归调用-每个调用都需要与数据透视图和n-recursionDepth元素进行比较。即O(n*n)需要进行比较

然而，有一个简单的变体，其分区分为3组（<，=和>）。O(n)在这种情况下，此变体具有性能-
与其选择枢轴，不进行交换，然后递归0到pivotIndex-1and pivotIndex+1to
n，它将将与枢轴相等的所有事物都放置到“中间”分区（在所有相同输入的情况下，总是意味着本身进行交换（即无操作）意味着在这种特殊情况下，n次比较调用堆栈的深度仅为1，并且不会发生交换。我相信这种变种至少已经进入了Linux上的标准库。