数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 C++ 对包含 0、1 和 2 的数组进行排序
给定一个包含 0、1 和 2 的数组，将元素按顺序排序，使得所有 0 都位于 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
更新于: 2021年2月5日
800 次浏览
广告