★ FEATURED ARTICLE 排序算法大概是每个程序员最早接触、也最容易被问“懂没懂”的一大类基础题。我刚工作那会儿面试官让我手写快速排序写完还追问了一句“如果数据里全是重复元素你的写法会退化吗”当时我愣了一下后来实际调过性能才发现这个问题问得一点都不多余。排序算法背下来很容易但真到了项目里根据数据特征、内存限制、稳定性要求去选对算法、写对边界、调出性能又是另一回事。这篇文章把冒泡、选择、插入、归并、快速、堆、计数、基数、桶排序这几种常用算法放在一起从“它们到底在解决什么问题”讲起把每种算法的核心思想、实现要点、适用边界和实际项目中容易踩的坑都过一遍。适合正在复习算法的学生准备面试的开发者以及要在项目里处理数据排序、正在纠结选型的工程师。排序的应用面不用多讲数据库索引维护、排行榜计算、搜索结果的排序输出、数据分析前的预处理处处都有它。很多人学完就忘是因为只背了代码没理解每种算法背后的“性能账”和“场景账”。这篇文章想把这笔账一起算清楚。1. 先搞清一个前提没有完美的排序算法1.1 排序问题本质上是“搬数据”的效率问题很多人有个误解觉得排序就是“把数字从小到大排一遍”只要结果对就行。但实际工程里排序消耗的不只是时间还有内存、缓存命中率、交换次数、稳定性以及递归栈的深度。一个排序算法在生产环境里跑得慢往往不是“比较大小”本身慢而是数据搬移的次数太多或者内存分配太频繁。举个例子如果排序的对象是简单的整数数组那么复制一个元素的开销很小快排的指针交换方案几乎无敌。但如果排序对象是一条条包含几十个字段的结构体记录交换一次要拷贝一大块内存这时候交换次数最少的算法就可能反超。我做过一次模拟测试对100万条记录按某个字段排序用“交换次数极多的鸡尾酒排序”内存分配开销极大换成“交换次数最少的堆排序”后耗时下降了近一半。这个经验让我意识到分析算法时不能只盯着大O复杂度要连数据的“搬运成本”一起算。所以学习排序算法的关键不是记住“哪个是O(n log n)”而是建立一套独立的判断框架数据规模多大、元素是否可随机访问、内存够不够、要不要稳定排序、数据本身是不是基本有序。带着这些前提去选算法才是真实项目里的思考方式。注意网上的时间复杂度表格只是理论值。实际性能受数据规模、元素大小、缓存友好度、编译器优化影响很大最终选型一定要结合自己的业务数据做基准测试。1.2 用三个维度给算法分类比背复杂度更实用我习惯把常用排序算法按三个维度分成几个抽屉需要的时候直接对应拉取。第一个维度是“比较类/非比较类”。比较类算法依靠元素之间的“大于/小于”关系做判断比如快排、归并、堆非比较类算法利用元素本身的取值结构直接放置比如计数排序、基数排序、桶排序。非比较类通常快但对数据范围或分布有严格要求泛用性差。第二个维度是“稳定/不稳定”。稳定排序能保持相等元素的原始相对顺序。这个需求在业务里特别常见比如先按销量排序再把销量相同的记录按上架时间保持原来的先后顺序这时候必须用稳定排序。归并排序就是最常见的稳定排序代表快排和堆排序实现不好就很容易破坏稳定性。第三个维度是“原地/非原地”。原地排序只需要常量级额外空间比如快排、堆排非原地排序需要临时的额外数组或容器比如归并排序需要O(n)的辅助空间。内存受限的嵌入式环境、超大文件的外部排序场景对空间的要求往往比时间更苛刻。有了这三个维度分析一个排序算法的优劣就有了框架。接下来逐个看具体算法时我也都会带着维度标签来聊方便对比。维度类别典型算法一句话特点比较方式比较类快排、归并、堆排通用性强靠比较决定顺序比较方式非比较类计数、基数、桶排利用取值分布速度快但有条件稳定性稳定冒泡、插入、归并保持相等元素原顺序稳定性不稳定选择、快排、堆排可能改变相等元素顺序空间原地冒泡、选择、插入、堆排额外空间O(1)空间非原地归并、计数、基数需要额外数组或容器2. 入门三件套冒泡、选择、插入2.1 冒泡排序教学意义大于实战意义冒泡排序的思路非常直观相邻两个元素比较反序就交换每一轮把当前未排序部分的最大值“冒”到末尾。代码如下def bubble_sort(arr): n len(arr) for i in range(n): swapped False for j in range(n - i - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break return arr我写冒泡时一定会加一个swapped标志位。这个优化很基础作用是如果某一轮从头到尾没有发生交换说明数组已经有序直接终止。对“基本有序”的数据这个优化能让最好情况复杂度降到O(n)。但要说实战冒泡排序确实不推荐。它的平均和最坏时间复杂度都是O(n²)比较和交换次数都很多。即使加了提前终止它对乱序数据也不够看。我见过一些初级工程师在数据量只有几千时用它勉强能跑一旦数据量到了几十万立刻卡到怀疑人生。不过别急着否定它。冒泡排序在“水果排队”这种解释场景里特别合适因为它每一步操作都和学生脑子里对排序的直觉一致。教学价值很高面试里也偶尔会要求写出来考察基础。我的建议是理解即可不必在生产代码里用。2.2 选择排序交换次数最少但比较次数不减选择排序的做法是每一轮从待排序区间选出最小元素和当前区间第一个元素交换。为什么说它“交换次数最少”因为每一轮最多只做一次交换整体交换次数是O(n)而冒泡排序的交换次数是O(n²)。如果元素的复制/交换成本非常高选择排序在某些场景是有价值的。def selection_sort(arr): n len(arr) for i in range(n): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i] return arr但它的比较次数固定是O(n²)不管数据是否有序都要扫描完全部待排序区间。而且它不稳定比如数组[5a, 8, 5b, 1]第一轮找到最小的1和下标0的5a交换两个5的相对顺序就变了。业务里的稳定排序需求选择排序直接出局。实际中选择排序还有一个小变种叫“双向选择排序”同时维护头部的最小值和尾部的最大值能把时间复杂度常数项减少大约一半。我在一次数据量很小的嵌入式场景里用过省内存、代码简单效果意外不错。但常规开发中选择排序同样更多是教学和面试用途。2.3 插入排序别小看它实战中的“替补王牌”插入排序的思路是把数组看成“已排序部分”和“未排序部分”每次从未排序部分取出一个元素在已排序部分从后往前找位置插入。它很像玩扑克牌时整理手牌的动作。def insertion_sort(arr): for i in range(1, len(arr)): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key return arr插入排序有两个非常大的优点。第一对“近似有序”的数据最好情况复杂度是O(n)几乎可以跳过大部分移动。第二它是稳定的。这两个性质让插入排序在工程里成了“高效的兜底角色”。我举两个实际场景。一个场景是“小数据量排序”数据量在20以内时插入排序往往比快排还快因为快排的递归开销和分区逻辑在小规模数据上是纯浪费。很多工业级排序库的处理方式就是如果待排序区间长度小于某个阈值就改用插入排序来收尾。比如Android和Java的排序库里都有类似的实现。另一个场景是“在线排序”比如实时接收用户行为数据、需要维护一个始终有序的列表。新数据到来时大多数情况下只需要插到末尾或接近末尾的位置插入排序几乎就是为这种场景设计的。我用它维护过一个小型的实时排行榜数据量不大效果非常稳定。实操心得如果只是自己写工具脚本面对几乎有序或小规模数据完全可以直接用插入排序没必要上快排。写起来简单还不容易有递归崩溃的风险。3. 进阶主力归并、快排、堆排3.1 归并排序稳定的代价是吃内存归并排序是典型的分治思想把数组从中间切成两半分别排序再把两个有序子数组合并成一个有序数组。它的时间复杂度稳定在O(n log n)不受数据分布影响而且是稳定的。def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result上面的写法最直观但我在实际中会做两个改造第一不采用切片拆分数组而是用传入左右边界的下标方式减少切片带来的内存复制第二复用一份临时数组做合并避免每一层递归都申请新数组。这样改造后空间复杂度仍然是O(n)但常数项会小很多。归并排序最典型的工程应用是外部排序。当数据大到无法全部加载到内存时可以把大文件切分成多个小分块逐块排序后写入磁盘再对这些有序分块做多路归并。这也是很多数据库做排序时背后的思想。不过要注意归并排序需要O(n)的辅助空间这在内存紧张的环境里是个问题。另外它对缓存并不完全友好合并时会把数据在两个区间来回搬动。我在某次处理超大数组时归并排序耗内存明显高于快排最后为了内存稳定换成了原地排序方案。3.2 快速排序最流行却最容易写错快速排序也是分治思想但它和归并有个本质区别快排是“先分区再递归”并且在分区时就把元素放到了相对正确的位置上不需要合并步骤。核心是partition分区过程选一个基准值pivot把小于等于基准的放左边大于基准的放右边返回基准最终的下标。def quick_sort(arr, low, high): if low high: pi partition(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi 1, high) def partition(arr, low, high): pivot arr[high] # 简单起见取最后一个元素 i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1快排的难点在于基准值的选择。最理想的情况是每次分区都让左右两边差不多长时间复杂度保持在O(n log n)。但如果数据已经有序我上面的写法每次取最后一个元素做基准分区就极度不平衡时间复杂度直接退化成O(n²)。这就是面试官问“重复元素和数据有序时会怎样”的由来。解决退化问题的常用手段有三个随机选基准每次在[low, high]中随机挑一个下标降低最坏情况出现的概率。三数取中取low、mid、high三个位置的中间值作为基准对基本有序的数据效果很好。三路分区把数组分成小于、等于、大于基准的三个区间处理大量重复元素时能避免重复比较和交换。我在实际项目中用的是“随机选基准小数据插入排序收尾三路分区”的组合。实测下来对包含大量重复记录的日志数据、几百万量级表现比普通快排稳定很多也没有出现明显退化。另一个容易忽略的问题是递归深度。最坏情况下快排递归深度O(n)会导致栈溢出。很多语言对函数递归深度有限制数据量大时不一定是因为算法慢崩掉的而是栈先撑不住了。工程实现里会采用“尾递归优化”或“循环手动栈”来规避。3.3 堆排序性能稳定但稳定性一般堆排序利用二叉堆这种数据结构来排序。第一阶段把数组调整成最大堆第二阶段不断取出堆顶最大值和堆末尾元素交换再把剩余部分重新调整成堆。这样每次取最大值的复杂度是O(log n)总共n次总复杂度O(n log n)。def heap_sort(arr): n len(arr) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) for i in range(n - 1, 0, -1): arr[i], arr[0] arr[0], arr[i] heapify(arr, i, 0) def heapify(arr, n, i): largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right if largest ! i: arr[i], arr[largest] arr[largest], arr[i] heapify(arr, n, largest)堆排序最大的优势是“原地最坏情况O(n log n)”。它不需要快排那样担心分区不平衡导致退化也不像归并那样需要额外O(n)内存。对时间性能要求苛刻、内存又紧张的场景比如嵌入式系统或实时系统的优先级队列堆排是很稳的选择。但堆排序有两个天然短板。第一它不稳定相等元素的相对顺序可能会在交换过程中被破坏。第二它的实际常数项偏大因为缓存命中率不高堆的下滤操作会在大范围跳跃访问元素导致某些数据规模下它反而比快排慢。我在实践中对堆排序的定位是“稳定性能的兜底者”。当我不想为快排放心退化问题又不能接受归并的额外内存时就用堆排。它的运行时间比较可预测没有意外。注意堆排序适合“始终维护前K个最大/最小元素”这类场景比如Top K问题。直接对整个数组做排序反而优势不大。用堆做Top K复杂度是O(n log K)。4. 特殊场景计数、基数与桶排4.1 计数排序数据范围小时威力巨大计数排序属于非比较类排序。它的前提是知道数据的最小值和最大值的范围然后直接开一个长度等于范围的计数数组统计每个值出现的次数最后按顺序输出。def counting_sort(arr): if not arr: return arr min_val, max_val min(arr), max(arr) count [0] * (max_val - min_val 1) for x in arr: count[x - min_val] 1 result [] for i, c in enumerate(count): result.extend([i min_val] * c) return result在数据范围比较小、数据量比较大的情况下比如给0到1000之间的100万个整数排序计数排序的时间复杂度是O(n k)这里的k是数据范围。它甚至比O(n log n)的比较类算法快很多因为它完全不比较元素大小。但计数排序有两个限制。第一数据必须是“可索引”的整数或者能够映射成有限范围的整数。第二数据范围如果太大比如0到2^31之间的数字即使只有几十个数计数数组也会爆内存。另一个坑是我自己写的简化版本不是稳定排序但在工程实现中只要在统计后用“前缀和反向遍历”的方式放置元素计数排序就可以保证稳定性。这也是基数排序的基础。4.2 基数排序从低位开始逐位整理基数排序是“多次计数排序”的组合。把数字按位切分先按最低位排再按次低位排一直到最高位。因为计数排序是稳定的所以每一轮排序后数字在高位相等时低位的相对顺序仍然保留。举个例子排序三位数时先按个位排序再按十位排序最后按百位排序。每一轮都用稳定排序做内部整理最终所有数字就能按从小到大的顺序排好。基数排序的时间复杂度是O(d × (n k))d是位数。对固定位数的整数、字符串等数据它很可能比快排还快。我在处理“12位商品编号排序”之类固定格式数据时用过效果很好。不过它要求数据能被拆分成若干“位”并且每位都能映射到有限范围。对浮点数、复杂结构体的直接排序基数排序应用起来要麻烦得多。实际使用时还要注意字节序和内存占用问题因为每一轮都可能要用额外的计数数组和临时输出数组。4.3 桶排序均匀分布场景的高性能选择桶排序的思路是把数据按值域范围分到若干个“桶”里每个桶内部再用其他排序算法排序最后按桶顺序依次取出合并。它的平均时间复杂度接近O(n)但如果数据分布不均匀大量数据挤到少数几个桶里效率就会退化甚至比快排还差。def bucket_sort(arr, bucket_count10): if not arr: return arr min_val, max_val min(arr), max(arr) bucket_size (max_val - min_val) / bucket_count buckets [[] for _ in range(bucket_count)] for x in arr: idx min(int((x - min_val) / bucket_size), bucket_count - 1) buckets[idx].append(x) result [] for b in buckets: if b: b.sort() # 对内层使用内置排序 result.extend(b) return result桶排序特别适合“数据在某个范围内大致均匀分布”的场景比如对一组分布在[0, 100)之间的随机浮点数排序。我在线性插值计算和统计绘图的数据预处理里用过它均匀数据下速度确实快。需要注意桶的数量怎么定。桶太少单个桶内部数据多内层排序压力大桶太多创建桶和合并的空转开销也大。一般经验是桶数量取“数据量的平方根”左右再结合数据分布微调。如果数据极度偏斜比如大多数数据集中在一个很窄的值域里桶排序不如直接用快排。5. 实战选型面对不同数据怎么选算法5.1 没有最佳算法只有最合适的组合做工程最忌讳的是“手里一把锤子看所有数据都是钉子”。我刚入行时总爱什么都用快排后来遇到一些特殊场景才明白排序选型要看几个关键条件。第一看数据量。数据量很小时O(n²)算法反而有优势。比如十个八个数直接用插入排序比折腾快排分区还快。数据量超大时O(n log n)是基本要求甚至要考虑外部排序。第二看内存限制。内存紧张时排除归并排序和基数排序优先考虑原地排序。我自己在嵌入式环境里排过数据堆排序是最稳妥的选择之一。第三看稳定性需求。如果数据要在多次排序之间保持原有相对顺序必须使用稳定排序。归并排序是首选如果不想吃内存可以在实现细节上下功夫。第四看数据本身的特征。已经基本有序的数据插入排序最好用重复元素特别多三路快排和计数排序有优势数据范围很小的整数计数排序和基数排序完胜。实际项目里的数据往往有自己的规律不要只看“平均情况”。5.2 工程实现里的通用优化除了算法层面的选型我在工程代码里还总结了几条通用的优化经验。一是“混合排序”。工程上很流行的策略是大规模数据用快排或归并当递归到小区间时切换成插入排序。这个阈值一般在8到20之间。具体多少最合适最好在不同机器上跑基准测试不要照搬别人的数。二是“避免递归带来的栈风险”。某些场景下普通快排的递归深度可能很深。可以把递归调用改成显式栈或者用尾递归优化。不少语言的编译器和运行时对递归有深度限制数据量达到十万级时就要小心了。三是“尽量减少元素搬移”。如果排序对象是结构体或对象交换整个元素很昂贵。可以考虑先创建一个下标数组对下标排序再按最终下标顺序重新排列数据。这在数据库系统中很常见。四是“利用局部性原理”。相对连续访问内存的算法往往比跳跃访问的算法更高效。归并排序和插入排序对缓存相对友好堆排序在这一点上较差。性能优先的实时场景我一般优先考虑缓存友好的算法。6. 常见实现错误与调试经验6.1 越界、死循环、稳定性丢失是排序代码的三座大山排序算法代码看起来短但坑非常多。我给人评审代码时见得多的问题主要集中在这几类。第一类是数组越界。比如快速排序的partition中双指针移动时没有严格限制边界堆排序中左右孩子下标的计算超出了当前堆的有效范围。这种问题在单机上可能偶发但换了边界输入就会复现。我的经验是每个数组访问前先心算一遍下标是否是有效的“0到当前长度-1”。第二类是死循环。典型场景是快排的三路分区中左右指针遇到等于基准值时没有正确移动导致循环卡死。还有人写二分插入排序时如果数据全相等某些写法会在while循环里打转。调试办法很简单给循环加计数器一旦超过数组长度就立刻抛异常能快速暴露问题。第三类是稳定性丢失。很多人写归并排序时在合并阶段用了小于等于号这没问题但如果在两个子数组相等时先取了右边的元素稳定性就破坏了。这种错误在功能上几乎看不出来只有对比原数据相对顺序的测试用例才能发现。6.2 用断言、日志和随机测试来验证排序我调试排序代码时会用一套标准流程。首先是最简单的“结果正确性检查”排序后数组单调不减长度不变元素内容不变。这一条只验证了基本结论远远不够。其次做“稳定性检查”给每个元素加一个序号字段比如用元组(值, 序号)排序后检查值相同的元素序号是否保持相对顺序。这样就可以自动发现稳定排序被破坏的问题人工肉眼很难发现。然后是“随机压力测试”用固定种子生成大量随机数组再和高可信度的内置排序结果对比。这个流程我用过很多次能快速发现边界相关问题。测试时一定要覆盖空数组、单元素数组、全部相等的数据、已经有序的数据、逆序数据、大量重复数据、超大数值的数据。对于性能退化类问题我会在分区或比较函数里加日志统计递归深度、比较次数、交换次数。比如快排如果出现“比较次数远超 n log n”的情况基本可以推断分区严重失衡基准选择出了问题。6.3 我总结的几条实用心得我在多次项目中积累了一些比教案更“接地气”的心得。第一内置排序往往是首选。大多数现代语言的内置排序比如Python的Timsort、Java的DualPivotQuicksort都是经过高度优化的混合算法性能和稳定性都远超自己手写的版本。自己写排序算法前先想清楚是不是真的有必要。业务代码里直接调用内置排序是最可靠的方案。第二如果必须手写就选“心智负担最小”的算法。项目里手写排序多半是为了特殊的稳定性、懒惰排序或自定义比较器。这时我宁愿多花一点常数时间也要选择逻辑简单、不容易写错的算法因为可维护性比微小的性能优势更值钱。第三排序算法的基础思想会迁移到其他领域。比如堆排序中的堆调整思想可以用于优先队列归并排序的合并思想可以用于两有序链表的合并快排的分区思想可以用于求Top K或找中位数。学习这些算法时多想想它们的抽象结构收益远不止“会排序”本身。第四性能分析一定要基于真实的业务数据。理论复杂度只是在无限规模下的渐进趋势。我曾见过一个项目用计数排序给订单编号排序理论上快得飞起实际上订单编号跨度太大开了一个巨大的计数数组性能反而很差最后换了基数排序才解决问题。数据和场景不同结论可以完全不同。排序算法这个主题看似基础实际越用越有内容。我个人的体会是不要在代码里堆砌算法而是要建立“数据特征→约束条件→算法选择→工程优化→测试验证”的完整链路。多写几次、多Benchmark几轮你对排序的感觉会从“背代码”变成“真正会选、会用”。
阅读完成 · 觉得有帮助？
