使用C ++对0、1和2的数组进行排序

给定0、1和2的数组，请按以下顺序对元素进行排序，以使所有零先于1出现，而所有2则最后出现。我们必须就地对数组的所有元素进行排序。

我们可以使用DNF（荷兰国旗）排序算法解决此问题。例如，

输入1 -

arr[ ]= {2,0,0,1,2,1 }

输出-

0 0 1 1 2 2

说明-使用DNF排序算法对给定的包含0,1和2的元素数组进行排序，它将输出显示为{0,0,1,1,2,2}。

输入- 2 -

arr[ ]= {0,1,1,2,1,1,0}

输出-

0 0 1 1 1 1 2

说明-使用DNF排序算法对给定的包含0,1和2的元素数组进行排序，它将输出显示为{0,0,1,1,1,1,2，}。

解决这个问题的方法

在给定的0、1和2数组中，我们可以使用DNF排序算法。

DNF排序算法-该算法需要3个指针，通过交换必要的元素来遍历整个数组。

• 在数组的开头创建一个低指针，在数组的末尾创建一个高指针。

• 找到数组的中点，并创建一个中点指针，该指针将从数组的开始一直循环到结尾。

• 如果数组的中指针为“ 0”，则交换指向低的元素。递增低指针和中指针。

• 如果数组的中指针为“ 2”，则将其与指向高位的元素交换。递增中指针，递减高指针。

• 如果数组的中指针为“ 1”，则增加中指针。

示例

#include<iostream>
using namespace std;
void dnfsort(int a[], int n){
   int low= 0;
   int high= n-1;
   int mid=0;
   while(mid<=high){
      if(a[mid]==0){
         swap(a[mid],a[low]);
         mid++;
         low++;
      }
      if(a[mid]==1){
         mid++;
      }
      if(a[mid]==2){
         swap(a[mid],a[high]);
         high--;
      }
   }
}
int main(){
   int a[]= {1,0,0,2,1,1,0,0,1};
   int n= sizeof(a)/sizeof(int);
   dnfsort(a,n);
   for(int i=0;i<n;i++){
      cout<<a[i]<<" ";
   }
   return 0;
}

运行上面的代码将生成如下输出：

0 0 0 0 1 1 1 1 2