有不同的方法来对只包含两种元素（即只有1和0）的数组进行排序。我们将讨论三种不同的方法来实现这个目标。第一种方法简单地使用预定义的sort()函数对给定的数组进行排序。第二种方法是计数排序方法，我们将计算0和1的数量，然后通过首先写入0的次数来更新数组，然后写入1的次数。在最后一种方法中，我们使用了双指针方法。

问题陈述

我们被给定一个只包含1和0的数组。我们的任务是将所有的0和1排列，使得1在数组的最右边，0在数组的左边

Example

示例

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) 时间并按升序返回数组。

Example

示例

下面是一个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，这将自动表示所需的排序数组。

这是一种简单的方法，但它会向数组中插入新的值，而不仅仅是交换它们的位置，因此这种方法不高效。

Example

示例

下面是使用 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排列到数组的左边。

我们从初始索引开始，如果找到的元素为 1，我们将与索引“end”处的元素交换它，并将结束指针递减 1。

如果找到的元素是0，那么就不需要执行任何交换操作，因为它已经在最左边的位置，我们只需将起始指针增加1即可。

Example

示例

以下是实现此方法的代码 -

#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）的数组进行排序。