04 创意排序：荷兰国旗问题与桶排序思想

创意排序：荷兰国旗问题与桶排序思想

摘要

本文介绍两道”不像排序题的排序题”：Sort Colors（颜色分类）和 First Missing Positive（缺失的第一个正数）。前者要求对只有三种值（0、1、2）的数组原地排序，是经典的荷兰国旗问题（Dutch National Flag Problem），核心是三路分区思想；后者看似查找题，实际上需要用一种巧妙的原地桶排序思想，在 $O(n)$ 时间和 $O(1)$ 空间内解决。这两道题都是考察候选人能否突破”套模板”思维的好题目。

---

第 1 章 荷兰国旗问题：Sort Colors

1.1 题目

LeetCode 75 - Sort Colors（中等）

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

我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。

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

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

进阶：你能想出一个仅使用常数空间的一趟扫描算法吗？

1.2 简单但不优雅的解法

解法一：计数排序

因为只有 0、1、2 三种值，先统计每种值的个数，然后按顺序填充：

public void sortColors(int[] nums) {
    int count0 = 0, count1 = 0, count2 = 0;
    for (int x : nums) {
        if (x == 0) count0++;
        else if (x == 1) count1++;
        else count2++;
    }
    int i = 0;
    while (count0-- > 0) nums[i++] = 0;
    while (count1-- > 0) nums[i++] = 1;
    while (count2-- > 0) nums[i++] = 2;
}

时间 $O(n)$，空间 $O(1)$，但需要两次遍历（一次统计，一次填充）。题目进阶要求一趟扫描。

解法二：两次冒泡/两次双指针

第一次遍历把所有 0 换到最前面，第二次遍历把所有 2 换到最后面。也是两次遍历。

上面两种解法都能通过，但都需要两次扫描。题目进阶要求一趟扫描，这就是荷兰国旗问题的精髓所在。

1.3 荷兰国旗算法：三路分区一趟扫描

问题的来源

这道题由 Edsger Dijkstra（算法领域的传奇人物，以发明 Dijkstra 最短路径算法闻名）提出，因为荷兰国旗的三色横条与这道题完全对应（红、白、蓝）而得名。

核心思想：维护三个区域

将数组想象成三个区域，用三个指针 low、mid、high 来维护：

[0, low)    → 已处理的 0 区域（红色区）
[low, mid)  → 已处理的 1 区域（白色区）
[mid, high] → 待处理区域（unknown）
(high, n-1] → 已处理的 2 区域（蓝色区）

初始状态：low = 0，mid = 0，high = n - 1（所有元素都在待处理区域）

扫描指针 mid 从左向右移动，根据 nums[mid] 的值决定操作：

• nums[mid] == 0：应该放到红色区。将 nums[mid] 和 nums[low] 交换，low++，mid++
• nums[mid] == 1：已经在白色区，位置正确，mid++
• nums[mid] == 2：应该放到蓝色区。将 nums[mid] 和 nums[high] 交换，high--（mid 不前进！）

生产避坑：为什么遇到 2 时 mid 不前进

当 nums[mid] == 2 时，将它和 nums[high] 交换后，nums[high] 的值（原 nums[mid]，即 2）已经处理好，所以 high--。 但交换来的 nums[mid]（原 nums[high]）是未知的，可能是 0、1 或 2，还需要在下一次循环中处理，所以 mid 不移动。 相比之下，遇到 0 时 mid++ 是因为：交换来的 nums[mid]（原 nums[low]）一定是 1（因为 [low, mid) 区间全是 1），不需要再处理。

public void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;
 
    while (mid <= high) {
        if (nums[mid] == 0) {
            // 0 应该在最左边，和 low 交换
            swap(nums, low, mid);
            low++;
            mid++;  // [low, mid) 全是 1，交换来的一定是 1，可以直接前进
        } else if (nums[mid] == 1) {
            mid++;  // 1 在中间，位置正确
        } else {  // nums[mid] == 2
            // 2 应该在最右边，和 high 交换
            swap(nums, mid, high);
            high--;
            // mid 不前进，因为换来的值未知，需要在下次循环处理
        }
    }
}
 
private void swap(int[] nums, int i, int j) {
    int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
}

时间 $O(n)$，空间 $O(1)$，且只需一趟扫描。

1.4 完整走一遍示例

以 [2, 0, 2, 1, 1, 0] 为例，n=6：

步骤	low	mid	high	数组状态	操作
初始	0	0	5	[2,0,2,1,1,0]	nums[mid]=2，交换(0,5)，high--
1	0	0	4	[0,0,2,1,1,2]	nums[mid]=0，交换(0,0)，low++,mid++
2	1	1	4	[0,0,2,1,1,2]	nums[mid]=0，交换(1,1)，low++,mid++
3	2	2	4	[0,0,2,1,1,2]	nums[mid]=2，交换(2,4)，high--
4	2	2	3	[0,0,1,1,2,2]	nums[mid]=1，mid++
5	2	3	3	[0,0,1,1,2,2]	nums[mid]=1，mid++
结束	2	4	3	[0,0,1,1,2,2]	mid>high，退出

