首页 > 代码库 > 荷兰国旗问题
荷兰国旗问题
荷兰国旗有三横条块构成，自上到下的三条颜色依次为红，白，蓝。现有若干由红，白，蓝三种颜色的条块序列，要将它们重新排列使所有相同颜色的条块在一起。本问题要求将所有红色的条块放在最左边，所有白色的条块放在中间，所有蓝色的条块放在最右边。
//条块颜色依次存放在L[0,1,2........n-1]中算法利用快速排序思想,将整个序列按红，白，蓝排序。
思想：
设置三个整数r,w,b,其中r指向红色条块区域的下一个单元,w指向白色区域的下一个单元,b指向蓝色条块区的下一个单元。
开始时，令r和w为0,b为n-1,w相当于快速排序的low指针,b相当于快速排序的的hight指针。
最终L[0....r-1]存放红色条块,L[r....w-1]存放白色区域,L[w....n-1]存放蓝色条块区域。
检查L[w]有一些三种情况：
（1）如果L[w]=2它已经在白色区域,w直接加1.
（2）如果L[w]=3则将它加到蓝色区域头部,即L[w]与L[b]交换，且b减1.
（3）如果L[w]=1,此时先将白色区域的第一个元素（即红色区域的下一个单元）移动到白色区域末尾，再将它加到红色区域的下一个
单元.即L[w]与L[r]交换，且r和w同时加1.
重复上述操作直到w>b为止。
#define LOCAL#include<cstdio>#include<cstdlib>#include<iostream>using namespace std;typedef int ElemType;const int maxSize=45;void Sort(int L[],int n){ int x,r,w,b; r=w=0; //相当于low=0 b=n-1; //相当于hight while(w<=b) { x=L[w]; if(x==1) { L[w]=L[r]; w++; L[r]=x; r++; }else if(x==2){ w++; }else{ L[w]=L[b]; L[b]=x; b--; } }}void Output(int L[],int n){ for(int i=0;i<n;i++) { cout<<L[i]<<","; } cout<<endl;}int main(){#ifdef LOCAL freopen("data.in","r",stdin); freopen("data.out","w",stdout);#endif int i=0,L[maxSize]; for(i=0;i<maxSize;i++) { cin>>L[i]; } Sort(L,maxSize); Output(L,maxSize); return 0;}
荷兰国旗问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。