对一个包含两种类型元素的数组进行排序

有不同的方法来对只包含两种元素（即只有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 
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
输出
在编译时，上述程序将产生以下输出 - 
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 
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
输出
编译时，它将产生以下输出 - 

							

								
								

									数组应用&二维数组 word版
									
所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分他们的变量的集合，这个名字称为数组名，编号称为下标。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。数组是在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来的一种形式。这些按序排列的同类数据元素的集合称为数组。 数组应用&二维数组目录 1. 数组的简单应用2. 数组排序3. 数组查找4. 数组的使用思想5. 查表法6. 二维数组7. 数组综合
								
								下载 
							
						
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 
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
输出
After sorting the array, the array obtained is 0 0 0 1 1 1 1 1

时间复杂度 - 由于我们只遍历数组一次，因此这种方法的时间复杂度是线性的，即 O(N)
空间复杂度 − 由于我们没有使用任何额外的空间，所以空间复杂度为 O(1)。
结论
在本文中，我们讨论了三种不同的方法来对仅包含两种类型元素（即仅 1 和 0）的数组进行排序。