最终：[0, 0, 1, 1, 2, 2] ✅

1.5 荷兰国旗与快速排序的关系

荷兰国旗算法本质上是快速排序的三路分区（3-Way Partition）。

普通快速排序的分区只分两类（小于 pivot 和大于等于 pivot），遇到有大量重复元素的数组时，效率很低——所有等于 pivot 的元素仍然需要在后续的递归中处理。

三路分区将数组分成三类：小于 pivot、等于 pivot、大于 pivot。等于 pivot 的元素在一次分区后就完全处于正确位置，不再参与后续递归。这使得三路快速排序在”有大量重复元素”的场景下，时间复杂度从 $O(n^2)$（全相同元素时）提升到 $O(n)$。

Java 的 Arrays.sort 使用的双轴快速排序，本质上也包含了类似的三路分区思想。

---

第 2 章 First Missing Positive：原地桶排序

2.1 题目

LeetCode 41 - First Missing Positive（困难）

给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 $O(n)$，并且只使用常数级别额外空间的解决方案。

输入: nums = [1,2,0]
输出: 3

输入: nums = [3,4,-2,1]
输出: 2

输入: nums = [7,8,9,11,12]
输出: 1

2.2 逐步推进：从暴力到最优

第一步：分析答案的范围

对于一个长度为 $n$ 的数组，缺失的最小正整数的范围是 $[1,n+1]$。

为什么？ 如果数组恰好包含了 $1,2,\dots ,n$ 这 $n$ 个正整数，那么缺失的最小正整数是 $n+1$。如果数组中某些位置被负数、0、或大于 $n$ 的数占据，那么 $[1,n]$ 中必然有某个数缺失，答案在 $[1,n]$ 中。

关键结论：答案一定在 $[1,n+1]$ 范围内，也就是说只有 $1$ 到 $n$ 这 $n$ 个正整数是”有效候选”，大于 $n$ 的数直接无关。

第二步：如果可以用额外空间

创建一个大小为 $n+1$ 的布尔数组 seen，遍历 nums，对 $[1,n]$ 范围内的值 $v$，标记 seen[v] = true。然后从 1 开始扫描 seen，找到第一个为 false 的位置，就是答案。

空间 $O(n)$，时间 $O(n)$。但题目要求 $O(1)$ 额外空间，不能用这种方法。

第三步：能不能把 nums 本身当作 seen 数组用？

这是解题的核心突破！

我们希望把 $nums$ 变成一个”位置映射”：如果正整数 $v$ 出现在数组中，就把它放到下标 $v-1$ 的位置（下标从 0 开始，所以值 $v$ 对应下标 $v-1$）。这样，最后扫描一遍数组，找到第一个不满足 nums[i] == i+1 的位置 $i$，答案就是 $i+1$。

这本质上是一个桶排序：把数组元素分配到它应该在的”桶”（位置）里。

2.3 原地桶排序的实现

交换操作：对 nums[i]，如果 1 <= nums[i] <= n 且 nums[i] != i+1（还没到正确位置）且 nums[nums[i]-1] != nums[i]（目标位置上的值不同，即不会死循环），就把 nums[i] 换到它该去的地方 nums[nums[i]-1]，然后继续处理现在 nums[i] 的值（因为换来了新值）。

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
 
    // 第一步：原地排序，把 nums[i] 放到 nums[nums[i]-1] 的位置
    for (int i = 0; i < n; i++) {
        // 循环交换：只要当前位置的值不在正确位置，就一直换
        while (nums[i] > 0               // 值是正数
            && nums[i] <= n              // 值在有效范围内
            && nums[nums[i] - 1] != nums[i])  // 目标位置的值不等于 nums[i]（避免死循环）
        {
            int target = nums[i] - 1;   // 该值应该放在的下标
            int tmp = nums[target];
            nums[target] = nums[i];
            nums[i] = tmp;
            // 注意：i 不前进，继续处理换来的新值
        }
    }
 
    // 第二步：扫描数组，找第一个不满足 nums[i] == i+1 的位置
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
 
    // 所有位置都满足，答案是 n+1
    return n + 1;
}

关键条件解析：

1. nums[i] > 0：负数和 0 不是有效的正整数，不需要放到特定位置
2. nums[i] <= n：大于 $n$ 的值不在有效范围内，放到哪个位置都不影响答案
3. nums[nums[i] - 1] != nums[i]：如果目标位置已经放着和 nums[i] 相同的值（即重复元素），就不需要再换了，否则会死循环（如 [1, 1]，下标 0 和 1 都是 1，不断交换）

2.4 详细走一遍示例

