arrays - 如何以每个元素大于/小于其邻居的方式重新排列数组

Question

例如，如果数字是:

30, 12, 49, 6, 10, 50, 13

数组将是:

[10, 6, 30, 12, 49, 13, 50]

如你所见:

• 6 小于 10 和 30 并且
• 49 大于 12 和 13 等等。

这些数字都是不同的，而且是真实的。我需要最高效的算法。

Answer 1

这可以在 O(n) 中完成:

1. 在 O(n) 中找到中位数(描述见 Wikipedia
2. 将每个大于中位数的元素放在奇数位置，将每个较小的元素放在偶数位置

当然，这假设所有元素都是不同的，否则有时会失败。