登录
O(n) 插入排序，简洁写法（Python/Java/C++/C/Go/JS/Rust）
2025年5月17日 08:57
不让用 $\texttt{sort}$ 吗？有意思……
技巧：O(1) 插入元素
假设现在有一个有序数组 $a=[0,0,1,1,2,2]$。在 $a$ 中插入一个 $0$，同时保证 $a$ 是有序的，你会怎么做？
最暴力的想法是，把 $0$ 插在数组的最左边，原来的元素全体右移一位，得到 $[0,0,0,1,1,2,2]$。这样做是 $\mathcal{O}(n)$ 的。
实际上，我们可以「狸猫换太子」：不是插入元素，而是修改元素！
对比一下插入前后：
- 插入前 $[0,0,1,1,2,2]$。
- 插入后 $[0,0,0,1,1,2,2]$。
竖着看，其实只有 $3$ 个位置变了：
- 原来的 $a[2]$ 变成 $0$。
- 原来的 $a[4]$ 变成 $1$。
- 末尾新增一个 $2$，相当于 $a[6]=2$。
怎么知道要修改的位置（下标）？
- 维护 $0$ 的个数，即为改成 $0$ 的位置，记作 $p_0$。上例中 $p_0=2$。把 $a[p_0]$ 改成 $0$。
- 维护 $0$ 和 $1$ 的个数，即为改成 $1$ 的位置，记作 $p_1$。上例中 $p_1=4$。把 $a[p_1]$ 改成 $1$。
- 末尾新增的位置记作 $i$，把 $a[i]$ 改成 $2$。
细节
如果 $a$ 中没有 $2$ 呢？上面第三步就错了。
比如现在 $a=[1]$，插入一个 $0$，变成 $[0,1]$。
如果按照上面三步走，最后把 $a[1]$ 改成 $2$，得到的是 $[0,2]$，这就错了。
要写很多 $\texttt{if-else}$，特判这些特殊情况吗？
不需要，我们可以倒过来算：先把 $a[1]$ 改成 $2$，再把 $a[1]$ 改成 $1$（覆盖），最后 $a[0]$ 改成 $0$，得到 $[0,1]$。这种「覆盖」等价于「没有 $2$ 的时候不改成 $2$」。
如果插入的是 $1$ 呢？
跳过「把 $a[p_0]$ 改成 $0$」这一步。
如果插入的是 $2$ 呢？
只需要把 $a[i]$ 改成 $2$ 即可。
本题思路
对 $\textit{nums}$ 执行插入排序，也就是对 $i=0,1,2,\ldots,n-1$ 依次执行如下过程：
- 现在前缀 $\textit{nums}[0]$ 到 $\textit{nums}[i-1]$ 是有序的，我们把 $\textit{nums}[i]$ 插入到这个有序前缀中，从而把前缀 $\textit{nums}[0]$ 到 $\textit{nums}[i]$ 变成有序的。
- 算法执行完后，$\textit{nums}$ 就是一个有序数组了。
class Solution:
def sortColors(self, nums: List[int]) -> None:
p0 = p1 = 0
for i, x in enumerate(nums):
nums[i] = 2
if x <= 1:
nums[p1] = 1
p1 += 1
if x == 0:
nums[p0] = 0
p0 += 1
class Solution {
public void sortColors(int[] nums) {
int p0 = 0;
int p1 = 0;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
nums[i] = 2;
if (x <= 1) {
nums[p1++] = 1;
}
if (x == 0) {
nums[p0++] = 0;
}
}
}
}
class Solution {
public:
void sortColors(vector<int>& nums) {
int p0 = 0, p1 = 0;
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
nums[i] = 2;
if (x <= 1) {
nums[p1++] = 1;
}
if (x == 0) {
nums[p0++] = 0;
}
}
}
};
void sortColors(int* nums, int numsSize) {
int p0 = 0, p1 = 0;
for (int i = 0; i < numsSize; i++) {
int x = nums[i];
nums[i] = 2;
if (x <= 1) {
nums[p1++] = 1;
}
if (x == 0) {
nums[p0++] = 0;
}
}
}
func sortColors(nums []int) {
p0, p1 := 0, 0
for i, x := range nums {
nums[i] = 2
if x <= 1 {
nums[p1] = 1
p1++
}
if x == 0 {
nums[p0] = 0
p0++
}
}
}
var sortColors = function(nums) {
let p0 = 0, p1 = 0;
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
nums[i] = 2;
if (x <= 1) {
nums[p1++] = 1;
}
if (x === 0) {
nums[p0++] = 0;
}
}
};
impl Solution {
pub fn sort_colors(nums: &mut Vec<i32>) {
let mut p0 = 0;
let mut p1 = 0;
for i in 0..nums.len() {
let x = nums[i];
nums[i] = 2;
if x <= 1 {
nums[p1] = 1;
p1 += 1;
}
if x == 0 {
nums[p0] = 0;
p0 += 1;
}
}
}
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
- 空间复杂度：$\mathcal{O}(1)$。
分类题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