以 [3, 4, -2, 1] 为例，n=4：

第一步：原地排序

i=0，nums[0]=3：

• 条件满足（3>0，3<=4，nums[2]=−2 ≠ 3），交换 nums[0] 和 nums[2]
• 数组：[-2, 4, 3, 1]，nums[0]=-2
• 条件不满足（-2 <= 0），停止
• 前进 i=1

i=1，nums[1]=4：

• 条件满足（4>0，4<=4，nums[3]=1 ≠ 4），交换 nums[1] 和 nums[3]
• 数组：[-2, 1, 3, 4]，nums[1]=1
• 条件满足（1>0，1<=4，nums[0]=-2 ≠ 1），交换 nums[1] 和 nums[0]
• 数组：[1, -2, 3, 4]，nums[1]=-2
• 条件不满足（-2 <= 0），停止
• 前进 i=2

i=2，nums[2]=3：

• 条件满足（3>0，3<=4，nums[2]=3 == 3），条件3不满足，停止
• 前进 i=3

i=3，nums[3]=4：

• 条件满足（4>0，4<=4，nums[3]=4 == 4），条件3不满足，停止

最终数组：[1, -2, 3, 4]

第二步：扫描

• i=0：nums[0]=1 == 1，✅
• i=1：nums[1]=-2 ≠ 2，返回 2

结果：2 ✅

2.5 为什么这是”桶排序”

桶排序的思想：将 $n$ 个元素分配到 $k$ 个桶里，每个桶对应一个值域区间。在本题中：

• 共 $n$ 个”桶”（数组的 $n$ 个位置）
• 第 $i$ 个桶（下标 $i-1$）用来存放值等于 $i$ 的元素
• 有效元素（$[1,n]$ 范围内的正整数）都有且仅有一个属于它们的桶

不同之处在于：标准桶排序需要额外空间存放桶，而这道题用原数组本身充当桶，是一种”原地桶排序”（In-Place Bucket Sort）。

核心概念：鸽巢原理在本题中的体现

如果数组中存在 $k$ 个不同的有效正整数（$[1,n]$ 范围内），那么这 $k$ 个数最多能填满 $k$ 个”桶”，剩下的 $n-k$ 个桶必然是空的。最小的空桶对应的下标 + 1 就是答案。 鸽巢原理保证了答案一定在 $[1,n+1]$ 范围内，这是本题算法的基础假设。

2.6 时间复杂度的细节分析

粗看之下，代码有两层循环（外层 for，内层 while），似乎是 $O(n^2)$。但实际上是均摊 $O(n)$。

分析：每次 while 循环中的交换操作，会把一个元素放到它最终正确的位置上。一旦某个元素到达正确位置，它就永远不会再被交换（因为条件 nums[nums[i]-1] != nums[i] 会让它停留）。总共最多有 $n$ 个元素，每个元素最多被交换 1 次，所以所有 while 循环的总交换次数是 $O(n)$，均摊到每个 i 是 $O(1)$，总时间 $O(n)$。

---

第 3 章 两道题的共同思想

3.1 “限制条件就是优化机会”

Sort Colors 和 First Missing Positive 都有一个共同点：题目给出了元素值的额外约束（只有 0/1/2 三种值；答案范围在 $[1,n+1]$），而正是这些约束让我们能做出比通用排序更优的解法。

• Sort Colors：值域只有 3 种，可以用三路分区一趟完成
• First Missing Positive：答案范围有限，可以用原数组充当哈希表/桶

面试中遇到类似问题，要主动思考：题目给出了哪些额外约束？这些约束能否用来降低时间/空间复杂度？

3.2 原地操作的思维模式

两道题都要求 $O(1)$ 额外空间，核心技巧都是把原数组本身当作辅助数据结构使用：

• Sort Colors：把数组分成三个”区域”，用三个指针维护
• First Missing Positive：把数组当作”桶”，用下标存放值

这种”用原数组当辅助存储”的思维，在很多需要 $O(1)$ 空间的题目中都会用到，值得专门记忆。

---

小结

本文讲解了两道”创意排序”题目：

1. Sort Colors（荷兰国旗问题）：用三路分区（DNF 算法）一趟扫描完成三值数组的原地排序。三个指针 low、mid、high 维护三个区域，关键是遇到 2 时 mid 不前进。时间 $O(n)$，空间 $O(1)$。

2. First Missing Positive（原地桶排序）：利用”答案在 $[1,n+1]$ 范围”的约束，将原数组当桶使用，通过循环交换把每个有效元素放到正确位置，然后扫描找第一个空桶。均摊时间 $O(n)$，空间 $O(1)$。

这两道题的共同教训是：读清楚题目约束，约束往往就是算法的突破口。

---

上一篇：03 链表排序双题精讲：插入排序与归并排序的链表实现 下一篇：05 二分查找核心模板：从基础到左右边界锁定