颜色分类

中等题，快速排序

示例

示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

解析

设置 3 个索引，left 指向数组的开始位置，right 指向数组的结束位置，index 指向数组的开始位置。

我们让 index 从头开始向后移动，在移动的过程中，它指向的元素会出现三种情况：

• 如果 index位置上的元素值为 0，则说明是红色，要放在最前面去，此时最前面的那个元素被 left 指着，所以让 index 指向的元素和 left 指向位置上的元素进行交换，交换完毕之后，说明 0 已经在它应该在的位置，即在整个数组的左区域，所以 left 可以向后移动，index 也向后移动
• 如果若 index 位置上的元素值为 1，则说明是白色，就应该放在中间，不用管它，继续移动 index
• 如果 index 位置上的元素值为 2，则说明是蓝色，要放在最后面，此时最后面的那个元素被 right 指着，所以让 index 指向的元素和 right 指向位置上的元素进行交换，交换完毕之后，说明 2 已经在它改在的位置，即在整个数组的右区域，right 向前移动，但由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种，到了 index 后，还需要继续观察一轮，所以 index 先不移动

代码

// 颜色分类( LeetCode 75 ):https://leetcode-cn.com/problems/sort-colors/  
class Solution {  
    public void sortColors(int[] nums) {  
        // left  指向数组的开始的位置，它指向的位置左侧都是 0  
        int left = 0;  
        // right  指向数组的结束的位置，它指向的位置右侧都是 2  
        int right = nums.length - 1;  
        // index 指向数组的开始位置  
        int index = 0;  
        // index 向后移动，当它越过 right 时跳出循环，不需要再判断了  
        // 因为此时说明 index 右侧的都已经是 2  
        while( index <= right ){  
            // 获取当前的元素值  
            int cur = nums[index];  
            // 如果 index 位置上的元素值为 0  
            if(cur == 0){  
              // 说明是红色，要放在最前面去  
              // 最前面的那个元素被 left 指着，所以让 index 指向的元素和 left 指向位置上的元素进行交换  
              swap(nums,left,index);  
              // index 可以向后移动  
              index++;  
              // left 可以向后移动，它的左侧区域都是 0  
              left++;  
              // 如果 index 位置上的元素值为 1  
            }else if(cur == 1){  
                // 说明是白色，就应该放在中间，不用管它，继续移动 index  
                index++;  
                // 如果 index 位置上的元素值为 2  
            }else if(cur == 2){  
                // 说明是蓝色，要放在最后面  
                // 所以让 index 指向的元素和 right 指向位置上的元素进行交换  
                swap(nums,right,index);  
                // 由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种  
                // 交换到了 index 后，还需要继续观察一轮，所以 index 先不移动  
                right--;  
            }  
        }  
    }  
    // 通过中间变量，交换两个元素的值  
    // nums[i] 的值变为了 nums[j] 的值   
    // nums[j] 的值变为了 nums[i] 的值   
    private void swap(int[] nums, int i ,int j){  
        // 使用临时变量 temp，保存 nums[i] 的值  
        int temp = nums[i];  
        // nums[i] 的值修改为 nums[j] 的值  
        nums[i] = nums[j];  
        // nums[i] 的值修改为 temp 的值  
        nums[j] = temp;  
    }  
}