1. 问题背景与核心需求
这道题目来自著名的LeetCode Hot 100系列，编号75题"颜色分类"(Sort Colors)。作为算法面试中的经典问题，它要求我们原地(in-place)对包含红、白、蓝三种颜色的数组进行排序，其中用0、1、2分别代表这三种颜色。
在实际开发中，这类问题常见于图像处理领域。比如在Photoshop等软件中，当我们需要对像素点的RGB值进行特定排序时，就会遇到类似的场景。题目给出的约束条件——只能使用常数空间且必须一趟扫描完成——模拟了内存受限环境下的真实需求。
2. 算法思路解析
2.1 暴力解法的局限性
最直观的解法是直接调用语言内置的排序函数，但这显然违背了题目考察的本意。另一种思路是两次遍历：第一次统计0、1、2的个数，第二次重写数组。虽然时间复杂度是O(n)，但需要两趟扫描。
2.2 荷兰国旗问题
这道题实际上是经典的"荷兰国旗问题"的变种，由计算机科学家Edsger Dijkstra提出。核心思想是通过三个指针将数组划分为三个区域：
- left指针左侧全是0
- right指针右侧全是2
- 中间是未处理的1
2.3 单次遍历算法
最优解采用三指针法，只需要一次遍历：
- 初始化left=0, right=n-1, current=0
- 当current <= right时循环：
- 如果nums[current]==0，交换到left位置，left++, current++
- 如果nums[current]==2，交换到right位置，right--
- 如果是1，current++
这个算法的时间复杂度是O(n)，空间复杂度O(1)，完美满足题目要求。
3. 代码实现与细节
3.1 Python实现示例
def sortColors(nums): left, right = 0, len(nums) - 1 current = 0 while current <= right: if nums[current] == 0: nums[left], nums[current] = nums[current], nums[left] left += 1 current += 1 elif nums[current] == 2: nums[right], nums[current] = nums[current], nums[right] right -= 1 else: current += 13.2 关键点说明
- 边界条件处理：当current超过right时终止循环
- 交换逻辑：0往左交换后current可以前进，因为左边已经处理过；2往右交换后current不能前进，因为交换过来的元素还未检查
- 1的处理：直接跳过，让中间自然形成1的区域
4. 算法正确性证明
我们可以用循环不变式来证明这个算法的正确性：
初始化：三个区域都为空，满足条件 保持：
- 每次遇到0，交换到left位置，保证left左侧全是0
- 每次遇到2，交换到right位置，保证right右侧全是2
- 遇到1不做处理，自然留在中间 终止：current > right时，所有元素都已处理
5. 变种与扩展
5.1 四色排序问题
如果颜色增加到四种，同样可以使用类似的多指针方法解决。需要维护三个分界点，将数组分为四个区域。
5.2 部分有序情况
如果数组已经部分有序，算法依然有效，但可以考虑优化提前终止的条件。
5.3 实际应用场景
这种算法在操作系统内存管理、数据库索引维护等需要高效原地排序的场景都有应用价值。
6. 常见错误与调试技巧
6.1 典型错误模式
- 交换2之后current也增加：会导致漏检交换过来的元素
- 边界条件错误：current应该与right比较而非数组长度
- 指针移动顺序错误：left和current的移动需要协调
6.2 调试建议
可以打印每次交换后的数组状态和指针位置，观察分区是否正确形成。对于小数组（如[2,0,1]）要特别注意边界情况。
7. 性能优化思考
虽然算法已经是理论最优，但在实际实现中还可以考虑：
- 使用位运算代替交换操作
- 对于大规模数据，可以考虑并行化处理
- 在特定硬件架构下优化内存访问模式
8. 面试技巧
遇到这类问题时，建议：
- 先明确问题约束条件
- 从暴力解法开始，逐步优化
- 画图说明指针移动过程
- 讨论时间/空间复杂度
- 考虑边界情况和测试用例
这道题很好地考察了候选人对指针操作和原地算法的掌握程度，是面试中的高频考点。理解其背后的荷兰国旗问题本质，有助于举一反三解决类似的数组分区问题。
