以 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

基数排序是一系列更普遍适用的 O(n) 排序。

它是比较排序，平均需要 Omega(n * log n) 比较，因此不能在最坏情况或平均情况线性时间内运行。

Answer 2

从两端遍历数组，并在需要时交换 1 和 0。运行时间复杂度为 O(n)，但具有所有 if 条件（类似暴力的方法。可能不是预期的答案）；）

int i = 0 ;
int j = array.size -1 ;
for ( i = 0 ; i < j ; ) {

    if( array[i] == 1) {
        if( array[j] == 0 ) {
            array[j] = 1 ; array[i] = 0 ; //Swap 
            i++; j--; 
            continue;
        }
        //else
            j--;
            continue;

    }
   //else
        if( array[j] == 0 ) {
            i++; 
            continue;
        }

        //else 
            i++ ;
            j--;            
}

Answer 3

由于它是一个二进制数组，因此可以使用双指针方法以 O(n) 的复杂度来求解它。 代码将如下所示：

void sort01(int arr[], int n){
int i = 0, j = n - 1;
while (i <= j){
    if (arr[i] == 0)
    {
        i++;
    }
    else
    {
        swap(arr[i], arr[j]);
        j--;
    }
  }
}