高度优化的算法,用于对仅由0 n 1组成的数组进行排序

Question

我需要找到一个高度优化的算法来排序一个只包含0 n 1的数组.

我的解决方案版本是计算编号.零(比如说x)和(比如说y).完成后,在数组中放置x零,然后输入y 1s.这使它成为O(n).

任何运行比这更好的算法??? 我在面试中被问到这个问题.

Answer 1

由于您必须检查每个n输入元素,因此无法改进O(n).

此外,由于你的算法需要O(1)内存,你也无法改进(没有什么比渐近更好O(1)).

Answer 2

我们不能比O(n)做得更好,但看起来我们可以一次完成

low = 0; 
high = arr.length - 1;

while (low < high) {
    while (arr[low] == 0) {
        low ++;
    }
    while (arr[high] == 1) {
        high --;
    }
    if (low < high) {
    //swap arr[low], arr[high]
    }
}

Answer 3

如果对数组求和,则可以得到1的数,效率稍高,但仍为O(n).