以O(n)复杂度排序数组

Question

我在Atrenta的采访中被问到一个有趣的问题.这是一个复杂的O(n)阵列,我说这是不可能的,但他坚持认为,即使在采访之后.

就是这样.

你有一个数组,让我们说:[1,0,1,0,1,1,0],这需要进行排序.在阵列中必须做什么(从某种意义上讲,没有涉及其他数据结构.

我没有,我认为不可能做任何复杂的O(n).我能想到的最好的是O(n*log n),我的知识来自维基百科.

如果你知道的话,请给我你的想法和一个方法.

Answer 1

在您的示例中,数组中只有两个不同的值,因此您可以使用计数排序:

zero_count = 0
for value in array:
    if value == 0:
        zero_count += 1
for i in 0 ... zero_count:
    array[i] = 0
for i in zero_count ... array.size:
    array[i] = 1

Radix排序是一系列更普遍适用的O(n)种类.

这是比较排序需要欧米茄(N*log n)的平均,并因此比较不能在运行最坏情况或平均情况的线性时间.