75. 颜色分类

题意：

解题思路：

思路：
1.最后的结果是所有的0在前, 所有的2在后,
    1.1 首先从前后向扫描0, 把所有0swap到头部,然后缩小范围，l++；
    1.2 然后从前向后扫描2, 把所有2swap到尾部,确定2是最后一个后，缩小范围，r--；

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function sortColors(&$nums) {
        return $this->sortThreeColorsCount($nums);
        $left = 0;
        $right = count($nums) - 1;
        for ($i = 0; $i <= $right; $i++) {
            if ($nums[$i] == 0) {
                $this->swap($nums, $i, $left);
                $left++;
            } elseif ($nums[$i] == 2) {
                $this->swap($nums, $i, $right);
                $right--;
                      $i--;
            }
        }
    }
    function swap(&$nums, $i, $j) {
        $temp = $nums[$i];
        $nums[$i] = $nums[$j];
        $nums[$j] = $temp;
    }
    function sortThreeColorsCount(&$nums) {
        if ($nums == null || count($nums) == 0) return;
        $cnt0 = $cnt1 = $cnt2 = 0;
        foreach($nums as $num) {
            if ($num == 0) ++$cnt0;
            else if ($num == 1) ++$cnt1;
            else ++$cnt2;
        }
        $k = 0;
        for ($i = 0; $i < $cnt0; ++$i) $nums[$k++] = 0;
        for ($i = 0; $i < $cnt1; ++$i) $nums[$k++] = 1;
        for ($i = 0; $i < $cnt2; ++$i) $nums[$k++] = 2;
    }
}

GO代码实现：

func sortColors(nums []int)  {
    l, r := 0, len(nums)-1
    for i := 0; i <= r; i++ {
        if nums[i] == 0 {
            swap(nums, i, l)
            l++
        } else if nums[i] == 2 {
            swap(nums, i, r)
            // i-- ？因为有可能挪过来的数据还是2，
            //所以需要重新检查（下一次）i 的数据
            i--
            r--
        }
    }
}
func swap(nums []int, i,j int){
    nums[i], nums[j] = nums[j], nums[i]
}