正文
算法笔记_051:荷兰国旗问题（Java）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
目录
1 问题描述
2 解决方案
1 问题描述
现有n个红白蓝三种不同颜色的小球，乱序排列在一起，请通过两两交换任意两个球，使得从左至右的球依次为红球、白球、蓝球。这个问题之所以叫荷兰国旗，是因为将红白蓝三色的小球弄成条状物，并有序排列后正好组成荷兰国旗。
2 解决方案
为了方便编码与讨论，用数字0表示红球，数字1表示白球，数字2表示蓝球，所以最后生成的排列为0,1,2。
解决该问题，只需先设定三个用于指定元素的下标指针（PS：在Java中没有指针，此处方便描述）:一个前指针begin，一个中指针current，一个后指针end。Current指针遍历整个数组序列：
（1）当current指针所指元素为0时，与begin指针所指的元素交换，而后current++，begin++；
（2）当current指针所指元素为1时，不做任何交换，而后current++；
（3）当current指针所指元素为2时，与end指针所指的元素交换，而后current指针不动，end--.
那么，为什么在上述第（3）步中，current指针不动？因为如果end所指元素为0时，此时current指针就不能动。
具体代码如下：
package com.liuzhen.array_2;
public class HollandFlagProblem {
//输出荷兰国旗问题后的排序结果，时间复杂度为O(n)，空间复杂度为O(1)
public void getHollandSort(int[] A){
int begin = 0;
int current = 0;
int end = A.length - 1;
while(current <= end){
//值得注意的是：此处if语句是使用if-else if-else if，而没有使用if-if-if。这样使用保证每一次循环只执行一个条件，
//否则，若使用if-if-if，可能会形成一次循环执行两到三个if条件，造成最终结果错误（PS:即在循环结束前，发生current > end）
if(A[current] == 0){
swap(A,begin,current);
begin++;
current++;
}
else if(A[current] == 1)
current++;
else if(A[current] == 2){
swap(A,current,end);
end--;
}
}
//输出排完序后的数组A相应元素
System.out.println("对数组A进行划分后的元素顺序为：");
for(int i = 0;i < A.length;i++)
System.out.print(A[i]+" ");
}
//交换数组A中m位置和n位置上元素的值
public void swap(int[] A,int m,int n){
int temp = A[m];
A[m] = A[n];
A[n] = temp;
}
public static void main(String[] args){
HollandFlagProblem test = new HollandFlagProblem();
int[] A = {2,0,2,0,0,2,1,1,0,2,1,0,1,2,0,1,2,0,1,0,2,1,0,2,0,1,2,0,1,2,0,2,1,0};
test.getHollandSort(A);
}
}
运行结果：
对数组A进行划分后的元素顺序为：
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2
参考资料：
1.《编程之法面试和算法心得》 July 著
