排序与查找专栏导览：从原理到 LeetCode 面试通关

专栏定位

本专栏面向有一定编程基础、正在备战技术面试的工程师。讨论范围严格限定于排序算法与查找算法两大主题，不涉及树、图、动态规划等其他领域。

目标：帮助读者真正理解排序与查找的底层原理，而非死记硬背套路。每道题的讲解遵循”是什么 → 为什么出现 → 不这样会怎样 → 如何落地 → 边界与反例”的推导链，力求通俗易懂而不失深度。

专栏目录

序号	文章标题	核心话题	覆盖 LeetCode 题目
01	排序算法原理全景：从 $O (n^{2})$ 到 $O (n lo g n)$ 的演进之路	排序算法分类、时空复杂度横向对比、稳定性分析、面试选型决策	概念篇，无具体题目
02	归并排序实战三连：有序数组与有序链表的合并艺术	归并分治框架、双指针归并、原地归并的陷阱、多路归并优先队列	Merge Sorted Array、Merge Two Sorted Lists、Merge k Sorted Lists
03	链表排序双题精讲：插入排序与归并排序的链表实现	链表插入排序的指针细节、链表归并排序（递归 + 迭代）、 $O (1)$ 空间约束	Insertion Sort List、Sort List
04	创意排序：荷兰国旗问题与桶排序思想	三路快排思想、DNF 算法、鸽巢原理、桶的下界证明	Sort Colors、First Missing Positive
05	二分查找核心模板：从基础到左右边界锁定	二分的四大模板、闭区间不变量、重复元素的左右边界	Search Insert Position、Search for a Range
06	二分查找的变体：旋转有序数组与有序矩阵	旋转数组有序性分析、二维矩阵的 Z 字形搜索	Search in Rotated Sorted Array、Search a 2D Matrix
07	快速选择与 TopK 问题：期望 $O (n)$ 的奇妙算法	快速排序分区、快速选择算法、最小堆 TopK、BFPRT 算法简介	Kth Largest Element in an Array、Top K Frequent Elements
08	排序在非排序题中的妙用：区间合并与会议室	按端点排序、贪心区间合并、差分数组	Merge Intervals、Meeting Rooms、Non-overlapping Intervals
09	计数排序与基数排序：线性时间排序的边界与代价	计数排序原理与限制、基数排序位权展开、桶排序的稳定性	Maximum Gap、H-Index
10	排序与查找综合通关：面试高频模式总结	模式识别、算法选型决策树、复杂度速查、常见错误盘点	综合复习篇

专栏阅读建议

第 01 篇必读：理解各排序算法的”性格特点”，后续题目的解法选型才有根基
排序篇（02-04、08-09）：重点理解每道题为何选用当前排序算法，而非强行套模板
查找篇（05-06）：二分查找的核心在于不变量维护，建议先在纸上推导边界条件再看代码
进阶篇（07）：快速选择是高频面试考点，理解其与快速排序的关系是关键
本专栏不覆盖：哈希表查找（不属于线性时间有序查找范畴）、树形结构的搜索、图算法

复杂度速查表

算法	最好	平均	最坏	空间	稳定
冒泡排序	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	✅
插入排序	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	✅
选择排序	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (1)$	❌
归并排序	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (n)$	✅
快速排序	$O (n lo g n)$	$O (n lo g n)$	$O (n^{2})$	$O (lo g n)$	❌
堆排序	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (1)$	❌
计数排序	$O (n + k)$	$O (n + k)$	$O (n + k)$	$O (k)$	✅
基数排序	$O (nk)$	$O (nk)$	$O (nk)$	$O (n + k)$	✅
桶排序	$O (n + k)$	$O (n + k)$	$O (n^{2})$	$O (n + k)$	✅
二分查找	$O (1)$	$O (lo g n)$	$O (lo g n)$	$O (1)$	—