对包含两种元素的数组进行排序

---

对仅包含两种元素（即只有 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）的数组进行排序。