只由0和1组成的数组排序的高度优化算法

Question

我需要找到一个高度优化的算法来对只包含0和1的数组进行排序。

我的解决方案是计算0的数量（假设为x）和1的数量（假设为y）。一旦您这样做了，就在数组中放置x个0，然后是y个1。这使其为O(n)。

是否有任何比这更好的运行算法？？？我在面试中被问到这个问题。

- akaHuman

---

你确实需要扫描整个数组一次。这使得它的时间复杂度为O(n)。我认为没有其他算法可以比O(n)更好。 - Vikas

Answer 1

自从你必须检查每一个n个输入元素，因此你无法在O(n)上取得进展。

此外，由于你的算法需要O(1)的内存，你也无法改进它（没有比O(1)更优异的渐近复杂度）。

- NPE

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]
    }
}

- Anish Dasappan

Answer 3

如果您对数组求和，您可以得到1的数量，这样稍微更有效一些，但仍然是O(n)。

- Kevin DiTraglia

Answer 4

您不能比O(N)更高效，因为需要检查每个项目。

- Tudor

Answer 5

我们所说的“数组”是什么类型？如果我们要计算一个16位无符号整数中的比特数，那么已经开发出了几种O(1)时间复杂度的算法：请参见快速比特计数例程。

这是其中呈现的算法之一；他们称之为Nifty Parallel Count。

#define MASK_01010101 (((unsigned int)(-1))/3)
#define MASK_00110011 (((unsigned int)(-1))/5)
#define MASK_00001111 (((unsigned int)(-1))/17)
int bitcount (unsigned int n) {
   n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101);
   n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011);
   n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111);
   return n % 255 ;
}

- ZeroOne

Answer 6

这听起来像是单根算盘排序。现在我很好奇你的面试官是谁。

http://www.dangermouse.net/esoteric/abacussort.html

- Noah Buddy