排序和查找算法是所有写代码的人绕不开的两座山。从大学期末考到社招技术面从给Excel里的IP地址排个序到在上亿条日志里定位一条记录背后翻来覆去就是这么几个经典套路。我从2013年开始正经写项目到现在手写过冒泡排序、快速排序、二分查找也在生产环境里踩过sort函数用错导致整张报表数据错乱的坑。这篇东西不是算法导论的压缩版而是基于这些年在真实项目里摸爬滚打出来的一份梳理把最常见的排序和查找算法讲透附上可以直接抄的代码和排查经验。这篇文章适合谁正在准备面试的应届生、平时写业务代码但想补底层基础的后端和嵌入式工程师以及单纯想搞明白“排序”和“查找”背后到底在做什么的爱好者。看完你至少能回答这几个问题为什么快排那么快、二分查找为什么老写错边界、哈希表和二叉树到底该怎么选。1. 排序和查找为什么值得花时间搞懂1.1 它们在程序里的真实位置排序和查找是所有数据处理流程的底层依赖。去电商网站按价格筛选背后是数据库的ORDER BY在跑在日志文件里找一个关键字好的工具会用二分思想做索引Excel里对一列IP自定义排序本质就是写了个比较函数。可以这么说只要一个程序在跟数据打交道它就躲不开排序和查找。拿我一个实际项目举例。之前做一个日志解析工具每天要处理几十万行日志需求是从里面快速定位某条消息。第一版图省事直接顺序查找每条日志遍历一遍整个文件。当时的数据量还不算大但每次查询都要扫全量慢到喝杯咖啡回来结果还没出。后来我换成哈希索引把消息的若干关键字段映射到一个哈希表里查询时间从O(n)直接降到O(1)整个工具用起来完全是两个东西。这种性能差距不是靠加服务器能解决的纯粹是算法选型的差距。很多人觉得“业务开发用不到算法”但实际情况是你写的每一行代码都在隐式地做算法选型。你选择用std::map还是std::unordered_map就是选了红黑树还是哈希表你决定在内存里排序还是丢给数据库就是选了快排还是外部归并。不懂底层就只能靠猜。1.2 选型之前必须搞清楚的几个概念在展开聊具体算法之前有几个基础概念必须掰扯清楚。不懂这几个词后面的代码和复杂度分析根本没法看。时间复杂度算法运行时间随数据规模增长的趋势用大O表示法描述。比如O(n)代表线性增长O(n²)代表平方级增长O(log n)代表对数级增长。它衡量的是增长趋势不是具体的秒数。空间复杂度算法执行过程中额外占用的内存大小。原地排序算法只需要常数级别的额外空间而非原地算法比如归并需要O(n)的辅助数组。稳定性排序算法是否保持相等元素的原始相对顺序。稳定排序如冒泡、插入、归并在需要二次排序时非常关键。原地排序指排序过程中只需要常量级别的额外空间不需要复制整个数组。内存受限的环境里这可能是比时间复杂度更重要的指标。严格弱序自定义比较器必须遵守的规则。简单说就是比较函数必须像号一样满足反对称ab和ba不能同时成立和传递性。这个规则在C的std::sort里是硬性要求违反它会导致未定义行为。注意不是所有场景都需要最快的算法。数据量只有几十条时冒泡排序这样简单直白的实现出bug的概率远低于复杂的快排变形数据量中等时插入排序甚至可能比快排更快因为它的常数因子小。选算法从来不是选“最牛”的而是选“最匹配”的。2. 排序算法全景拆解从冒泡到快排2.1 基础排序三兄弟的适用边界冒泡排序、插入排序、选择排序这三种都是教科书级别的O(n²)排序算法也是无数人算法生涯的第一课。但它们的实战价值经常被低估。冒泡排序的核心思想是每一轮从头到尾比较相邻元素顺序不对就交换像气泡一样把当前最大或最小的元素逐步“冒”到数组末尾。C代码长这样void bubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { std::swap(arr[j], arr[j 1]); swapped true; } } // 如果一整轮都没发生交换说明数组已经有序提前退出 if (!swapped) break; } }这里有一个很多人忽视的优化点加一个swapped标志位如果某一轮遍历下来都没发生过交换说明数组已经完全有序可以直接终止。优化之后冒泡排序在近乎有序的数组上时间复杂度可以从O(n²)降到O(n)这个特性在真实场景里非常实用。比如你有一份已经排好序的数据只是末尾追加了几个新条目冒泡排序跑一遍就能快速解决问题。插入排序的思路跟整理扑克牌一模一样从第二张牌开始依次把每张牌插入到前面已经有序的子序列中比它大的牌就整体后移腾位置。void insertionSort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; // 将比key大的元素向后移动 while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }这段代码有个天然优势比较和交换只发生在相邻元素之间所以它和冒泡排序一样是稳定排序。插入排序在“基本有序”的数据上表现非常好因为内层while循环往往执行不了几次就退出了。这个特性让它在工程上很吃香很多标准库的排序实现包括C的introsort和Python的Timsort在递归到底层、面对小规模子数组时都会切换成插入排序来收尾就是看中了它的低常数开销。选择排序的思路是最简单的每轮从剩余元素中挑出最小值放到已排序区域的末尾。但它的缺点也很突出无论输入数据是否有序每轮都必须完整遍历剩余部分来找最小值时间复杂度雷打不动O(n²)而且它是不稳定的。举一个不稳定的例子数组[3a, 3b, 1]第一轮找到最小值1与第一个元素3a交换结果变成[1, 3b, 3a]两个3的相对顺序被颠倒了。这个特性使得选择排序在工程上用途非常有限我现在基本只会在教学场景里写它。这三兄弟的适用边界其实很清楚算法时间复杂度平均稳定性额外空间实战推荐度冒泡排序O(n²)优化后可O(n)稳定O(1)低仅近有序时值得用插入排序O(n²)近有序时O(n)稳定O(1)高小规模数据首选选择排序O(n²)不稳定O(1)低教学用2.2 进阶排序归并、堆排序与快速排序的取舍当数据量升到十万、百万级O(n²)的排序连等结果都等不起必须换O(n log n)级别的算法。快速排序Quick Sort是应用最广泛的排序算法核心思想是分治每轮选一个基准值pivot把数组分成小于基准和大于基准两半然后递归排序左右两个子区间。最经典的实现是Lomuto分区法选最后一个元素当基准int partition(int arr[], int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; std::swap(arr[i], arr[j]); } } std::swap(arr[i 1], arr[high]); return i 1; } void quickSort(int arr[], int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } }快排最大的坑在基准值选择上。上面这种固定取末尾元素的做法一旦输入数据本来就是有序的每次分割都会极度不平衡递归深度变成n时间复杂度退化成O(n²)。工程上最常见的规避手段是三数取中取区间首元素、中间元素、尾元素的中位数作为基准。C标准库的std::sort更狠它用的是introsort——本质上是快排但设定了一个递归深度阈值当递归过深时直接切换成堆排序保证最坏时间复杂度不会超过O(n log n)。归并排序Merge Sort是另一种分治思路先把数组从中间拆成两半分别排序再合并两个有序序列。它是稳定的O(n log n)排序算法代价是需要O(n)的额外空间。void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; std::vectorint L(n1), R(n2); for (int i 0; i n1; i) L[i] arr[left i]; for (int j 0; j n2; j) R[j] arr[mid 1 j]; int i 0, j 0, k left; while (i n1 j n2) { if (L[i] R[j]) arr[k] L[i]; else arr[k] R[j]; } while (i n1) arr[k] L[i]; while (j n2) arr[k] R[j]; } void mergeSort(int arr[], int left, int right) { if (left right) { int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } }归并排序最大的优势是稳定且不受输入数据分布影响。无论输入是正序、逆序还是完全乱序它都能稳定在O(n log n)。所以在数据库这种需要稳定排序、数据量又大的场景里归并排序和它的变种依然是主力。在磁盘外部排序里归并思想也是绝对的核心。堆排序Heap Sort的思路是先把数组构造成一个最大堆然后反复将堆顶元素和末尾元素交换再调整剩余数组重新满足堆性质。它的优点是原地排序、最坏情况也能保持O(n log n)但它不稳定而且常数因子比较大实际排序速度通常不如快排。它的价值主要在于“最坏情况兜底”和“求Top K”这类不需要全排序的场景。这三种高级排序的取舍我的建议是只要不是必须自己手写就直接用标准库。C用std::sortintrosort需要稳定就std::stable_sort归并Python直接用sorted或list.sortTimsortJava用Arrays.sort根据类型选快排或归并。自己手写算法主要是为了学习和应付面试生产环境里标准库的成熟实现比绝大多数人自己写的都靠谱。2.3 工程场景里的排序细节结构体、pair与字符串热搜词里混了不少非常实际的问题“sort函数排序struct”、“vectorpairint,int排序”、“字符串排序”、“excel排序ip地址”。这些问题说明大家真正关心的不是手写排序而是怎么在真实代码里正确调用标准库的排序API。以C的std::sort为例有几个细节经常让人栽跟头。第一std::sort不是稳定排序。需要保持相等元素原始顺序的场景必须换成std::stable_sort。我之前在做一个订单管理系统时先按订单时间排序再按客户等级排序因为用了std::sort同等级的客户之间订单时间乱掉了测试用例直接挂掉。后来换成stable_sort就正常了。第二自定义比较器必须遵守严格弱序规则。最常见的问题是写了return a b或return a b。这种写法在ab时会同时让ab和ba成立违反严格弱序结果是未定义行为——可能崩溃可能排序错乱可能看起来正常但偶尔抽风。struct Person { std::string name; int age; }; std::vectorPerson people {{Alice, 30}, {Bob, 25}, {Charlie, 30}}; // 正确写法按年龄升序年龄相同时按姓名升序 std::sort(people.begin(), people.end(), [](const Person a, const Person b) { if (a.age ! b.age) return a.age b.age; return a.name b.name; });第三vectorpairint,int排序时如果没有自定义比较器默认会先按first升序first相同时按second升序。这个默认行为在很多场景已经够用。但如果pair里存的是坐标你想按x平方加y平方的距离排序就必须自己写比较器否则结果跟你的预期差了十万八千里。第四字符串排序同样是std::sort的活默认按字典序字节序排。但一旦涉及中文问题就来了。std::string的比较是按字节一级一级比的UTF-8编码下汉字的字节顺序跟拼音顺序完全没关系。比如“啊”的UTF-8编码是E5 95 8A“吧”是E5 90 A7按字节比较“吧”会在“啊”前面但拼音里“啊”(a)明显应该在“吧”(b)前面。我用C写了一个城市列表排序功能中文城市名按拼音排序的需求折腾了一个下午最后用了ICU库的collator才搞定。这个坑不遇到真的想不到。3. 查找算法实操顺序、二分与哈希3.1 顺序查找最笨但永远有用的方法顺序查找Sequential Search的思路零门槛从头到尾遍历数组遇到目标值就返回下标。时间复杂度O(n)。代码简单到不行int sequentialSearch(int arr[], int n, int target) { for (int i 0; i n; i) { if (arr[i] target) return i; } return -1; }就这个简单的循环也有一个优化技巧值得知道——哨兵位。把目标值放在数组末尾作为“哨兵”循环里就少了一个i n的判断int sentinelSearch(int arr[], int n, int target) { int last arr[n - 1]; arr[n - 1] target; int i 0; while (arr[i] ! target) i; arr[n - 1] last; if (i n - 1) return i; return (last target) ? n - 1 : -1; }这种做法牺牲了一个位置存哨兵换来了每次循环少一次比较。虽然现代编译器的优化能力很强但在数据量大或者循环次数极多的场景下这个优化依然有实际价值。我做过一个嵌入式相关的项目设备MCU主频很低内存也紧张每次查找都要尽量省运算哨兵查找在那时候确实比普通写法快一些。顺序查找的适用场景是数据量小、数据无序、查找频率不高。比如加载配置文件时遍历一遍找某个key或者处理用户输入的几个选项完全没必要上哈希表。很多人一听到“查找”就条件反射地用map其实在小数据量场景下顺序查找的常数极小性能一点也不差代码还简单。3.2 二分查找边界条件才是灵魂二分查找Binary Search在面试题里的地位等同于“两数之和”属于必考中的必考。热搜词里出现了一堆相关词条“二分法查找”、“二分查找pta函数”、“二分算法”、“二叉树查找”可见这个知识点的热度。算法思想一句话在有序数组里每次拿目标值跟中间元素比小于中间值就去左半边找大于就去右半边找每轮排除一半数据时间复杂度O(log n)。但代码写对的人真的不多。最经典的一个版本int binarySearch(int arr[], int n, int target) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) return mid; else if (arr[mid] target) left mid 1; else right mid - 1; } return -1; }这里有几个坑我大概在面试里看过不下一百个人踩过。第一个坑是mid的计算。写(left right) / 2的人很多正常情况下没问题但一旦left和right都接近INT_MAX两者相加就直接整数溢出了得到负数数组访问越界。用left (right - left) / 2就永远不会溢出。第二个坑是循环条件和边界值的搭配。上面代码里right初始化为n - 1循环条件是left right这是一个“左闭右闭区间”的写法。如果你把循环条件改成left right把right初始化为n那是“左闭右开区间”的写法对应关系完全不同。最可怕的是这两种写法混着来比如右边界是n但循环里还写mid - 1数据量稍大就直接死循环。第三个坑是“找第一个等于目标值的位置”这类变体。实际业务里我们经常要的不是“有没有”而是“边界在哪”。比如在一个有序数组里找某个分数段的人数就得找第一个大于等于60的索引和第一个大于90的索引。C标准库提供了std::lower_bound和std::upper_bound能直接完成这类操作强烈建议优先用它们而不是自己手写变种二分。// 找第一个 target 的迭代器 auto it std::lower_bound(arr.begin(), arr.end(), target); // 找第一个 target 的迭代器 auto it2 std::upper_bound(arr.begin(), arr.end(), target); // [it, it2) 区间内所有元素都等于 target注意二分查找的前提是数组有序。如果你的数据是动态插入的每次插入都要先做二分找位置、再移动元素维护有序数组的成本可能非常高。这种情况下别硬上二分考虑用二叉查找树或者跳表更合理。3.3 哈希查找与二叉查找树的实战对比除了顺序查找和二分查找工程上用得最多的查找结构是哈希表Hash Table和二叉查找树Binary Search Tree。哈希查找的核心是一个哈希函数把key映射成数组下标插入和查找的均摊时间复杂度都是O(1)。代价是空间占用比较大还需要处理哈希冲突。常见的冲突解决手段有链地址法和开放寻址法。Python的dict、Java的HashMap、C的std::unordered_map底层都是哈希表。我在实际项目里用哈希表的一个经典案例是去重。有一个功能要从几百万个手机号里筛出重复项最简单高效的做法就是全部塞进一个哈希集合里边插边查碰到已经存在的就标记为重复。整个流程跑下来大概几秒钟如果用嵌套循环两两比较跑一天都跑不完。二叉查找树则维护了一个有序结构任意节点的左子树所有值都小于它右子树所有值都大于它。查找时间复杂度平均O(log n)但最坏情况插入顺序恰好有序会退化成链表复杂度变成O(n)。为了根治这个问题工程上出现了各种平衡树AVL树要求左右子树高度差不超过1红黑树用颜色标记维持“近似平衡”。C的std::map底层就是红黑树插入、删除、查找都稳定在O(log n)。哈希表和二叉树怎么选关键在于你是否需要“有序性”。哈希表的优势是单点查找极快但它无法按照key的大小顺序遍历也无法做范围查询。二叉查找树天生有序可以很方便地做“找出所有成绩在60到90之间的学生”这种范围查询。我把这个决策逻辑整理成了下面这张表需求推荐方案原因静态数据一次构建多次查询哈希表O(1)查找性能极佳要求按key顺序输出二叉查找树 / 有序数组二分哈希表无法有序遍历数据量只有几十个顺序查找够用且最简单常数小数据持续插入且需要范围查询平衡二叉树 / B树兼顾插入和维护有序性超大数据量落磁盘B树减少磁盘IO次数需要稳定地最坏情况性能平衡二叉树哈希表最坏情况可能O(n)4. 常见问题与排查技巧实录4.1 边界条件翻车现场我这些年看过的算法代码边界错误简直是重灾区。下面这张表是我总结出来的高频翻车点基本涵盖了排序和查找代码里最容易出问题的位置问题场景翻车原因正确做法空数组没处理n0进入算法前先检查长度单元素数组二分循环条件写错导致无法进入明确使用左闭右闭或左闭右开并保持一致有大量重复元素二分返回位置不确定明确需求改用lower_bound/upper_bound数组长度很大(leftright)/2溢出用left (right-left)/2比较器违反严格弱序用了或统一用相等的元素返回false整数求和溢出大量数字相加超出int范围改用long long或提前检查递归深度过大快排固定选末尾元素做基准三数取中或改用introsort我自己印象最深的一次翻车是写归并排序的合并逻辑时把L[i] R[j]写成了L[i] R[j]。这个区别在大多数情况下不影响排序结果但在有相等元素时会破坏稳定性而且debug时特别难发现因为数组是有序的只是相对顺序变了。4.2 稳定性与排序结果的可预测性稳定性这个词对业务代码的影响比很多人想象的大得多。我举一个真实的例子一个报表功能需要先按日期排序再按金额排序。如果用的是不稳定排序第二轮的排序会打乱第一轮的结果导致同一天的数据里金额顺序是乱的。用稳定排序那么同金额的数据还会保持日期顺序。另外一个容易被忽视的问题是“排序结果可预测性”。不管数据是不是有序同一个排序算法、同一个输入输出必须完全一致。这样写测试用例才有意义。如果排序结果随执行次数发生变化自动化测试根本没法维护。所以在需要可预测结果的场景稳定排序几乎是硬性要求。4.3 实战选型速查表工程里最需要的就是能快速做决策。下面这张速查表是我这些年实际用下来总结的排序和查找的需求基本都能在这里找到答案数据规模排序方案查找方案100条以内插入排序或直接标准库sort顺序查找100到1000万条快排std::sort/introsort或归并排序后二分查找或哈希表1000万以上、内存够归并排序或数据库ORDER BY分片哈希或布隆过滤器先过滤数据在磁盘上外部归并排序B树索引需要稳定排序归并排序 / stable_sort不涉及插入删除频繁且需有序平衡二叉查找树std::map红黑树字符串、IP等复杂key自定义比较器注意编码自定义哈希函数这张表的核心逻辑很简单数据量小就选编码复杂度最低的方案数据量大优先时间复杂度需要稳定就选归并需要有序就选树只需要等值查询就选哈希。把这几个维度的优先级想清楚遇到排序查找的场景基本不会纠结。说实话排序和查找算法我写了这么多年最大的体会是面试和笔试让你手写快排和二分不是为了让你以后天天手写而是逼你理解每一步背后的原因。边界条件怎么处理、比较器规则怎么定、稳定性有什么影响这些细节才是决定算法代码能不能真正上生产环境的东西。最后给一个建议别只在在线刷题平台上刷算法题找机会把自己项目里的真实数据导出来亲手实现几种排序算法跑一遍看看它们在正序、逆序、大量重复值、超大数据量这些不同分布下的表现差异。这种亲手对比得到的体感比看一百篇题解都来得深刻。