有不同的方法來對只包含兩個元素（即只有1和0）的陣列進行排序。我們將討論三種不同的方法來實現這個目標。第一種方法簡單地使用預先定義的sort()函數對給定的陣列進行排序。第二種方法是計數排序方法，我們將計算0和1的數量，然後透過先寫入0的次數來更新數組，然後寫入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 ]
在此方法中，我們將直接使用 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
在這個方法中，我們將簡單地計算數組中 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)。雖然我們使用了額外的變量，但由於它們是線性的，所以空間複雜度是常數。
在這種方法中，我們將保留兩個指針，即start和end。我們將同時使用start指標從陣列的開頭（索引為0）開始遍歷，並使用end指標從末尾（索引為len-1）開始遍歷。
我們的任務是將所有的1排列到陣列的最右邊，這將自動將所有的0排列到陣列的左邊。
我們從初始索引開始，如果找到的元素為 1，我們將與索引「end」處的元素交換它，並將結束指標遞減 1。
如果找到的元素是0，那麼就不需要執行任何交換操作，因為它已經在最左邊的位置，我們只需將起始指標增加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）的陣列進行排序。
以上是對一個包含兩種類型元素的陣列進行排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！
