排序考慮以下數組二進制數

數組時間複雜度：| 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） –

排序考慮以下數組二進制數

回答

相關問題