来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors/

描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

题解

又名荷兰国旗问题，使用三个指针。curr为当前考虑的元素，P0追踪0的最右边界，p2追踪2的最左边界。
在整个算法执行过程中 nums[idx < p0] = 0 nums[idx > p2] = 2

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         int p0 = 0, p2 = nums.length - 1, curr = 0;
  5.         int tmp;
  6.         while (curr <= p2) {
  7.             if (0 == nums[curr]) {
  8.                 tmp = nums[curr];
  9.                 nums[curr++] = nums[p0];
  10.                 nums[p0++] = tmp;
  11.             } else if (2 == nums[curr]) {
  12.                 tmp = nums[curr];
  13.                 nums[curr] = nums[p2];
  14.                 nums[p2--] = tmp;
  15.             } else {
  16.                 curr++;
  17.             }
  18.         }
  19.     }
  20. }

复杂度分析