排序考虑以下数组二进制数

数组时间复杂度：| 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; 
      } 
     } 
    } 
}

第二届一个：

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

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

来源

2013-10-01 user2833862

阅读[益智：排序0的阵列和1层的在一个解析]（http://stackoverflow.com/questions/17900922/puzzle-sort-an-array-of-0s-and-1s- in-one-parse/17901084＃17901084） –

只计算一个人的数量，然后用零填充你的数组，然后用零个数填充你的数组。复杂性将是O（n）。

在您的这两种情况下，你有一个O（N²）的复杂性

来源

2013-10-01 08:38:40

这也可以被认为是基数排序。 – Adam

@Adam或桶排序。不过，我不认为这个问题应该使用排序算法解决，当有更直接的事情时。 –

它更类似于[计数排序]（http://en.wikipedia.org/wiki/Counting_sort）。 – Dukeling

一日一会（N^2）时间在O阵列，因为它是冒泡排序的直接含义进行排序。但第二种方法不会对数组进行排序，因为您在从末尾开始交换时使用前0替换1。所以如果你的数组像0 0 0 1 1 1那么第二个代码会将第三个索引中的1与第二个索引中的0交换，最后它看起来像0 0 1 1 1 0。我不知道那个x是什么？

来源

2013-10-01 08:45:40

正如@Alexandru说好给O（N），你只需要重复两次

要查找的0计数，1
要使用1填充数组，0作为数说。

如果你正在寻找另一种选择，你可以看看这是O（N）。

for(int i=0, j=n-1;i<j;) 
{ 
if(a[i]==1 && a[j]==0) swap(a[i],a[j]); 
else if(a[i]==1 && a[j]==1) j--; 
else if(a[i]==0 && a[j]==0) i++; 
else if(a[i]==0 && a[j]==1) {j--; i++;} 
}

来源

2013-10-01 09:09:47 MissingNumber

+正确！你可以简化为[拼图：在一个解析中对0和1的数组进行排序。]（http://stackoverflow.com/questions/17900922/puzzle-sort-an-array-of-0s-and-1s-in-一解析/ 17901084＃17901084） –

排序考虑以下数组二进制数

回答

相关问题