我得到了这个算法，该算法计算数组的中位数并将其周围的其他项分区。
它将所有小于中位数的元素放在集合 A1 中，所有等于它的元素放在 A2 中，所有大于它的元素放在 A3 中。如果 A1 大于 1，它会递归地进入它，A3 也会发生同样的情况。它在 A 中复制 A1、A2 和 A3 的串联后终止。
我知道它与 Quickselect 非常相似，但我不知道如何进行才能计算出最坏情况下的时间复杂度。
我所知道的是，在Quicksort中，时间复杂度是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)
关于algorithm - 该算法的递归关系是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55444817/