排序这块内容几乎是每个学编程的人绕不开的一道坎。不管是校招笔试、面试八股、日常业务开发还是数据结构和算法的系统学习排序永远会占据一个特殊的位置。但这个专栏标题里最值钱的部分其实是后面那个括号——“包括时间复杂度讲解”。因为很多人排序代码背得滚瓜烂熟一到“为什么这个算法好”“数据量大了会怎样”就卡壳。这篇文章我就把这套东西从头到尾捋一遍把排序算法的实现、复杂度分析的思路、以及在实际项目里怎么选型一次性讲明白。不管你是正在备考的学生、准备跳槽的开发者还是工作中被排序需求困扰的业务程序员都能从这里拿到直接能用的东西。1. 排序专栏的整体思路先建立时间复杂度直觉再去记算法1.1 为什么讲排序必须从时间复杂度切入我见过太多初学者学排序是这么个过程先背一个冒泡排序的代码然后背一个快排的代码考试能默写出来就算学会。但一旦被问“这两种算法差多少”“100万条数据排序需要几秒”就答不上来了。问题出在哪出在把排序学成了死记硬背没有建立复杂度意识。时间复杂度这个概念本身并不难但它不是靠“记住定义”就能掌握的需要在具体的算法里反复体会。排序算法恰恰是最好的复杂度分析练习场——因为它有足够多的算法变体冒泡、选择、插入、希尔、归并、快排、堆排它们的复杂度从O(nlogn)到O(n²)都有空间复杂度也是各不相同同一个算法在最好、最坏、平均情况下的表现还可能差异巨大。所以说排序专栏必须把时间复杂度的讲解放在最前面而不是只贴代码。先搞清楚“复杂度到底在衡量什么”再回头去看每个排序算法你会发现一切都顺了——你会知道为什么插入排序在近乎有序的数组上能跑赢快排知道为什么快速排序虽然平均快但总有人觉得它不稳知道为什么数据库和Java底层都不约而同选择了某种排序作为兜底。1.2 大O记号是怎么帮你“估算”性能的要理解时间复杂度先得理解大O记号代表的是一种“数量级”的感觉而不是具体耗时。大O描述的是当输入规模n增长时算法操作次数的增长趋势。换句话说它回答的是“数据翻倍时间大约翻几倍”这个问题。我习惯用一个很生活的类比来解释这件事假设你要在1000页的字典里找一个词。如果你一页一页从前往后翻运气好第1页就找到运气差翻到底。平均来说大约要翻n/2页。这就是O(n)线性查找。如果按字母索引二分着找每次都能排除一半的范围从1000页里定位只需要约10次。这就是O(logn)快得离谱。如果做一件事要两层循环嵌套比如拿每一页去和其余所有页比较那就是O(n²)1000页就要做大约100万次比较。这三个数量级的差距在n1000时还只是“看起来差很多”但到了n1000000时候差距就变成了天壤之别。我随便估算一比特O(n²)的一百万数据要做10¹²次操作而O(nlogn)的大约是2×10⁷次相差五万倍。这就是为什么工程师在数据量大的时候坚决不用冒泡排序——不是冒泡有问题是它的复杂度决定了它在大规模数据下必然失控。另一个容易踩的坑是“忽略常数和低阶项”。很多初学者会说快排平均O(nlogn)归并也是O(nlogn)那它们应该差不多快。实际上快排在小数据上也经常比归并快不少因为快排的常数因子更小、缓存友好度高。大O记号只告诉你“趋势”真正的性能还得看具体实现、数据特征和硬件特性。1.3 最好、最坏、平均三种情况加上一个稳定性一个排序算法的时间复杂度光说一个平均数是不够的。严谨的分析要区分最好情况、最坏情况和平均情况。冒泡排序在已经排好序的数组上如果加了标志位一趟扫描下来发现没有交换复杂度就能降到O(n)但同样的算法在倒序数组上就是标准的O(n²)。快速排序平均是O(nlogn)但如果每次选的基准数都恰好是数组里最大或最小值它的分区会退化成O(n²)。这里我还想多说一句**稳定性的含义是排序后相同元素的相对顺序保持不变。**这一点在你只按某一个字段排序列时特别重要。比如你先按年龄排序再按姓名拼音排序如果第二次排序是稳定排序那么年龄相同的人在内部仍然保持第一次的拼音顺序。Java对象的sort就利用了这个特性可以做到多级排序。判断一个算法是否稳定不用死记看它的交换方式就能推导出来冒泡排序仅相邻元素交换相同值不会跨过对方所以稳定选择排序会“跨距离”交换把最值扔到前面去同值元素的相对位置可能被改变所以不稳定插入排序逐个向后搬动稳定快排有跨区间交换不稳定归并排序是分组后按顺序合并稳定堆排序的交换距离极大基本不可能保证稳定。主流的O(nlogn)排序算法里只有归并排序是天然稳定的这也是它至今仍是很多语言内置排序核心组件的原因之一。想清楚这些基本盘后面看任何排序器的设计思路都能看透。2. 手撕排序从O(n²)到O(nlogn)的进阶路线2.1 被低估的O(n²)三兄弟冒泡、选择、插入O(n²)级别的排序算法经常被人当成“入门玩具”但实际上它们各有不可替代的价值。冒泡排序理解起来最直观就是把大数逐步“冒泡”到尾部。它每趟排序都能确定一个最大值的位置n个元素要跑n-1趟每趟比较长度递减。最朴素的写法没有任何优化稳定跑满O(n²)。但如果你加一个swapFlag标志位当某一趟完全没有发生交换时就可以提前结束。在近乎有序的数组上加了标志位的冒泡可以把复杂度降到接近O(n)这个优化在真实业务里非常常见——很多对历史记录做“补排序”的小需求其实底层就是类似思路。选择排序的思路比冒泡更直接每趟扫描剩余区间选出最小值放到已排序区间的末尾。它和冒泡的复杂度一样都是O(n²)但交换次数少很多每趟只交换一次。缺点是它不稳定——“跨距离”交换是罪魁祸首。而且无论输入有序还是无序选择排序都得老老实实跑完所有的扫描没有提前退出的机会。它倒是有一个特殊优点交换次数是全部排序算法中最少的之一。在某些交换成本极高比如大对象swap的场景选择排序反而有优势。插入排序我是真心想替它正名。它的思路类似于你在斗地主时理牌每次抓一张新牌把它插入到已经整理好的手牌里合适的位置。它的复杂度同样是O(n²)但在两个场景下它表现极好一是数据量小比如二三十个以内二是数据“几乎有序”。几乎有序指的是每个元素距离它最终位置不远这时候插入排序的内层循环很快就跳出总复杂度趋近O(n)。这就是为什么很多工程化的排序算法里都保留了一个“小数组兜底逻辑”——当递归分治到数组长度小于某个阈值时直接调用插入排序收尾性能反而比继续递归更好。我一直建议初学者把这三个算法都自己亲手写一遍然后跑一下数据量从100到10000的耗时变化。你会直观感受到“O(n²)”这个符号背后对应的真实延迟增长曲线这种体感是任何理论分析都给不了的。2.2 进阶王牌快速排序、归并排序、堆排序快排的地位不用多说它是绝大多数实际排序场景的主力。核心思想就四个字分而治之。选一个基准元素pivot一趟分区把小于它的放左边、大于它的放右边然后分别对左右两个子区间递归重复。快排的平均复杂度是O(nlogn)最坏是O(n²)。最坏情况发生在每次分区都极端不平衡时——比如数组本身已经有序而你又每次选择第一个元素作为基准。避免这个问题最有效的办法是随机化基准选择或者在开始前先把数组打乱一遍。随机基准把“最坏情况”变成了一个概率极低的事件这也是“随机化算法”思想的一个经典应用。代码实现上分区函数partition是快排的灵魂经典的Lomuto分区实现简洁但常数略大Hoare分区实现更复杂但平均更快。在工程实践里多数语言底层并不直接用最朴素的快排而是用它的改良版本。归并排序的思路是“先拆后合”把数组对半拆开直到每个子数组只剩一个元素然后再两两合并合并过程中按序挑出较小值。归并排序最大的优势有两个一是复杂度稳定在O(nlogn)无论输入有序还是无序它都是这个表现这一点比快排更“老实”二是它是稳定排序。代价是需要额外的O(n)内存来辅助合并。我前面提到过Java对对象数组的sort用的就是TimSort也就是归并排序的改良版。堆排序是另一个O(nlogn)选手它利用二叉堆的性质不断取出堆顶元素然后调整剩余元素维持堆结构。堆排序的优点是完全原地排序不需要额外空间最坏情况下也能保持O(nlogn)。缺点是不稳定、常数因子偏大、对缓存很不友好。实际上堆排序的用处更多体现在“动态取最大”的场景比如任务调度、TOP K问题而不是作为一个单纯的数组排序器去和快排竞争。想把这块学扎实建议你把这几个算法写成可以打印出每一趟结果的版本亲自观察一下各个算法在同一个乱序数组上的处理过程。我会在后面的“常见问题与调试”部分专门列一份排查清单这里面细节坑比很多人想象的多。2.3 一张复杂度对照表把核心信息压在一起整理一张表把主流排序算法的核心参数列出来方便参考和复习。这张表里的数据都是基于基础实现分类的特殊优化会改变某些行的数值比如加了标志位的冒泡和插入排序在有序场景是O(n)。排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(nlogn)~O(n^1.5)取决于增量序列O(1)不稳定快速排序O(nlogn)O(n²)O(logn)递归栈不稳定归并排序O(nlogn)O(nlogn)O(n)稳定堆排序O(nlogn)O(nlogn)O(1)不稳定我自己当年学这张表的时候最容易记混淆的两个点一是快排的空间复杂度不是O(1)它虽然原地交换但递归调用会占用栈空间平均是O(logn)最坏是O(n)二是希尔排序的时间复杂度其实没有一个绝对准确的公式它和增量序列的选择强相关。这张表还能帮你反向推导出很多决策。比如有一个需求数据量极大、内存不够、要求稳定、必须复杂度可控——归并排序几乎就是为这个场景量身定做的。又比如数据量不大、不需要稳定、想代码简单——插入排序就够了。梳理出“算法—场景”的对应关系比单独记忆算法本身要有用得多。3. 工程实战语言内置排序背后的门道3.1 Java和JavaScript的sort为什么和你手写的不一样很多新手第一次接触Java的Arrays.sort会困惑明明学排序算法时老师让我写各种排序怎么Java自己用的排序这么复杂实际上Java对基本类型数组如int[]、char[]的排序用的是Dual-Pivot Quicksort双轴快排对对象数组的排序则用TimSort。你查文档时可能还会看到它包含一个阈值判断——数据量小的时候直接转插入排序数据量大的时候走分治路线。这种“混合排序”是现代工程排序的常态。更值得提醒的是JavaScript的sort方法有个著名的坑如果数组元素是数字直接用sort()它默认会把元素转成字符串再比较结果就是 [10, 9, 2, 1].sort() 会变成 [1, 10, 2, 9]这种看上去完全不对的结果。原因在于默认比较器是字典序比较字符串比较是一位一位比字符的所以“10”会排在“2”前面。正确的做法是传入比较函数(a, b) a - b。这一点我在第4章讲字符串排序时会再展开因为它本质上暴露了“排序的比较规则”和“数组本身的结构”这两个维度是独立的。工程上我强烈建议你养成一个习惯**任何语言的内置排序在传入自定义比较器时一定先明确比较器返回值的语义——负数代表a在前正数代表b在前0代表相等。**这个约定在所有主流语言里是通用的但它太基础了以至于经常被忽略一旦忽略就会产生微妙的bug。3.2 数据库排序索引、ORDER BY和组内名次从搜索引擎热词来看很多人会搜“mysql排序”“oracle取值大小排序”“sql server分组后组内排序”。这些看似是不同数据库的语法问题背后其实是同一个本质——SQL的ORDER BY子句决定了查询结果集的排序规则。MySQL里最简单的用法是SELECT ... ORDER BY column DESC。但如果数据量很大ORDER BY一个没有索引的字段会导致数据库先临时排序这个过程可能非常吃内存。如果排序字段上有索引数据库可以直接按索引顺序扫描返回结果效率高很多。所以常见的侧写是看到慢查询里有“Using filesort”就要考虑是否需要建索引。这里“filesort”并不是指真的把数据写到文件而是指数据库需要额外的排序步骤。Oracle和SQL Server的排序基本语法类似。真正拉开差距的场景是“分组后组内排序”——这就要请出窗口函数了。SQL Server里用ROW_NUMBER() OVER (PARTITION BY 分组字段 ORDER BY 排序字段)来给组内记录编序号。如果你搜到过“sql server 分组后组内123排序”其实就是ROW_NUMBER函数的应用场景。不过这里有个常规陷阱ROW_NUMBER生成的序号不允许并列即使字段值相同也会强行分出先后如果想保留并列排名需要用RANK()或DENSE_RANK()。三者的区别用一次考试分数举例就是ROW_NUMBER按物理顺序编连续号没有并列一说。RANK并列时占用序号位比如两个并列第一下一名排第三。DENSE_RANK并列不占序号位两个并列第一后下一名还是排第二。这个问题在工作中特别常见我几乎每年都会被问到一次。第一次用窗口函数做分组排名的人十有八九会在这个细节上栽跟头。至于Tableau、Sequelize这类工具或者框架里的排序它们本质上都是把用户的排序意图翻译成SQL的ORDER BY或者数据源的排序操作理解底层SQL逻辑之后各种工具的语法差异就都只是皮相了。3.3 实际写代码时排序选型的决策清单结合数据规模、数据特征、稳定性需求这三个维度我整理一个实践经验里的选型参考清单可以直接对照着来。数据量很小几十个以内或者数据基本有序优先插入排序简单高效。数据量中等内存充裕需要稳定输出归并排序或者直接用语言内置的TimSort。数据量很大不要求稳定不要求原地修改普通快排加随机基准就够了。数据量很大内存紧张只能原地排序堆排序场景极其少见但确实存在。只找最大/最小的前K个值优先用堆不要全量排序。数据库里的排序交给SQL的ORDER BY能走索引就绝不让它走filesort。有一个很重要的工程原则**语言内置排序永远是你的第一选择。**只有当你确认内置排序无法满足需求比如你明确知道数据量超出内置策略的适用范围、需要自定义更彻底的结构时才考虑自己重新实现。很多性能问题其实出在“用户自己写了一个低效排序”而不是“内置排序不够快”。这一点我反复强调过很多次。4. 那些“不走寻常路”的排序场景4.1 拓扑排序给依赖关系排队“拓扑排序”在热词里反复出现它虽然也叫排序但和“把数字从小到大排列”完全是两码事。拓扑排序处理的是有向无环图DAG里的节点顺序如果存在一条边指向B说明A必须先于B完成那么排序结果里A必须出现在B之前。典型应用场景包括课程先修顺序的安排、编译构建工具里任务执行顺序的推导、以及包管理器里的依赖安装顺序。实现拓扑排序的核心思路是Kahn算法先统计每个节点的入度把入度为0的节点放入队列然后逐个出队每出队一个节点就把所有依赖它的节点的入度减1当入度变为0时再入队直到队列为空。如果最终处理过的节点数少于总节点数说明图里存在环也就是存在循环依赖这时候任务顺序无法确定。热词里有个“programmer升职记排序楼层”其实那个游戏里有一关的任务本质就是调度多个任务并满足依赖顺序把它理解成拓扑排序后就容易多了。学习这部分内容的最大价值在于你会意识到“排序”这个单词在不同语境下的含义差异极大动手之前先把问题定义清楚永远比急着写代码重要。4.2 字符串排序里的“字典序冤案”字符串排序是工程中出现频率最高、也是最容易让人困惑的排序场景之一。它的特殊之处在于字符串默认的比较规则往往不是你想当然的“长度优先”或“数值优先”而是字典序——先比较第一个字符如果相同再比较第二个字符以此类推。于是就有了一些经典现象[10, 9, 2]按字典序升序是[10, 2, 9]因为字符“1”小于“2”小于“9”长度完全不起作用。含有字母和数字混合的字符串“A10”和“A2”按字典序比较时“A10”会在“A2”前面因为第2个字符“1”比“2”小。全角半角、大小写、中文编码等因素也会让结果显得“不合常理”。如果你自定义一个排序规则希望你拿到“A2”排在“A10”前面也就是把字符串内部的数字部分当成一个整体来比较就得自己实现“自然排序”比较器。在JavaScript里可以用localeCompare配合numeric选项在Java里可以用Java 8之后引入的字符串比较器或者自定义Comparator在Python里可以直接写keylambda x: int(正则提取的数字部分)然后先比较数字再比较字符串。这类需求在文件名排序、版本号排序、日志文件整理里特别常见。我建议你在实现任何字符串排序之前先把需求里的比较规则用一两句话写清楚否则一归纳代码你会发现“排序结果为什么这么怪”的问题又出现了。4.3 MapReduce排序当排序遇到了分布式热词里出现了大量“mapreduce排序—分组排序”“mapreduce排序—自定义排序”“mapreduce排序—倒排序索引”这样的条目。这其实是很多人在学习大数据框架时遇到的实践题。MapReduce里的排序不是一次性把所有数据放到一个数组里排而是在分布式计算的Shuffle阶段完成的mapper输出的键值对会先按key分区每个分区内部再按照key排序之后进入reducer。“分组排序”就是按key分组后组内再按value排序这在很多数据处理场景里要求你写一个自定义的比较器来指定排序字段和顺序。倒排序索引则是按文档做排序索引后反过来按词来组织的典型应用网上能找到大量填空式教程。对这些太细节的技术这篇文章不展开写实现但我建议所有学这部分的朋友都亲手跑通一个最简示例写一个MapReduce程序自定义key和value的排序规则观察Shuffle阶段的输出顺序。比起只看概念这样对理解分布式排序的“大局观”有很大帮助——你会明白如果单机的归并排序是不依赖全局内存的巨大归并那么分布式排序的精髓就是“分而治之归并思想”的极致体现。5. 常见问题与实操调试技巧5.1 为什么你写的快排总是不如内置函数快很多人在面试手撕快排时自我感觉良好但是一跑大数据量就发现性能不对。我复盘了一下通常出问题的点列成一份排查清单供你对照。递归深度过大导致栈溢出。如果你自己在Java里写递归快排却把一个较大数组倒序排输入最容易触发这个问题。解决办法是随机基准、随机打乱输入或者干脆改用非递归实现。分区函数写得不够高效。经典Lomuto分区思路虽然直观但其交换次数偏多工程上更常见的Hoare分区虽然在数值分布崎岖时比较绕但常数因子更优。小数组还在继续递归。很多生产级快排会在子数组长度小于某个阈值比如10到20时改用插入排序长期递归会让小数组的调用开销被无限放大。使用了额外数组。有些初学实现为了省事在分区阶段创建左、右两个新数组再拼接这会让空间复杂度从O(logn)直接退化为O(nlogn)性能大打折扣。基准选第一个或最后一个元素碰上有序输入直接进最坏情况。这一点前面已经反复强调过。我给学生的建议是先手写一个“教科书版快排”运行通过后再去对照生产级代码看它做了哪些额外优化然后逐个在简历上写“熟悉快排的工程优化”不是背概念是真的能说清楚在哪几行代码上做了优化、带来的效果是什么。5.2 稳定性判断速查表再次把稳定性的判断总结成表方便记忆。这里我给一个可以推导出结论的方法观察算法是否可能存在“跨越相等元素”的交换如果可能就不稳定。排序算法是否稳定判断依据冒泡排序稳定只交换相邻元素相等不交换选择排序不稳定将最值跨越多个位置交换插入排序稳定只向后挪动已排序元素相等位置不越过希尔排序不稳定分组跳步移动破坏相对顺序快速排序不稳定分区交换可能跨越相等元素归并排序稳定合并时优先取左子数组元素同值保持前者在前堆排序不稳定任意距离的父子交换稳定性不是一个“最好能有”的性质而是一个工程需求。例如有一个学生成绩表需要按总分排序总分相同再按学号从小到大排这时你先按学号排一次序再用稳定排序按总分排一次就能直接得到结果。如果第二次用的是不稳定排序总分相同的内部顺序就乱了。5.3 竞赛题背后的套路礼盒排序和三值排序热词里有两道竞赛题需要注意一道是美国USACO里的“三值排序”另一道是GESP四级“礼盒排序”。这两题如果只是刷题你很容易被表面的“排序”概念带偏把它们当普通排序题做但实际上它们考的是另一种“排序思维”。三值排序是一种只有三种值的序列重排问题。它的核心思路不是“调用一次排序”而是统计每种值的出现次数找到错位区间然后直接计算最少交换次数。因为只有三种值所以最终的排序结果只有六个分区块你要做的是把“本该在1区的2”和“本该在2区的1”这种跨区错位配对统计出来再算剩余循环交换的最小代价。这类题的训练价值是让你意识到排序算法本身是一回事针对数据特征的特殊排序策略是另一回事没有一种排序能覆盖所有问题场景。礼盒排序那道题我在实际环境里没跑过但从题面“时间限制1000ms内存限制65536KB”和“提交数25”可以看出它也是一道经典的组合优化类排序题大概率不是让你实现某个标准排序算法而是需要分析题目给定的排序规则找出规律后用O(n)或者O(nlogn)的方法解决。5.4 我的排序调试三板斧最后分享三个我在实际工作里屡试不爽的调试技巧尤其适合排序算法学习和业务代码排错。第一写一个“验证排序正确性”的小函数。排序完成后遍历数组确认arr[i] arr[i1]对全数组成立。听起来简单但大多数排序bug都能靠这一条抓住。这个验证函数要和应用逻辑解耦单独放一个测试文件里每次改完排序就跑去跑一遍相关测试。第二用小规模数据手工模拟。把数组缩到5到7个元素包括重复值、倒序、几乎有序三种输入程序每执行完一趟就打印数组状态。递归分治排序的问题会在“边界切分”和“区间越界”上暴露得非常清楚打印是最直接的定位手段。第三数据量不是“越大越容易发现问题”反而从小到大分级测试更有效。我一般分几档来做n10、n100、n10000、n1000000分别记录耗时和结果。这样既能定位小数据逻辑问题又能排查大数据下的超时和内存泄漏风险。如果某档数据量性能突变了再单独排查那一档对应的数据结构或递归深度问题。6. 这个专栏之后的扩展方向排序和复杂度分析这套东西说到底是基础中的基础但延伸出来的方向非常多。我自己学完这块之后觉得最值得往下深入的是几个点一是把“比较排序”和“非比较排序”放在一起学习比如计数排序、基数排序和桶排序它们能把复杂度降到O(nk)但前提是数据分布要满足某些条件二是去研究一下TimSort和双轴快排这些工业级排序器看它们如何融合多种基础排序这比单独默写某种算法更能提升对系统的理解三是把排序思维迁移到其他经典问题上比如合并区间、求逆序对、求数组中的第K大这些问题的核心其实都是排序或者“类排序”的思维。我觉得排序最迷人的地方就在这里表面看是“把元素排好序”这一个简单需求背后却藏着复杂度分析、工程选型、稳定性权衡、大数据思维这么多层东西。把这些层次全部穿起来排序这块才真正算学透了。