對包含兩種元素的陣列進行排序

---

對僅包含兩種元素（即只有 1 和 0）的陣列進行排序，有多種方法。我們將討論三種不同的方法。第一種方法簡單地使用預定義的 sort() 函式對給定陣列進行排序。第二種方法是計數排序方法，我們將計算 0 和 1 的數量，然後首先寫入 0（0 的計數次數），然後寫入 1（1 的計數次數）來更新陣列。在最後一種方法中，我們使用了雙指標法。

問題陳述

給定一個僅包含 1 和 0 的陣列。我們的任務是排列所有 0 和 1，使得 1 在陣列的最右邊，0 在陣列的左邊。

示例

Given array: a[] = [ 1, 1, 0, 1, 0, 1, 0, 1 ]
Resultant array: a[] = [ 0, 0, 0, 1, 1, 1, 1, 1 ]

方法 1：暴力法。

在這種方法中，我們將直接使用 sort() 函式對陣列進行排序。由於 1>0，排序後，所有 1 將排列在陣列的右側，所有 0 將排列在左側。

Sort() 函式：Sort() 函式需要 O(NlogN) 的時間，並以升序返回陣列。

示例

以下是上述方法的 C++ 實現，用於對包含兩種元素的陣列進行排序。

#include <bits/stdc++.h>
using namespace std;
int main(){
   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 };
   int len = sizeof(a) / sizeof( a[0] );
   
   // sort function to
   // sort the array
   sort( a, a + len);
   cout<< " After sorting the array, the array obtained is ";
   for(int iterator =0; iterator<len; iterator++){
      cout << a[iterator] <<" ";
   }
   return 0;
}

輸出

編譯後，上述程式將產生以下輸出：

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

方法 2：計數排序方法

在這種方法中，我們將簡單地計算陣列中 0 和 1 的數量，然後用 0 更新陣列的開頭，用 1 更新陣列的結尾。

透過這樣做，我們將所有 0 放置在陣列的最左邊，所有 1 放置在最右邊，這將自動錶示所需的已排序陣列。

這是一種簡單的方法，但它會插入新值到陣列中，而不是僅僅交換它們的位置，因此這種方法效率不高。

示例

以下是使用 C++ 實現上述方法的程式碼。

#include <iostream>
using namespace std;
int main() {
   int count = 0 ;
   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 };
   int len = sizeof(a) / sizeof(a[0]);
   for(int iterator=0; iterator<len; iterator++){
      if( a[iterator] == 0 )
      count++;
   }
   for(int iterator=0 ; iterator<len ; iterator++){
      if(count){
         a[iterator] = 0 ;
         count-- ;
      }
      else a[iterator] = 1;
   }
   cout<< " After sorting the array, the array obtained is ";
   for(int iterator =0 ; iterator<len ; iterator++){
      cout<< a[iterator] << " ";
   }
   return 0;
}

輸出

編譯後，它將產生以下輸出：

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

時間複雜度 - 由於我們只使用了一個迴圈，因此這種方法的時間複雜度為 O(N)

空間複雜度 - O(1)。雖然我們使用了額外的變數，但由於它們是線性的，因此空間複雜度是常數。

方法 3：解決此問題的最佳方法

在這種方法中，我們將保留兩個指標，start 和 end。我們將使用 start 指標從開頭（索引 0）遍歷陣列，使用 end 指標從結尾（索引 = len -1）同時遍歷陣列。

我們的任務是將所有 1 排列到陣列的最右邊，這將自動導致所有 0 位於陣列的左邊。

我們從初始索引開始，即 start，如果找到的元素是 1，我們將它與索引“end”處的元素交換，並將 end 指標遞減 1。

如果找到的元素是 0，則無需執行任何交換操作，因為它已經在最左邊的位置，我們只需將 start 指標遞增 1。

示例

此方法的程式碼如下：

#include <bits/stdc++.h>
using namespace std;
int main(){
   int start =0 ;
   int a[] = { 1, 1, 0, 1, 0, 1, 0, 1 } ;
   int len = sizeof(a) / sizeof( a[0] ) ;
   int end = len-1;
   while(start < end){
      if( a[start] ==1){
         swap(a[start], a[end]);
         end--;
      }
      else
         start++;
   }
   cout<< " After sorting the array, the array obtained is ";
   for(int iterator =0 ; iterator<len ; iterator++){
      cout<< a[iterator] << " ";
   }
   return 0;
}

輸出

After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

時間複雜度 - 因為我們只遍歷了陣列一次，所以這種方法的時間複雜度是線性的，即 O(N)

空間複雜度 - 因為我們沒有使用任何額外空間，所以空間複雜度是 O(1)。

結論

在本文中，我們討論了三種不同的方法來對僅包含兩種元素（即只有 1 和 0）的陣列進行排序。