说句实在话我一开始看到“排序查找简单模板”这几个字第一反应是这不就是每个程序员都该有的基本功吗可等我把“排序算法”“二分查找算法”“C语言排序数组”“字符串排序”“拓扑排序”这些热搜词串在一起看才反应过来问题远没有这么简单。排序和查找是数据处理问题的地基却也是最容易被轻视的部分。正因为看起来太基础很多人在笔试、面试、实际业务里反复栽跟头边界写错、死循环、排序结果和预期不一致、数据明明在却查不到。这篇文章就是把散落在各个热搜词里的需求收敛成一套可以直接抄的模板把排序和查找背后的逻辑讲透让新手能照着写老手也能回头查漏补缺。1. 排序查找的“模板思维”为什么记一堆代码不如留一套模板1.1 模板到底是什么一种可复用的解题骨架不少朋友听到“模板”两个字脑子里蹦出来的是 C 的类模板、Java 泛型、PPT 模板或者 Word 样板文档。这些确实是模板但排序查找里的“模板”是另一层含义它是一段被反复验证过、能应对大部分同类问题的程序骨架。比如二分查找不管题里数组是什么类型只要是有序集合、要查找目标值核心逻辑都是那十来行变来变去的只是比较规则和区间定义。把这段骨架固定下来遇到新题就不用从头推理边界条件而能把注意力放在“这个题和标准模板哪里不一样”上。我带新人的时候经常被问我背了十来个排序算法笔试还是会忘是不是记忆力不行我说你压根不该背算法你该背的是模板。算法书里的归并排序伪代码有一大堆但真正到了笔试考场两三分钟能默写出来的一定是你平时反复敲过、调过、踩过坑的那一版。这就是模板的意义它帮你把“想”的成本变成了“查”。新人要做的第一件事不是去网上复制高深莫测的代码而是从朴素版本开始敲出自己的模板库。就像厨师不会把整本菜谱背下来但一定会在手边备一份常用调味比例和刀工节奏模板库就是程序员的备菜筐用的时候顺手就能抓到不用临时翻书。1.2 一套好模板必须包含的三个要素我自己整理排序查找模板时会刻意检查三样东西缺一样都不放心放进模板库。第一数据怎么组织。数组还是链表数字还是字符串单关键字还是结构体多字段这决定了模板的形参和返回值怎么设计。第二比较规则是什么。升序还是降序按第一关键字还是第二关键字字符串是字典序还是长度优先这些规则应该是模板里可以替换的部分而不是写死的魔数。第三出口条件是什么。循环什么时候结束找不到目标返回什么值输入为空或者长度为一时会不会出问题这就是大家常说的边界条件。拿二分查找举例出口条件通常是 left right也就是区间里已经没有元素可查了但如果你用的是左闭右开写法出口就变成了 left right。两者看起来差不多实际运行完全不一样混用就是死循环和越界的直接来源。模板的核心价值就是把最容易出错的地方固定下来不允许每次临时改来改去。这也是为什么我在做代码评审时只要看到一个人写了好几种风格混杂的二分就会直接告诉他别调了重写一版比这个快得多。1.3 从热搜词看模板的边界模板字符串、类模板、树状数组模板这次整理热搜词的时候有个很有意思的现象和“模板”绑在一起的不止排序算法还有“模板字符串”“类模板名称不能重复”“树状数组模板”。这说明模板思维在各条技术路线里是通用的。模板字符串是语言层面的字符串拼接骨架类模板是类型层面的复用骨架树状数组模板则是为解决“动态前缀和与有序统计”这类问题沉淀下来的固定写法。所以下面给出的排序查找模板不只是给你几段代码抄更希望你能看到代码背后的复用思路同样的模板C 语言里可以用函数指针实现C 里可以用仿函数和 lambda 实现Python 里可以直接传函数参数数据库里则变成了 ORDER BY 子句和索引查找。技术形态不同骨架是相通的。理解了骨架你就能在不同语言里切换而不是每次换一门语言都要全部重学。2. 查找类模板从顺序查找到二分查找2.1 顺序查找模板最简单但应用场景最广顺序查找可能是所有查找算法里最不值得一提的。思路就是从头到尾扫一遍找到就返回下标找不到返回 -1。但我得说它的应用场景比想象中广得多数据量小、数据无序、查找次数少、或者根本不确定用什么规则排序时暴力遍历反而最稳。def linear_search(arr, target): for i, value in enumerate(arr): if value target: return i return -1这段代码没有任何技巧时间复杂度 O(n)空间复杂度 O(1)。你可能会吐槽这也能叫模板实际业务里我见过不少场景一个配置文件里要查某个 key 是否存在总共就几十项用户上传的临时目录里要定位某个文件名Excel 里某一行数据要按照姓名匹配另一张表……数据量在百级以内时这种写法既不需要排序预处理也避开了二分查找对有序要求的限制出错概率最低。我常说查找算法的选择不是“越高级越好”而是“前提条件是否满足、操作成本是否可接受”。2.2 二分查找模板边界处理是灵魂二分查找是查找类模板里真正的硬核角色。它有一个前提数据必须是有序的。在这个前提下每次取中间值和目标比较把区间缩小一半时间复杂度 O(log n)。大规模有序数据的查找需求基本都是用它解决的。def binary_search(arr, target): left, right 0, len(arr) - 1 while left right: mid left (right - left) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid - 1 return -1我见过太多人在这里栽跟头原因集中在三处。第一mid 的算法。直接写(left right) // 2在极端情况下可能溢出写成left (right - left) // 2才稳妥这个写法在 C、C、Java 里都适用。第二循环条件的符号。用while left right表示闭区间每轮都能处理到 left right 时那个唯一的元素如果写成left right最后一个元素就可能被漏掉。第三在arr[mid] target时忘记把 mid 跳过去导致区间里永远包含当前 mid最后死循环。我自己的习惯是一套代码里只维护一种区间写法。要么全用闭区间 [left, right]循环条件left right更新就是left mid 1、right mid - 1要么全用左闭右开 [left, right)循环条件left right更新是left mid 1、right mid。最怕的是左半边用左闭右开、右半边用闭区间这种混搭是错误的最大来源。2.3 二分查找变体模板lower_bound 和 upper_bound比基础二分查找更实用的是两个变体模板。它们解决“有序数组里第一个大于等于目标值的位置”和“第一个大于目标值的位置”这类问题对应 C 标准库里的 lower_bound 和 upper_bound。def lower_bound(arr, target): left, right 0, len(arr) while left right: mid left (right - left) // 2 if arr[mid] target: left mid 1 else: right mid return left def upper_bound(arr, target): left, right 0, len(arr) while left right: mid left (right - left) // 2 if arr[mid] target: left mid 1 else: right mid return left这两个模板用的是左闭右开区间写法。lower_bound 返回第一个arr[mid] target的下标upper_bound 返回第一个arr[mid] target的下标。二者之差正好是 target 在数组里的出现次数。需要统计“有序集合中某个数值区间的元素个数”时一行代码就能算出来不用再循环遍历比大小。为什么变体这里不用闭区间因为左闭右开和 STL 语义天然对齐返回值可以直接当数组下标用对空数组也安全不会返回一个让人误会的哨兵值。我建议把基础二分和变体二分分开记忆二者循环条件和区间更新策略不同强行合并成一版反而容易混。如果笔试里不确定就花三十秒从“数组长度为 1”这个最小例子推一遍再写基本不会错。2.4 从查找模板到实际场景字符串查找、Excel 单元格查找查找目标不一定都是纯数字数组。“python查找excel中字符串”这类需求本质是把一列数据当成字符串数组做精确匹配或者子串匹配。数据量大时先排序再用二分查找模板定位量小时线性扫一遍足够。而“excel查找替换功能输入不了特殊符号”这个热搜词根源在于 Excel 的查找替换对话框把星号、问号当成了通配符想查字面的这些字符需要在前面加波浪号转义。这和编程里查找模板的逻辑一样查找规则不对目标永远查不中。所以我说查找算法的选择要结合数据规模、有序性和查找频率。有人一上来就写二分结果发现数据根本没排序还得先排序排序完又发现该数据每次都在变维护排序的代价反而更高。这种时候顺序查找其实是更合理的选择。判断力比代码本身更值钱。3. 排序类模板从基础排序到复杂排序3.1 冒泡排序与选择排序模板O(n²) 也不丢人排序算法里最容易在面试中被问的是快排和归并但最容易被忽略的反而是基础排序。我在业务里见过有人用冒泡排几千行配置数据——那其实不算错数据量小代码简单维护成本低。问题在于很多人连这个简单模板都写不稳。选择排序有个隐藏的坑每一轮并不是立刻交换而是先找到本轮最小值下标一轮结束后再交换。如果每比较一次就交换一次会把大量无意义的赋值操作做进去虽然功能没错性能却白白降低。void selection_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int min_idx i; for (int j i 1; j n; j) { if (arr[j] arr[min_idx]) { min_idx j; } } if (min_idx ! i) { int tmp arr[i]; arr[i] arr[min_idx]; arr[min_idx] tmp; } } }冒泡排序模板建议加一个剪枝标志如果某轮没有任何交换说明数组已经有序直接退出。这个优化在接近有序的数据上能省下大量时间而且代码并没有复杂多少。void bubble_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped 1; } } if (!swapped) break; } }这两个模板适合笔试基本功检查和小规模数据验证思路。它们不是最优雅的但一定是最不容易写错的。快排分区逻辑一复杂就容易出问题选择排序反而可以闭着眼写。3.2 快速排序模板与归并排序模板稳定性和逆序对的取舍真正在生产环境被高频使用的排序是快速排序。绝大多数语言标准库的排序实现底层都基于快排的变体所以业务代码里通常不该自己写快排直接调用 sort 就行。但作为模板我建议掌握一个版本因为笔试说不准什么时候就会让你手撕。def quick_sort(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] left [x for x in arr if x pivot] mid [x for x in arr if x pivot] right [x for x in arr if x pivot] return quick_sort(left) mid quick_sort(right)这个版本的效率不是最高的但理解成本最低。它用三句话做了分区小于、等于、大于。第一次接触快排的人从这个写法入门更容易看清分治思想。等你需要写 C 语言版本时再把列表推导换成双指针原地分区即可。归并排序模板的价值则在稳定性和分治结构def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) res [] i j 0 while i len(left) and j len(right): if left[i] right[j]: res.append(left[i]) i 1 else: res.append(right[j]) j 1 res.extend(left[i:]) res.extend(right[j:]) return res归并排序时间复杂度稳定在 O(n log n)且是稳定排序。如果你在做“统计逆序对”的题归并的合并过程顺手就能算出来如果排序对象是结构体且要求相同关键字保持原顺序也必须选择稳定排序。这也是为什么很多算法题的标准答案都会用归并。3.3 自定义比较器结构体排序的灵魂真正能让排序模板从“能跑”变到“好用”的是比较器。C 语言的 qsort 规定比较函数返回负数、零、正数C 的 sort 支持 lambda 表达式Python 的 sort 接受 key 函数Java 里则是 comparator。这些都是同一件事的不同外衣。“C语言排序数组”看起来简单但如果数组里存的是结构体呢比如按姓名字典序排学生记录再按年龄升序作为第二关键字。我习惯写一个比较函数传给 qsortstruct Student { char name[64]; int age; }; int cmp_student(const void *a, const void *b) { const struct Student *sa (const struct Student *)a; const struct Student *sb (const struct Student *)b; int name_cmp strcmp(sa-name, sb-name); if (name_cmp ! 0) return name_cmp; return (sa-age sb-age) - (sa-age sb-age); } qsort(students, n, sizeof(struct Student), cmp_student);这里有个常见错误比较函数写成return a-age - b-age。在 age 差值很大的时候可能溢出导致排序结果诡异。稳妥的写法是像上面那样用逻辑表达式(sa-age sb-age) - (sa-age sb-age)它只会返回 -1、0、1永不溢出。这类细节就是面试官最爱挖的坑也恰恰是模板注释里最该写的注意事项。3.4 拓扑排序模板有依赖关系的“排序”除了数值排序还有一种排序在处理任务调度、课程编排、流程图时非常常见就是拓扑排序。它的输入是有向无环图输出是一个线性顺序保证每个节点都出现在所有依赖它的节点之前。from collections import deque def topo_sort(n, graph, in_degree): q deque([i for i in range(n) if in_degree[i] 0]) order [] while q: u q.popleft() order.append(u) for v in graph[u]: in_degree[v] - 1 if in_degree[v] 0: q.append(v) if len(order) n: return order else: return []这个模板有两个关键点。第一入度为 0 的节点先入队它们没有前置依赖可以先输出。第二每处理完一个节点把它后继节点的入度减一减到 0 再入队。如果最后 order 长度不等于 n说明图里有环不存在合法的拓扑排序。这类模板我在给前端依赖树做构建顺序规划、给任务列表做依赖排序时都用到过属于“排序”里思路最特别的一种。3.5 其他排序模板字符串排序、树状数组辅助排序字符串排序的核心问题无非是“按字典序还是按长度排”以及“中文按拼音还是按 Unicode 码排”。实际工程里Python 用 sorted 加 key 参数C 语言用 qsort 加 strcmpJava 用 Collections.sort 加自定义 comparator。这里的模板主要就是比较规则的定义代码本身反而简单反而不值得去背所谓“字符串排序算法”。树状数组模板则适合处理“动态前缀和 排序后统计”的场景。比如要快速查询某种数值在已排序数组中的排名可以先对数组离散化再用树状数组记录每个排名出现的次数这样在某个排名区间内做统计时查询和更新的复杂度都是 O(log n)。这类模板在竞赛题里常见业务里用得少但思路值得收藏起来遇到“频繁更新 频繁问排名”的需求时会比排序后暴力统计优雅得多。4. 模板在真实业务和办公场景中的应用不只会写代码4.1 数据库排序与查找MySQL ORDER BY 背后的有序性逻辑日常写业务时排序查找的需求很少自己写算法而是都交给了数据库。“mysql排序”“oracle 取值大小排序”“sql server 分组后组内排序”这些热搜词说的其实就是这件事。MySQL 的 ORDER BY 语句如果表很小直接全表扫再排序没什么问题数据一旦上了百万级没有任何一个代码模板能救你只能靠索引。B 树索引天然保持数据有序优化器在排序时可以利用索引顺序扫描避免额外的 filesort。这里的“排序查找模板”其实就是 SQL 的写法规范过滤条件要能命中索引排序字段最好和 where 条件的联合索引匹配字符串排序要注意字符集和排序规则。举一个常见的反例WHERE 子句里写了LOWER(name) abc这类对列做函数运算的写法会破坏索引的有效性查询就会走全表扫描性能断崖式下跌。把业务查询当成“数据有序性”问题来思考其实和写二分查找模板时的思路完全一致先看前提条件是否满足再决定用哪种路径。这不是让你背 SQL 技巧而是让你养成先看执行计划、再写语句的习惯。4.2 办公自动化中的模板Word、PPT 和“改了打不开”的问题再来看“poi 生成 word”“通过修改模板中的图表数据修改word图表”“修改数据后无法打开生成的word”这些词。它们属于办公自动化里的模板文件操作。很多朋友会把 docx 文件当成普通文件直接改内部 XML或者在原模板上反复覆盖再另存结果很容易损坏文件。我的经验是用 Apache POI 修改 Word 模板里的图表数据最稳妥的做法是先把模板读成内存对象再以它为基础生成新文档而不是每次直接改同一个文件再另存。也就是说要保持“基础模板 每次生成副本”的生产模式。这样能避免文件内部引用错乱也防止生成到一半时原模板被破坏。POI 对图表数据源的处理在不同版本上有不少差异千万不要让修改逻辑长在同一个文件句柄上否则很容易出现“改了之后打不开”的问题。“模板”这个词在这里的含义是复用骨架但复用时必须保留一份干净底稿每次都在底稿上做一次性派生。4.3 编译期模板问题类模板名称不能重复热搜词里“类模板名称不能重复”其实是个经典编译报错在同一个命名空间或作用域里声明了两个同名类模板。这类报错本身很简单但解决并不总是删一行那么简单。如果你在做版本兼容可能有两种功能不同但名称恰好相同的类模板需要把其中一个放进独立的 namespace或者用预处理宏控制编译分支。从模板的复用视角看这个报错也在提醒我们代码模板不是越多越好每个模板都要有独立的名字和明确职责。我的代码库里就曾出现过同事复制了一个模板类又忘记改名编译报错查了半天最后靠全局搜索同名类模板才定位。从此我给自己定了个规矩模板文件放进工程先检查类名唯一性再检查构造函数、成员函数和既有模板是否冲突。这个检查耗时不到一分钟但能省掉每次几小时排查成本。5. 常见问题与排查技巧实录5.1 二分查找死循环与越界两个必查项目二分查找最容易出现的问题有三个我列成一张速查表现象可能原因处理办法程序卡住不结束区间更新没有排除 mid或循环条件写反确保每轮 left 或 right 严格缩小越界访问 arr[mid]right 初始值写成 len(arr)却使用闭区间循环统一区间写法不混用左闭右开和闭区间找到却返回错误位置比较规则写反或者数组没有先排序先排序再查找排序比较和查找比较保持一致排查时我会在循环里打印 left、mid、right 三个值观察区间是否一直在收缩。只要每轮都严格收缩二分查找就不会死循环。越界问题几乎全部来自 left、right 初始化和循环条件的“半套组合”。写模板之前先想清楚你是左闭右开还是闭区间然后全程都按这一种写。5.2 排序结果和预期不一致稳定性和比较器双重检查排序结果“看起来不对”第一件事查的是比较器。我在一次真联调里遇到过排序结果在本地和服务器上不一样最后发现是比较器用了浮点数比较精度问题导致本应相等的数值被判定不相等。第二件事是查排序是否稳定。如果排完之后相同关键字的相对顺序变了看起来就会像“乱排”这时要换成归并排序这类稳定排序或者在比较器里加入第二、第三关键字明确优先级。数据量不大时直接在排序前打印几条原始数据排序后再打印几条对照着看比盯着代码猜快得多。5.3 查找不到时的返回值设计别让 -1 变成炸弹顺序查找和二分查找在找不到目标时一般返回 -1但这在业务里经常导致后续逻辑混乱。比如你在模板方法里直接拿返回下标去取数组元素-1 在某些语言里会访问数组最后一个元素Python 里甚至不会报错结果却完全是错的。所以我建议在调用处增加一个判断找不到时走独立分支不要继续使用结果。如果封装的是一个库函数返回值语义要写清楚最好用“返回下标 是否存在的布尔位”这种组合或者干脆返回 NULL / 空值避免调用方把 -1 当正常下标。这个设计看似细节线上故障往往就藏在里面。5.4 模板代码管理的几个土办法最后分享几个我整理模板的土办法。一是每个模板文件开头写清楚时间复杂度和适用条件注明这个模板的坑在哪里。二是用统一命名规则比如 binary_search / binary_search_first_ge前一个找精确位置后一个找第一个不小于目标值的位置避免两个模板长得像、用时拿错。三是定期把笔试和线上问题里踩到的新坑补进注释把模板库当成长期积累而不是一次性脚本。你会发现自己整理的模板才是真正能随手拿来用的因为它记得住每个坑。我个人在实际使用中最大的体会是每次碰壁后把“错误写法”和“正确写法”一起补进模板注释刚开始觉得浪费时间但当我在一次线上问题里从模板库翻出那条注释发现和这次问题一模一样时才明白真正让模板值钱的不是你十分钟内默写出的代码而是踩过的每一个边界条件的坑。你如果也有自己的排序查找模板库不妨花半天时间重新过一遍把之前没写明白的边界条件补上以后写任何查询、排序逻辑都能更踏实。这个积累越早开始越好用。