Sort Colors（颜色分类）

题目 / Problem

中文： 给定一个包含 n 个红色、白色或蓝色对象的数组 nums，要求原地排序，使相同颜色的对象相邻，并按照红、白、蓝的顺序排列。

使用整数 0、1 和 2 分别表示红色、白色和蓝色。不能使用语言内置的排序函数。

English: Given an array nums containing n objects colored red, white, or blue, sort the array in place so that objects of the same color are adjacent and ordered red, white, then blue.

The integers 0, 1, and 2 represent red, white, and blue, respectively. The library's sorting function may not be used.

示例 / Examples

Example 1

Input:  nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

数组中分别有两个 0、两个 1 和两个 2。原地排序后，所有 0 在前，接着是 1，最后是 2。
The array contains two 0s, two 1s, and two 2s. After in-place sorting, all 0s come first, followed by 1s and then 2s.

Example 2

Input:  nums = [2,0,1]
Output: [0,1,2]

约束 / Constraints

• n === nums.length
• 1 <= n <= 300
• nums[i] 只能是 0、1 或 2。
  Each nums[i] is either 0, 1, or 2.

进阶要求 / Follow-up

能否只遍历一次，并使用常数额外空间完成排序？
Can the array be sorted in one pass using only constant extra space?

解题思路：荷兰国旗算法 / Approach: Dutch National Flag

使用三个指针把数组划分为四个区域：
Use three pointers to divide the array into four regions:

• low：下一个 0 应放置的位置。
  low: the next position where a 0 should be placed.
• current：当前正在检查的位置。
  current: the position currently being examined.
• high：下一个 2 应放置的位置。
  high: the next position where a 2 should be placed.

在循环过程中保持以下不变量：
Maintain the following invariants during the loop:

[0, low)             全部是 0 / all 0s
[low, current)       全部是 1 / all 1s
[current, high]      尚未检查 / unknown
(high, nums.length)  全部是 2 / all 2s

只要 current <= high，未知区域就还没有处理完。
As long as current <= high, the unknown region has not been fully processed.

三种情况 / Three Cases

nums[current] === 0

把它与 nums[low] 交换。交换后，这个 0 已经位于左侧正确区域，因此 low 和 current 都向右移动。
Swap it with nums[low]. The 0 is now in its correct left region, so advance both low and current.

[nums[low], nums[current]] = [nums[current], nums[low]];
low++;
current++;

nums[current] === 1

1 已经属于中间区域，不需要交换，只移动 current。
The 1 already belongs in the middle region, so only advance current.

current++;

nums[current] === 2

把它与 nums[high] 交换，并将 high 向左移动。此时不能移动 current，因为从右侧交换过来的数字尚未检查。
Swap it with nums[high] and move high left. Do not advance current, because the value swapped in from the right has not been examined yet.

[nums[current], nums[high]] = [nums[high], nums[current]];
high--;

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} nums
 * @return {void} Do not return anything; modify nums in place instead.
 */
function sortColors(nums) {
  let low = 0;
  let current = 0;
  let high = nums.length - 1;

  while (current <= high) {
    if (nums[current] === 0) {
      [nums[low], nums[current]] = [nums[current], nums[low]];
      low++;
      current++;
    } else if (nums[current] === 1) {
      current++;
    } else {
      [nums[current], nums[high]] = [nums[high], nums[current]];
      high--;
    }
  }
}

执行过程 / Walkthrough

以 nums = [2,0,2,1,1,0] 为例：
For nums = [2,0,2,1,1,0]:

此时 current = 4、high = 3，未知区域为空，排序完成。
Now current = 4 and high = 3, so the unknown region is empty and sorting is complete.

为什么遇到 2 时不移动 current？ / Why Not Advance After a 2?

当 2 与 nums[high] 交换后，从右侧换到 current 位置的值可能是 0、1 或 2。它原本属于尚未检查区域，因此必须在下一轮继续检查。
After swapping a 2 with nums[high], the new value at current may be 0, 1, or 2. It came from the unknown region and must be examined in the next iteration.

例如：
For example:

[2, 1, 0]
 ^     ^
current high

交换后 / After swapping:
[0, 1, 2]
 ^
current

如果交换后立刻执行 current++，新换来的 0 就不会被处理。
If current were advanced immediately, the newly swapped 0 would never be processed.

与计数法对比 / Comparison with Counting

另一种方法是先统计 0、1、2 的数量，再按数量覆盖原数组。它同样使用 O(1) 额外空间和 O(n) 时间，但需要两次遍历。
Another solution counts the number of 0s, 1s, and 2s, then overwrites the array. It also uses O(1) extra space and O(n) time, but requires two passes.

荷兰国旗算法满足进阶要求：一次遍历并使用常数额外空间。
The Dutch National Flag algorithm satisfies the follow-up: one pass with constant extra space.

复杂度 / Complexity

• 时间复杂度 / Time: O(n)，每个元素最多被常数次检查或交换。
  Every element is examined or swapped only a constant number of times.
• 空间复杂度 / Space: O(1)，只使用三个指针。
  Only three pointers are used.

易错点 / Common Pitfalls

• 题目要求原地修改数组，不需要返回新数组。
  Modify the input array in place; no new array needs to be returned.
• 不能使用内置的 sort()。
  Do not use the built-in sort() function.
• 循环条件应为 current <= high，因为 high 位置仍属于待检查区域。
  Use current <= high because the element at high is still in the unknown region.
• 遇到 0 时，low 和 current 都要加一。
  After processing a 0, increment both low and current.
• 遇到 2 时只减少 high，不要立即增加 current。
  After processing a 2, decrement only high; do not immediately increment current.