我得到了这个算法，它计算一个数组的中位数并对其周围的其他项进行分区。
它将所有元素都小于集合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（na-1）是最后一部分的递归调用。在这种情况下，最糟糕的情况发生在枢轴始终是阵列中最大或最小的项目时。
但是现在，既然我们将中位数作为支点，那么最坏的情况是什么呢？
你可以使用Big 5算法，它会给你一个近似的中位数。如果你在快速排序中使用它作为你的支点，那么最坏情况的复杂性将是O（n log n）而不是O（n ^ 2），因为我们每次都进行相等的除法，而不是在我们用不等的方式划分时的最坏情况一个桶有一个元素，另一个桶有n - 1个元素。
另一方面，这种最坏的情况不太可能发生。使用Big 5中值算法找到枢轴点有很多额外的开销，所以在实践中它通过选择随机枢轴来表现得更好。但如果你想每次都找到中位数，最坏的情况就是O（n logn）