看懂题目后，直觉是 —— new一个一样大小的数组，遍历一遍原数组，数出来0、1、2的个数，然后按照个数直接写入新数组。但题目要求在原地弄，也就是不能通过我们这样拷贝的方式。
并且进阶要求只遍历一遍。空间限制我们，时间也限制我们？那还怎么弄？因为要么牺牲空间换时间，要么牺牲时间换空间。他的要求不合理呀？再仔细一看，其实进阶要求的并不是时间复杂度在O(n)，而是只遍历一遍。直觉就告诉我们，遍历这一遍的时候必须狠狠折腾。
法（一）三指针 可以不用看
灵感来自于快排。
从左到右遍历数组nums，如果是0，都放到左边，如果是2，都放到右边。维护两个指针，一个left指向下一个放0的位置，一个right指向下一个放2的位置。再用一个指针去遍历。遍历到第i个时，有三种情况嘛，分三种情况讨论。
1. 当nums[i]==0时，放到左边去，具体操作是把指针i和指针left指向的元素交换一下。
① 重置left指针：通过while循环，重置left指针到下一个放0的位置。
② 重置i指针：因为新换到了i位置上一个数字，所以下次还是遍历i位置，所以i指针不变
2. 当nums[i]==1时，继续遍历下一个。
3. 当nums[i]==2时，放到右边去，具体操作是把指针i和指针right指向的元素交换一下。
① 重置right指针：通过while循环，重置right指针到下一个放2的位置。
② 重置i指针：因为新换到了i位置上一个数字，所以下次还是遍历i位置，所以i指针不变
然后捏，是通过用例测出来的一个特殊情况。会出现这样一种情况，i==left且nums[i]=nums[left]=0，这种情况就不要去交换了，直接i和left都加一。（PS ：因为我们的left指针和i指针都是从左往右的嘛，所以才会在交换0的时候遇到这种情况，交换2的时候不存在这种情况。）
class Solution { public void sortColors(int[] nums) { //定义left：指向下一个放0的位置 //定义right:指向下一个放2的位置 //定义i: 当前遍历的位置 int left=0; int right=nums.length-1; while(left<nums.length && nums[left]==0) left++; //初始化 while(right>=0 && nums[right]==2) right--; //初始化 int i=left; //初始化 while(i<=right){ if(nums[i]==0){ if(i==left){left++;i++;} //出错案例测出来的情况 else{swap(nums,left,i); while(nums[left]==0) left++;} //因为新换到了i位置上一个数字，所以下次还是遍历i位置，所以i指针不变 } else if(nums[i]==1){i++;}//什么也不干，直接遍历下一个 else if(nums[i]==2){swap(nums,i,right);while(nums[right]==2) right--;} } } public void swap(int[] nums,int a,int b){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }法（二）三指针 这个写起来更好实现
还有个更简单的思路，同样也是三指针，这次维护的是下一个放0的位置，下一个放1的位置。
同样也分三种情况：
1.nums[i]==0时，把这个0往前插，zero和i之间的整体后移一位
2.nums[i]==1时，把这个1往前插，one和i之前的整体后移一位
3. nums[i]==2时，继续遍历下一个
class Solution { public void sortColors(int[] nums) { //定义zero：下一个放0的位置 //定义one：下一个放1的位置 //定义i：当前遍历的位置 int zero=0; while(zero< nums.length && nums[zero]==0) zero++; //初始化 int one=zero; while(one< nums.length && nums[one]==1) one++; //初始化 int i=one; //初始化 while (i<nums.length){ if(nums[i]==0){ //[zero,i-1]闭区间内的元素整体后移一位 for(int j=i;j>zero;j--){nums[j]=nums[j-1];} //插入0 nums[zero]=0; //重置指针 zero++; i++; one++; //坑在这里，别忘了1的指针也跟着往右移了一位 } else if(nums[i]==1){ //[one,i-1]闭区间内的元素整体后移一位 for(int j=i;j>one;j--){nums[j]=nums[j-1];} //插入0 nums[one]=1; //重置指针 one++; i++; } else if(nums[i]==2) i++; } } }
