75. Sort Colors

本题刚毕业的时候做过，其实这次也算是大概知道思路，就是quicksort的变种，非常接近解出了，但还是没做出来。
思路：

• 设定两个pivot：
  • p0: p0右边的所有元素都是0，p0本身大于0
    
  • p2: p2左边的所有元素都是2，p2 本身小于2
    

• 从第一个点(curr)访问到p2所在点，结束，要注意，要访问所有的点

  • curr如果是0:
    • 交换该点和p0
      
    • curr向右移动1
      
    • p0向右移动1
      
  • curr如果是1:
    • curr向右移动1
      
  • curr如果是2:
    • 交换curr和p2
      
    • p2左移1
      
    • curr不动
      ```java class Solution { public void sortColors(int[] nums) { int p0 = 0; int i = 0; int p2 = nums.length - 1; while (i <= p2) { if (nums[i] == 0) { swap(nums, i, p0); ++p0; ++i; } else if (nums[i] == 1) { ++i; } else { swap(nums, i, p2); —p2; } } }

  private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } ```