有不同的方法来对只包含两种元素（即只有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中文网其他相关文章！
