题目：

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [0]
输出：[0]

示例 4：

输入：nums = [1]
输出：[1]

提示：

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

进阶：

你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？

---

题目说了争取可以一次扫描也就是一次遍历通过
如果多次扫描那有什么思路呢

刚开始先讲解多次扫描的思路点：

思路一：

通过遍历多少个数字然后依次添加到数组中去
这个已经遍历了好几次，虽然不符合条件的限定
展示c++版本
（主要是为了引出java的一个知识点，后面还是会用java来书写）

class Solution {
public:
    void sortColors(vector<int>& nums) {
        //只有 0 ，1,2  三种颜色
        int num0=0,num1=0,num2=0;
        for(int &x: nums) {
            if(x==0) num0++;
            else if(x==1) num1++;
            else num2++;
        }
        int k=0;
        while(num0--) nums[k++] = 0;
        while(num1--) nums[k++] = 1;
        while(num2--) nums[k++] = 2; 

    }
};

因为java的while类型不能这样使用，这样使用会出错

这种错误的意思大致就是

与C / C ++不同，它不会隐式转换为boolean。您必须将条件明确声明为boolean。

所以在改装的时候应该要这样书写

class Solution {
    public void sortColors(int[] nums) {
        //只有 0 ，1,2  三种颜色
        int num0=0,num1=0,num2=0;
        for(int num: nums) {
            if(num==0) num0++;
            else if(num==1) num1++;
            else num2++;
        }
        int k=0;
        while(num0!=0) {nums[k++] = 0;num0--;}
        while(num1!=0) {nums[k++] = 1;num1--;}
        while(num2!=0) {nums[k++] = 2; num2--;}
        
    }
}

---

思路二：

思路一的遍历次数取决于有多少个不同的数字
而思路二需要使用两次遍历，同样也要取决不同的数字，但比思路一好一些

主要思路是
遍历所有的数组，将其0找到并且替换，之后记住替换完之后，0的位置下标
从0的位置下标再次遍历，并找到1并且替换，之后剩下的就是2了

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int ptr = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
        for (int i = ptr; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
    }
}

---

思路三：

这回的思路是 一次遍历

以下思路都是参考官方解释
因为太绕太难想了
官方解释

区分于上一个思路，可以同时使用两指针，一个指针在前，一个指针在后

将 nums[i] 与 nums[p2] 进行交换之后，新的nums[i] 可能仍然是 2，也可能是 0。然而此时我们已经结束了交换，开始遍历下一个元素nums[i+1]，不会再考虑nums[i] 了，这样我们就会得到错误的答案
因此，当我们找到 2 时，我们需要不断地将其与nums[p2] 进行交换，直到新nums[i] 不为 2

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; ++i) {
            while (i <= p2 && nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[p2];
                nums[p2] = temp;
                --p2;
            }
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                ++p0;
            }
        }
    }
}

---

思路四：

和思路三大同小异
但是我竟然觉得 这个比思路三还要绕

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
                ++p1;
            } else if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                if (p0 < p1) {
                    temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                }
                ++p0;
                ++p1;
            }
        }
    }
}