快排之荷兰国旗问题

荷兰国旗问题

现有红白蓝三个不同颜色的小球，乱序排列在一起，请重新排列这些小球，使得红白蓝三色的同颜色的球在一起。这个问题之所以叫荷兰国旗问题，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。

问题分析

我们可以将这个问题视为一个数组排序问题。红白蓝分别对应数字0、1、2。红、白、蓝三色小球数量并不一定相同。

代码实现

public class NetherlandFlag {

    public static void main(String[] args) {
        int[] arr = {0,0,1,2,1,2,1,2,0,2,1,2,0,1,2,0,0,2,1,0,2,1,0,2,1,0,2,1,1,2,0,2,1,2,1,0};
        partition(arr,0,arr.length-1,1);
        for(int num : arr){
            System.out.print(num+" ");
        }
    }
    
    public static int[] partition(int[] arr,int L,int R,int num){
        int less = L-1;
        int more = R+1;
        int cur = L;
        while(cur<more){
            if(arr[cur]<num){
                swap(arr,++less,cur++);
            }else if(arr[cur]>num){
                swap(arr,--more,cur);
            }else{
                cur++;
            }
        }
        return new int[]{less+1,more-1};
    }
    
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

输出结果:

0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 

体会一下这行代码 :

swap(arr,++less,cur++);

代码思路说明：

只是需要用到三个索引：一个前索引less，一个当前索引cur，一个后索引more，cur指针遍历整个数组序列，当cur指针所指元素为0时，与++less指针所指的元素交换，current++；
current指针所指元素为1时，不做任何交换（即球不动），而后current++ ；
current指针所指元素为2时，与more指针所指的元素交换，而后，current指针不动，more-- 。

盗图说明（begin为less，并且less是左边界-1，more为end，是右边界+1）：

荷兰国旗问题解决思路.jpg

另外，如果目标数据是：

int[] arr = {7,3,5,1,2,5,6,8,10};
partition(arr,0,arr.length-1,5);

输出结果 ：

3 1 2 5 5 6 8 10 7 

比目标数字5小的在左侧，大的在右侧，但是左右两侧都是无序的。而快排则是通过递归，利用这种排序方式将整个数组排序。下一篇将会介绍快排。