题目描述
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。
进阶：你能想出一个仅使用常数空间的一趟扫描算法吗？
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
思路&js代码
1、插入排序
对 nums 执行插入排序，也就是对 i=0,1,2,…,n−1 依次执行如下过程：
- 现在前缀 nums[0] 到 nums[i−1] 是有序的，把 nums[i] 插入这个有序前缀，从而把前缀 nums[0] 到 nums[i] 变成有序的。
- 算法执行完后，nums 就是一个有序数组了。
var sortColors = function(nums) {
let p0 = 0, p1 = 0; // 0的数量是p0，0和1的数量是p1
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
nums[i] = 2;
if (x <= 1) {
nums[p1++] = 1;
}
if (x === 0) {
nums[p0++] = 0;
}
}
};2、双指针
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function(nums) {
let zero = 0; // `zero` 指针，表示 0 的右边界
let two = nums.length - 1; // `two` 指针，表示 2 的左边界
let i = 0; // `i` 为当前遍历指针
while (i <= two) { // 遍历数组，直到 `i` 超过 `two`
if (nums[i] === 0) {
// 0 交换 `nums[i]` 和 `nums[zero]`，然后 `zero++` 和 `i++`
[nums[i], nums[zero]] = [nums[zero], nums[i]];
zero++;
i++;
} else if (nums[i] === 1) {
// 1 位置正确，直接 `i++`
i++;
} else {
// 2 交换 `nums[i]` 和 `nums[two]`，然后 `two--`（但 `i` 不变）
[nums[i], nums[two]] = [nums[two], nums[i]];
two--;
}
}
};