目录
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 著
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
