问题
题目出自Leetcode：
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
分析
这个问题本质上就是排序，因此方法很多。但是我这里对“进阶”中所说的“仅使用常数空间的一趟扫描算法”这个条件很感兴趣，所以尝试着去实现这个条件下的方法。
我们可以注意到，这个问题里的数组元素只有3种：0、1、2（当然，就算是其它的也行，关键是只有“3种”）。所以可以这么考虑，对数组进行扫描，遇到2的时候，我们就把它移出来，然后扔到数组最后。遇到0的时候，我们也把它移出来，扔到数组最前。
这么扫描操作一轮之后，实际上数组就已经按照0、1、2的顺序排好序了。直接在原数组上操作即可，也不需要额外的数组和空间。
实现
先实现一个数组生成器吧，用来生成任意长度的随机数组，数组元素可能是0、1、2。
function createArr(len) {
return new Array(len).fill(null).map(() => parseInt(Math.random() * 3))
}
然后是排序函数：
function sort(arr) {
let len = arr.length;
let pushCount = 0;
for (let i = 0; i < len; i++) {
if (pushCount >= len - i) break; // 在把2往后扔的时候,我们对2进行计数. 如果剩余的长度跟2的个数已经一致了,就可以判断出后面已经全部是2了,没有别的可能了
if (arr[i] === 2) {
for (let j = i; j < len; j++) {
arr[j] = arr[j + 1];
}
arr[len - 1] = 2;
pushCount ++;
i--;
} else {
if (arr[i] === 0 && i != 0) {
for (let j = i - 1; j >= 0; j--) {
arr[j + 1] = arr[j];
}
arr[0] = 0;
}
}
}
return arr
}
这里需要注意几个点：
1）如果第一个元素就是0，那就别往数组最前面扔了，因为人家本来就是在最前面。
2）在把2往数组最后扔的时候，后面的元素会前移。也就是说，2后面的元素会移动到当前位置，这时需要对这个新移动过来的元素也进行一次判断，所以循环的索引标记 i 不能马上自增1。我们在将2扔入数组末尾的同时，让 i 先自减少1，然后在循环条件里 i 自增1 ，先减后增，就相互抵消了，相当于i没变，仍然停留在当前索引下的元素进行操作。
i - -;
3）我们其实不会把整个数组全部扫描完毕。想一想，在把2往数组最后扔的时候，到一定程度，数组最后就全是被我们扔过去的2了。这时实际上排序已经完成，没必要继续扫描了。通过定义一个pushCount变量，用来记录我们扔了多少次的2。每扔一次2，就让pushCount加1。当满足pushCount等于数组长度减去当前索引的时候，就可以停止扫描了。数组长度减去当前索引就是“数组剩余的元素”，如果剩余的元素跟我们扔2的次数（实际就是2的个数）一致，那意思不就是“剩余的元素已经全都是2”了么？此时整个排序结束。
if (pushCount >= len - i) break;
尝试
来试一下，先生成一个随机乱序的数组：
let arr = createArr(100)
输出：
[
1, 0, 0, 2, 1, 0, 0, 1, 0, 1, 1, 0,
2, 0, 2, 2, 2, 1, 2, 0, 1, 2, 2, 2,
1, 0, 1, 1, 0, 0, 0, 1, 1, 2, 0, 0,
1, 1, 2, 2, 0, 1, 0, 2, 0, 1, 0, 1,
1, 1, 2, 2, 1, 1, 2, 1, 2, 2, 0, 0,
2, 2, 2, 2, 2, 1, 0, 2, 2, 2, 0, 2,
1, 0, 0, 2, 1, 0, 2, 0, 2, 2, 0, 1,
2, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 1,
2, 2]
排序：
sort(arr)
结果：
[
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2
]