使用中位数对数组进行排序

Question

所以让我们假设你有一个算法来找到一个数组的中位数，让我们调用这个方法 X。X 基本上会在 O(n) 中找到数组 a（a 未排序）的中位数时间。我如何能够设计一个 O(n log n) 时间算法来对数组 a 进行排序，使用 X 作为辅助方法。无法真正理解中位数将帮助我对数组进行排序的事实...... ??

谢谢

Answer 1

在快速排序中，如果随机选择主元，则对数组进行排序的最坏情况复杂度为 O(n^2)。

但是也有快速排序的变体，其最坏情况时间复杂度为O(nlgn)。在这些变体中，枢轴元素是数组的中位数（n/2th 元素）或枢轴位置是数组大小的函数，因此它可以将数组分为两部分，这是数组大小（不是常量）的函数。

Answer 2

您可以通过递归地应用 X 来解决这个问题。考虑下面的子例程 Y:

给定一个长度为 n 的数组作为输入，我们首先应用方法 X 求输入数字的中位数 m，这需要时间 O(n).
然后我们扫描输入数组以重新排列数组中的数字，以便所有小于 m 的数字都在数组的左侧，而所有大于 [=12= 的数字]在数组的右边（而m在数组的中间），注意这一步也需要时间O(n).

因此在长度为 n 的输入数组上，子程序 Y 总共需要 O(n) 时间。

所以如果你递归地将子例程Y应用于中位数m左右的子数组并继续这个过程，输出将是一个排序数组，总时间是给出者：

T(n) = O(n) + 2 * O(n/2) + 4 * O(n/4) + ... + 2^log(n) * O(n / 2^log(n)) 
     = O(n) + O(n) + O(n) + ... + O(n)     // log(n) terms in total
     = O(n log(n))

使用中位数对数组进行排序

Sorting array using medians

arrays

algorithm

sorting

median