排序二进制数组的时间复杂度

1 c++ algorithm time-complexity

给出以下数组: | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |

我们必须对上面的数组进行排序,就像右边的所有1和左边的0一样.

我在C++中提出了2种算法.

第一个:

for(i = 0; i < n; i++) {
    if(a[i] == 1 && i != n - 1) {
        for(j = i + 1; j < n; j++) {
            if(a[j] == 0) {
                temp = a[j];
                a[i] = a[j];
                a[j] = temp;
                break;
            }
        }
    }
}
Run Code Online (Sandbox Code Playgroud)

第二个:

int x = 0;
for(i = 0; i < n; i++) {
    if(a[i] == 1) {
        for(j = n-x-1; j >= 0; j--) {
            if(a[j] == 0) {
                temp = a[j];
                a[i] = a[j];
                a[j] = temp;
                x++;
                break;
            }
        }
    if(x > n / 2)
    break;
}
Run Code Online (Sandbox Code Playgroud)

你能告诉我两者的时间复杂度吗?哪一个表现更好也建议我一个更好的解释算法.谢谢.

Ale*_*sie 15

只需计算1的数量,然后用第一个lengthOfArray - sum元素和第一个元素重新填充数组.复杂性将是O(n).

在这两种情况下,你的复杂度都是O(n²)

  • 它与[计数排序](http://en.wikipedia.org/wiki/Counting_sort)更相似. (3认同)