如何在O(n)时间O(1)空间下重排数组：前置0、中间2、后置1

你的思路方向偏了，而且代码里还有个明显的swap函数错误，导致交换逻辑根本没生效。先来拆解下问题：

你的代码存在的问题 #

1. Swap函数逻辑错误：
   你的swap函数里，input[j] = input[i];这一步完全没意义，赋值顺序彻底搞反了。正确的swap应该是先把input[i]暂存，再把input[j]的值赋给input[i]，最后把暂存的值赋给input[j]：

   function swap(input, i, j) {
       let temp = input[i];
       input[i] = input[j];
       input[j] = temp;
   }
   

   原来的代码相当于没做任何交换，因为最后input[i]还是原来的input[i]值。

2. 算法逻辑不完整：
   你当前的逻辑只尝试把0移到左边，但完全没处理2和1的位置。原问题要求数组分成三个明确区域：[0区 | 2区 | 1区]，你的代码只处理了0区，剩下的2和1自然是乱序的，得不到正确结果。

正确的解法：三指针法（类似荷兰国旗问题） #

我们可以用三个指针来划分三个区域，实现一次遍历完成排序：

• low：指向下一个0应该放置的位置，初始为0
• high：指向下一个1应该放置的位置，初始为数组末尾
• mid：遍历指针，从0开始，直到超过high

遍历规则 #

• 当arr[mid] === 0：把它和arr[low]交换，然后low++、mid++（交换过来的元素要么是0要么是2，已经符合区域要求）
• 当arr[mid] === 2：不需要交换，直接mid++（2本来就在中间区域）
• 当arr[mid] === 1：把它和arr[high]交换，然后high--（交换过来的元素可能是0或2，需要重新检查，所以mid不递增）

实现代码 #

let arr = [0, 1, 0, 2, 1];

function swap(input, i, j) {
    let temp = input[i];
    input[i] = input[j];
    input[j] = temp;
}

function moveZeroOneAndTwo(input) {
    let low = 0;
    let high = input.length - 1;
    let mid = 0;

    while (mid <= high) {
        if (input[mid] === 0) {
            swap(input, mid, low);
            low++;
            mid++;
        } else if (input[mid] === 2) {
            mid++;
        } else if (input[mid] === 1) {
            swap(input, mid, high);
            high--;
        }
    }
    return input;
}

console.log(moveZeroOneAndTwo(arr)); // 输出 [0, 0, 2, 1, 1]

逻辑说明 #

• 整个过程只遍历数组一次，时间复杂度O(n)，空间复杂度O(1)，完全符合你的要求。
• 每次处理mid位置的元素，把0归位到左区，把1归位到右区，2留在中间区，确保每个区域的元素都符合要求。

内容的提问来源于stack exchange，提问作者user5711656