75. Sort Colors

题目

给定一个数组 nums ，这个数组有 n 个对象 红，白，蓝。将它们本地排序使得相同的颜色相邻，并按红，白，蓝的顺序排列。
红白蓝分别用 0,1,2 表示。

解析

用排序算法很容易做到这一点。而元素本身是有限的，我们未知的只是 1 元素的上下界，在这个问题里，1元素的上下界可以转换为 0 元素的下界和 1 元素的上界。考虑左右指针，指向0元素和1元素的上下界。
初始时 p1= 0 p2=n-1
然后从左往右遍历，遇到 2 就交换到 p2 并使 p2--。
遇到 0 交换到 p1，并使p1++
遇到 1 忽略。直到小于 p2 指针。

伪代码

p1=0
p2=n-1
for i<=p2
  if nums[i] == 0
    swap(nums[p1],0)
    p1++
  if nums[i] == 2
    swap(nums[p2],2)
    p2--

代码

func sortColors(nums []int)  {
    p1:=0
    p2:=len(nums)-1
    for i:=0;i<=p2; {
        if nums[i] == 0 {
            nums[p1],nums[i] = nums[i],nums[p1]
            i++
            p1++
        }else if nums[i] == 2 {
            nums[p2],nums[i] = nums[i],nums[p2]
            p2--
        } else {
            i++
        }
    }
}

image.png

后记

1. 要确定 i 指针一定是小于等于 p2 的。否则重复交换，就会出错。