資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告