现在有一个包含n个物体的数组，其中物体颜色为颜色为红色、白色或蓝色，请对这个数组进行排序，让相同颜色的物体相邻，颜色的顺序为红色，白色，蓝色。
我们用0,1,2分别代表颜色红，白，蓝
注意：
本题要求你不能使用排序库函数
扩展：
一个非常直接的解法是两步的计数排序的算法
首先：遍历一遍数组，记录0,1,2的数量，然后重写这个数组，先将0写入，再将1写入，再将2写入
你能给出一个只用一步，并且能在常数级空间复杂度解决这个问题的算法吗？
<?php function sortColors($arr) { $num = count($arr); $redIndex = 0; $blueIndex = $num - 1; //如果i到了蓝色的开始位置,说明已经全部遍历了 for ($i = 0; $i < $blueIndex; $i ++) { //如果是蓝色,则换到后面,但是后面的需要继续判断,所以一直是蓝色可以循环 while ($arr[$i] == 2) { $tmp = $arr[$i]; $arr[$i] = $arr[$blueIndex]; $arr[$blueIndex] = $tmp; $blueIndex --; } //如果是红色,换到前面,然后继续,顺带可以判断一下后面的是不是红色 if ($arr[$i] == 0) { $tmp = $arr[$i]; $arr[$i] = $arr[$redIndex]; $arr[$redIndex] = $tmp; $redIndex ++; } print $i . json_encode($arr)."\n"; } return $arr; } $arr = [1,0,2,1,2,0,2,2]; $ret = sortColors($arr); print json_encode($ret);
