目录
1. 颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1] 输出：[0,1,2]
提示：
n == nums.length1 <= n <= 300nums[i]为0、1或2
1.1 题目分析
题目本质
只有三种取值 0/1/2，要求原地按 0→1→2 排序。可抽象为：一次扫描把元素分到三个“桶/分区”。
常规解法
计数法：统计 0/1/2 的数量，再回写。时间 O(n)，空间 O(1)，两趟且缺少“原地一次遍历”的训练价值。
直接排序：不允许用库排序，且会是 O(n log n)。
问题分析
若用交换排序或冒泡都会超过 O(n)。想在 O(n) 一趟里完成，必须让每次访问都把当前元素“扔到正确区域”，并保持区间边界稳定（循环不变式），这就是“荷兰国旗”思想。
思路转折
维护三指针把数组动态分成 4 段（不变式）：
0..left-1 全是 0
left..i-1 全是 1
i..right 还未处理
right+1..n-1 全是 2
指针 i 扫描未处理区：遇到 0 扔到左边，遇到 2 扔到右边，遇到 1 跳过。直到 i > right 结束
1.2 解法
算法思想
三指针分区（Dutch National Flag）：
0 ↦ 与 left 交换，left++，i++
1 ↦ i++
2 ↦ 与 right 交换，right--，i 不动（因为换来的元素未检查）
i）初始化：left=0, right=n-1, i=0。
ii）循环 i <= right：
nums[i]==0：交换到左区，扩左界并前进 i；
nums[i]==2：交换到右区，收缩右界，但不移动 i；
nums[i]==1：仅 i++。
iii）循环结束时四段不变式成立，数组即为 0…0 1…1 2…2。
小解释：为什么 0 情况可以 i++，而 2 情况不能
0 情况：left 永远 ≤ i。交换把 0 放到最左侧，nums[i] 会变成原来 left 位置的元素（已处理区的 1），可以直接前进。
2 情况：right 在 i 右边，交换把一个未知元素换到 i，必须继续判断它，所以 不能 i++。
1.3 代码实现
代码实现（写法一：直观边界 i <= right）
class Solution {
private void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
public void sortColors(int[] nums) {
int n = nums.length;
int left = 0, right = n - 1; // 左右“投放位”
for (int i = 0; i <= right; ) {
if (nums[i] == 0) {
swap(nums, left, i);
left++; i++; // 换来的一定在[0,left)或[1区]，无需再查
} else if (nums[i] == 2) {
swap(nums, right, i);
right--; // 换来的未知，i不动，继续检查当前位置
} else { // nums[i] == 1
i++;
}
}
}
}
代码实现（写法二：i < right，left=-1,right=n）
class Solution {
private void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
public void sortColors(int[] nums) {
int left = -1, right = nums.length, i = 0;
while (i < right) {
if (nums[i] == 0) swap(nums, ++left, i++); // 左区扩张
else if (nums[i] == 1) i++; // 中区自然累积
else swap(nums, --right, i); // 右区收缩，i不动
}
}
}
复杂度分析
时间复杂度：O(n)（每个元素最多被交换/访问常数次）
空间复杂度：O(1)（原地修改，仅常数指针）
2. 排序数组
给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5] 解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。
示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5] 解释：请注意，nums 的值不一定唯一。
提示：
1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104
2.1 题目解析
题目本质
把整型数组升序排列；目标是平均 O(n log n)，并尽量原地。数据范围允许重复与负数。
常规解法
归并排序：时间稳定 O(n log n)，但需要 O(n) 额外空间。
快速排序：平均 O(n log n)、原地；若选取随机基准 + 三路划分，对大量重复值更友好。
问题分析
经典双路快排在重复元素多时会退化，划分不均，递归层次加深。
三路划分把数组维护为三段：< key、= key、> key，一次扫描就把等于段“压缩”出来，递归只落在两侧，更稳定。
思路转折（不变式引导）
在子数组 [l, r] 内维护指针 left/i/right，保持不变式：
[l, left] < key
[left+1, i-1] = key
[i, rgiht-1] 未处理
[right, r] > key
循环扫描未处理区：
a[i] < key → 交换到左边 swap(++lt, i++)
a[i] == key→ i++
a[i] > key→ 交换到右边 swap(--gt, i)（i 不动，因新换来的还未判断）
当 i == right，未处理区为空，递归排序 < key的 [l,left] 与 > key的 [right, r] 两端。
2.2 解法
算法思想
随机基准：降低恶劣输入导致的退化概率；
三路划分：一次扫描把等于段“吃掉”，递归只落两端；
原地交换：常数额外空间。
i）递归基：if (l >= r) return;
ii）选择基准：key= nums[new Random().nextInt(r-l+1) + l]
iii）运行三路划分循环，维持不变式。
iiii）递归处理 [l, lt] 与 [gt, r]。
iiiii）结束
容易踩坑点：
比较方向：a[i] < key 放左边；a[i] > key 放右边。
递归基：if (l >= r) return;
i 的移动：放左 i++；放右 不要 i++；等于 i++。
边界名分清：l/r（递归区间）
l / r：当前递归处理的子数组边界（闭区间）。
left/right/i：划分指针，lt = l-1, i = l, gt = r+1key：数值（从 [l, r] 随机取出的元素的值）；不是索引。 复杂度分析
2.3 代码实现
import java.util.concurrent.ThreadLocalRandom;
class Solution {
private void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
public int[] sortArray(int[] nums) {
qsort(nums, 0, nums.length - 1);
return nums;
}
private void qsort(int[] nums, int l, int r) {
if (l >= r) return; // 递归基
// 随机基准，降低退化概率
int key = nums[new Random().nextInt(r-l+1) + l];
int left = l - 1, i = l, right = r + 1;
// 不变式：
// [l, left] < key
// [left+1, i-1] = key
// [i, right-1] 未处理
// [right, r] > key
while (i < right) {
if (nums[i] < key ) {
swap(nums, ++left, i++);
} else if (nums[i] > key ) {
swap(nums, --right, i); // i 不动：换来的还未检查
} else {
i++;
}
}
// 递归两端；等于 key 的中段 [left+1, right-1] 已就位
qsort(nums, l, left);
qsort(nums, right, r);
}
}
复杂度分析
时间复杂度：期望 O(n log n)；最差 O(n^2)（随机化可将概率降到极低）。
空间复杂度：原地划分 O(1) 额外空间，整体为递归栈 O(log n)（期望）