public static void main(String[] args) {
    int[] arr = {3, 5, 6, 3, 4, 5, 2, 6, 9, 0};
    int num = 3;	// 要求左边比3小，中间等于3，右边比3大
    dutchFlag(arr, num);
    System.out.println(Arrays.toString(arr));
}

public static void dutchFlag(int[] arr, int num) {
    if (arr == null || arr.length < 2) return;

    dutchFlag(arr, 0, arr.length - 1, num);
}

public static void dutchFlag(int[] arr, int L, int R, int X) {
    if (L >= R) return;
    
    // 不需要递归，因为题目没说左右要有顺序
	partition(arr, L, R, X);
}

// 分区函数，将arr分为：【小于区，等于区，大于区】
public static void partition(int[] arr, int L, int R, int X) {
    int less = L - 1;
    int more = R;
    // 此处跟快排的区别是：快排最后会将基准值和右区左边界值左交换，并返回基准值坐标然后递归
    while (L <= more) {
        if (arr[L] < X) {
            swap(arr, ++less, L++);
        } else if (arr[L] > X) {
            swap(arr, more--, L);
        } else {
            L++;
        }
    }
}

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}