1. 颜色分类

1.1 题目分析

1.2 解法

1.3 代码实现

2. 排序数组

2.1 题目解析

2.2 解法

2.3 代码实现

1. 颜色分类

75. 颜色分类 - 力扣（LeetCode）

给定一个包含红色、白色和蓝色、共 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.length
1 <= n <= 300
nums[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] == 1i++;}}}
}

代码实现（写法二：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. 排序数组

912. 排序数组 - 力扣（LeetCode）

给你一个整数数组 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, left] 与 [right, 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+1
key：数值（从 [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]     > keywhile (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);}
}

复杂度分析