我得到了这个算法，它计算数组的中位数并对其周围的其他项目进行分区。
它将所有小于中位数的元素放在集合 A1 中，将所有等于中位数的元素放在 A2 中，将所有较大的元素放在 A3 中。如果 A1 大于 1，它会递归进入它，A3 也会发生同样的情况。它在复制 A 中的 A1、A2 和 A3 串联后终止。
我知道它与快速选择非常相似，但我不知道如何继续以找出最坏情况下的时间复杂度。
我所知道的是，在快速排序中，时间复杂度为 T(n( = n -1 + T(a( + T(n -a-1(，其中 n - 1 表示分区，T(a( 是第一部分的递归调用，t(n-a-1( 是最后一部分的递归调用。在这种情况下，当枢轴始终是数组中最大或最小的项目时，会发生最糟糕的情况。
但是现在，既然我们有中位数作为支点，最坏的情况是什么？
您可以使用 Big 5 算法，它将为您提供近似的中位数。如果您在快速排序中使用它作为枢轴，最坏情况的复杂性将是 O(n log n( 而不是 O(n^2(，因为我们每次都进行相等的除法，而不是最坏的情况，即我们用一个桶有一个元素和另一个桶有 n - 1 个元素不均分。
另一方面，这种最坏的情况不太可能发生。使用Big 5中位数算法查找枢轴点有相当大的开销，因此在实践中，选择随机枢轴的表现优于它。但是，如果您想每次都找到中位数，最坏的情况是 O(n logn(