1. 概述

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

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

注意:

不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]

输出: [0,0,1,1,2,2]

2. 解题

<?php
class Solution
{
    /**
     * @param Integer[] $nums
     * @return NULL
     */
    public function sortColors(&$nums)
    {
        for ($i = 1; $i < count($nums); $i++) {
            $j = $i;
            while ($j > 0) {
                if ($nums[$j] < $nums[$j - 1]) {
                    $exchange = $nums[$j];
                    $nums[$j] = $nums[$j - 1];
                    $nums[$j - 1] = $exchange;
                }
                $j--;
            }
        }
        return;
    }
    /**
     * todo
     * @param Integer[] $nums
     * @return NULL
     */
    public function sortColors2(&$nums)
    {
        $white = -1;
        $left = -1;
        $right = count($nums) - 1;
        $min = $nums[0];
        for ($i = 1; $i <= $right; $i++) {
            ($nums[$i] < $min) && $min = $nums[$i];
        }
        // 遍历一次数组
        for ($i = 0; $i <= $right; $i++) {
            if ($left == -1 && $nums[$i] == $min) {
                $left = $i;
            }
            if ($nums[$i] == 0) {
                isset($nums[$left + 1]) && $this->swap($nums, $i, ++$left);
            } elseif ($nums[$i] == 2) {
                isset($nums[$right - 1]) && $this->swap($nums, $i, --$right);
            }
        }
        return;
    }
    private function swap(&$nums, $i, $j)
    {
        $tmp = $nums[$i];
        $nums[$i] = $nums[$j];
        $nums[$j] = $tmp;
    }
}
$nums = [2, 0, 2, 1, 1, 0, 0, 0, 0, 1, 2, 0, 2, 1, 0, 0, 2, 2, 2, 0, 0, 0, 1, 1, 2];
// echo implode(',', $nums) . "\n";
$cls = new Solution();
// $cls->sortColors($nums);
$cls->sortColors2($nums);
echo implode(',', $nums) . "\n";