Pengjielee's blog

题目

给定一个包含红色、白色和蓝色，一共 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]

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

进阶：

你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sort-colors 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

1、单指针

在第一次遍历中，我们将数组中所有的 0 交换到数组的头部。
在第二次遍历中，我们将数组中所有的 1 交换到头部的 0 之后。
此时，所有的 2 都出现在数组的尾部，这样我们就完成了排序。

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var swap = function (arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
};
var sortColors = function (nums) {
  let len = nums.length;
  // 使用一个指针 phead 表示「头部」的范围，
  // 初始值为 0，表示还没有数处于「头部」
  let phead = 0;
  for (let i = 0; i < len; i++) {
    if (nums[i] === 0) {
      swap(nums, i, phead);
      phead++;
    }
  }
  for (let i = 0; i < len; i++) {
    if (nums[i] === 1) {
      swap(nums, i, phead);
      phead++;
    }
  }
};

2、双指针

使用两个指针分别用来交换 0 和 1。
用指针 p0 来交换 0，p1 来交换 1，初始值都为 0。

var swap = function (arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
};
var sortColors = function (nums) {
  let len = nums.length;
  let p0 = 0,
    p1 = 0;

  for (let i = 0; i < len; i++) {debugger;
    if (nums[i] === 1) {
      //交换p1
      console.log('swap1_before', nums);
      swap(nums, i, p1);
      console.log('swap1_after', nums);
      //p1后移
      p1++;
    } else if (nums[i] === 0) {
      // 交换p0
      console.log('swap0_before', nums);
      swap(nums, i, p0);
      console.log('swap0_after', nums);
      // 没看懂？(我们有可能把1交换到最后面)
      if (p0 < p1) {
        swap(nums, i, p1);
      }
      p0++;
      p1++;
    }
  }
};

3、快速排序

借助快速排序partition过程的一趟扫描法。

实现1：

var swap = function (nums, i, j) {
  const temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
};
/* 
 * 分区定义：
 * 1. 区间[0, p0)的元素都 === 0
 * 2. 区间[p0, i) 的元素都 === 1
 * 3. 区间(p2, len - 1]的元素都 === 2
 */ 
var sortColors = function (nums) {
  let len = nums.length;
  if(len < 2) {
    return;
  }

  // 循环不变量的定义
  // all in [0, p0) == 0
  // all in [p0, i) == 1
  // all in (p2, len -1) == 2

  // 三个区间确保初始化时都为空区间
  let p0 = 0;
  let i = 0;
  let p2 = len - 1;

  while(i <= p2){
    if(nums[i] === 0){
      swap(nums, i, p0);
      p0++;
      i++;
    } else if(nums[i] === 1){
      i++;
    } else {
      // nums[i] == 2
      swap(nums, i, p2);
      p2--;
    }
  }
}

实现2：

var swap = function (nums, i, j) {
  const temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
};
var sortColors = function (nums) {
  let len = nums.length;
  if(len < 2) {
    return;
  }

  // 循环不变量的定义
  // all in [0, p0] == 0
  // all in (p0, i) == 1
  // all in [p2, len -1) == 2

  // 三个区间确保初始化时都为空区间
  let p0 = -1;
  let i = 0;
  let p2 = len;

  while(i < p2){ // i严格小于p2
    if(nums[i] === 0){
      p0++;
      swap(nums, i, p0);
      i++;
    } else if(nums[i] === 1){
      i++;
    } else {
      // nums[i] == 2
      p2--;
      swap(nums, i, p2);
    }
  }
}