题目

题目来源：力扣（LeetCode）

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

示例 3：

输入：nums = [0]
输出：[0]

示例 4：

输入：nums = [1]
输出：[1]

思路分析

我们借助快速排序的思想，对数组进行一个分区操作。分别定义一个循环不变量 i 及两个边界量 zero 和 two，其中：

  • 变量 i 是循环变量，一般设置为开区间，表示 i 之前的元素都是遍历过的；
  • 变量 zero 是前两个子区间的分界点，一个是闭区间，另一个就必须是开区间；
  • 变量 two 是另一个分界线，设计成闭区间；
  • len 是数组的长度；

则有：

  • 子区间 [0, zero) 存储所有的 0；
  • 子区间 [zero, i) 存储所有的 1；
  • 子区间 [two, len - 1) 存储所有的2；

我们遍历数组，如果当前遍历的数字为 0，则将当前的数字与 zero 所在的元素进行交换；如果数字为 2 ，则将当前的数字 2 与 two 所在的元素进行交换。最终遍历完数组后，数组已经排序好。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {void} Do not return anything, modify nums in-place instead.
  4.  */
  5. var sortColors = function(nums) {
  7.   const len = nums.length;
  8.   if (len < 2) return
  10.   const swap = (arr, i, j) => [arr[i], arr[j]] = [arr[j], arr[i]];
  12.   // 子区间 [0, zero) 存储所有的 0
  13.   // 子区间 [zero, i) 存储所有的 1
  14.   // 子区间 [two, len - 1] 存储所有的2
  16.   // 循环终止条件是 i == two，那么循环可以继续的条件是 i < two
  17.   // 为了保证初始化的时候 [0, zero) 为空，设置 zero = 0
  18.   // 所以下面遍历到数字是 0 的时候，元素先交换，然后循环变量再加
  19.   let zero = 0;
  21.   // 为了保证初始化的时候 [two, len - 1] 为空，设置 two = len
  22.   // 所以下面遍历到的元素是 2 的时候，边界量two先减，然后元素再交换
  23.   let two = len ;
  24.   let i = 0;
  26.   while(i < two) {
  27.     switch(nums[i]) {
  28.       case 0: // 元素先交换，然后循环变量再加
  29.         // swap(nums, zero++, i)
  30.         // i++
  31.         swap(nums, i, zero)
  32.         zero++
  33.         i++
  34.         break;
  35.       case 1:
  36.         i++
  37.         break;
  38.       case 2: // 边界量two 先减，然后再交换元素
  39.         // swap(nums, two--, i)
  40.         two--
  41.         swap(nums, i, two)
  42.         break;
  43.       default:
  44.         break;
  45.     }
  46.   }
  47. };