<span>荷兰国旗问题</span>
荷兰国旗问题：
现有红，白，蓝三个不同颜色的小球，乱序排列在一起，重新排列这些小球，使得红白蓝三色的同颜色的球在一起。
问题分析：
问题转换为：给定数组A[0,1,...,N-1]，元素只能取0，1，2三个值，设计算法使得数组重新排列成“000...111..222”的形式。
可以使用三个游标，begin=0，cur=0，end=N-1。
程序实现：
1 /*************************************** 2 FileName HollandFlag.cpp 3 Author : godfrey 4 CreatedTime : 2016/5/4 5 ****************************************/ 6 #include <iostream> 7 #include <cstring> 8 #include <vector> 9 #include <algorithm> 10 #include <stdio.h> 11 #include <stdlib.h> 12 13 using namespace std; 14 15 void HollandFlag(int* A,int size){ 16 int begin = 0; 17 int end = size - 1; 18 int cur = 0; 19 while(cur <= end){ 20 if(A[cur] == 2){ 21 swap(A[cur],A[end]); 22 end --; 23 } 24 else if(A[cur] == 1){ 25 cur ++; 26 } 27 else if(A[cur] == 0){ 28 swap(A[cur],A[begin]);//这里简化了步骤，提醒：cur与begin是否相同，分情况考虑 29 begin ++; 30 cur ++; 31 } 32 } 33 } 34 int main() 35 { 36 int a[] = {0,1,2,0,0,2,1,2,1,2,2,1,1,0}; 37 int size = sizeof(a)/sizeof(int); 38 for(int i=0;i<size;i++){ 39 cout<<a[i]<<" "; 40 } 41 cout<<endl; 42 HollandFlag(a,size); 43 cout<<"-----------After adjusting ------------"<<endl; 44 for(int i=0;i<size;i++){ 45 cout<<a[i]<<" "; 46 } 47 cout<<endl; 48 return 0; 49 }
运行结果：
转载请注明出处：
C++博客园：godfrey_88
http://www.cnblogs.com/gaobaoru-articles/
网易有道公司氛围 38人发布
