* 设有一个条块序列，每个条块为红（0）、白（1）、蓝（2）三种颜色的一种
* 假设该序列采用顺序存储，设计一个时间复杂度为O(n)的算法，使得这些条块按
* 红、白、蓝的顺序排好，即排成荷兰国旗的图案
* eg:初始化102100122102
* 目标：000011112222
* <p>
* 解决方案：
* 用0~i表示0元素区间
* 用k~n-1表示2元素区间
* 中间部分为1元素区间
* 用j从头开始扫描顺序表L中部的所有元素
* 每次循环{
* j指向1，保持不动 j++
* j指向0  i++, i,j换位置 j++
* j指向2，k--,j,k交换，
* }

public class NetherlandsFlag {

    public static void main(String[] args) {
        int[] arr = {1, 0, 2, 1, 0, 0, 1, 2, 2, 1, 0, 2};
        sortArr(arr);
        for (int i : arr) {
            System.out.println(i);
        }

    }

    public static void sortArr(int[] arr) {
        int i = -1;
        int j = 0;
        int k = arr.length;
        while (j < k) {
            if (arr[j] == 0) {
                i++;
                swapIntegers(arr, i, j);
                j++;
            } else if (arr[j] == 2) {
                k--;
                swapIntegers(arr, k, j);
            } else {
                j++;
            }
        }

    }

    public static void swapIntegers(int[] array, int index1, int index2) {
        int tmp = array[index2];
        array[index2] = array[index1];
        array[index1] = tmp;
    }

}