Java 分治算法实战：快速排序与归并排序

分治算法

使用快速排序和归并排序解决相关问题，这两个算法均基于分治思想。

颜色分类

题目解析：将数组中 0 放在左边，1 放在中间，2 放在右边。

在双指针算法中有一个移动零的题目，就是将所有 0 元素移动到右边，但是非 0 元素相对位置不改变。那题使用双指针将其数组分为三部分，因此这题也可以将其数组分块。

left表示为 0 区域最右侧，i遍历数组，right表示 2 区域最左侧。使用这三个指针将这个数组分为了 4 部分。

class Solution {
    public void sortColors(int[] nums) {
        // 可以将其数组分为三部分
        // [0, left]: 全是 0
        // [left+1, i-1] 全都是 1
        // [i, right-1] 待扫描
        // [right, n-1] 全是 2
        int left = -1;
        int i = 0;
        int right = nums.length;
        while (i < right) {
            if (nums[i] == 0) {
                swap(nums, ++left, i++);
            } else if (nums[i] == 1) {
                i++;
            } else {
                swap(nums, --right, i);
                // 此时会将 right-1 元素放到 i 下标，但是这个元素没有扫描过，所以这里不可以让 i++
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tem  nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}