前几天帮朋友准备面试他问我为什么面试官总喜欢问排序算法我的回答是排序算法看起来基础但它的分类维度、底层实现、时间空间复杂度、稳定性任何一个细节都能反映一个人的计算机基础是否扎实。我见过太多候选人能熟练背出快速排序的代码但追问一句“为什么有些排序是稳定的有些却不是”就卡壳了。这篇东西我就想系统地聊聊排序算法的分类和实现把自己这些年手写排序、看标准库源码、调优工程排序的经验都放进来。如果你正在准备算法面试或者工作中需要自己实现排序逻辑又或者只是想弄清楚sort()背后到底发生了什么这篇文章应该能给你一个比较完整的答案。排序算法的东西网上很多但大多是零散的知识点。我这里想换一种讲法先给一个能覆盖到所有排序算法的分类框架然后逐个教你怎么实现并说清楚每个实现里最容易踩的坑最后落到工程选型上讲讲到底什么时候该用哪种排序以及怎么验证自己写的排序是对的。1. 排序算法的核心分类标准不止是时间复杂度的差别1.1 比较排序与非比较排序是最大的一刀排序算法最常见的分类方法是“基于比较”和“不基于比较”。基于比较的排序通过比较元素之间的大小关系来决定顺序例如冒泡排序、快速排序、归并排序。这类排序有普适性几乎可以处理任何可比较的数据类型但有一个理论下限基于比较的排序在最坏情况下时间复杂度不可能低于 O(n log n)这个结论在算法导论里有严格证明核心原因是比较过程可以用决策树建模叶子结点的数量是 n!树的高度自然就是 log(n!) ~ O(n log n)。非比较排序不走这个路线它不是靠比较大小而是利用数据的本身特性比如数据范围有限、数据分布均匀或者数据可以按位拆开。典型的有计数排序、桶排序、基数排序。它们的理想时间复杂度可以达到 O(n k)k 是数据范围或者桶的个数。但代价是适用范围窄比如计数排序要求数据是非负整数且范围不能太大基数排序需要对元素的可分解性有额外要求。所以非比较排序不是万能的但在特定场景下它比快排还要快一个量级。1.2 稳定性、原地性、自适应性三个很多人忽略的分类维度除了比较/非比较我认为还有三个维度在实际工程中比时间复杂度更值得关注稳定性指排序后相等元素的相对顺序是否保持不变。稳定的排序有插入、冒泡、归并、基数典型不稳定的有选择、快排、堆排。为什么稳定性重要举个例子你想先按年龄排序再按姓名排序如果第二次排序是稳定的那么相同姓名的人年龄顺序仍然保持着第一次排序后的结果。在很多多级排序、数据库排序的场景里稳定性是硬需求。原地性in-place指排序时是否只需要 O(1) 的额外空间。堆排序是原地排序的典型归并排序需要 O(n) 的临时数组快排虽然原地重排元素但由于递归需要栈空间平均 O(log n)最坏 O(n)。自适应性指算法能否利用数据中已经有序的部分减少工作量。插入排序和冒泡排序的优化版都有这个特性当输入几乎有序时它们能很快完成排序。这也是为什么 Timsort 会把“利用有序子序列”作为核心设计思想。把这些维度汇总成一个表会更直观算法平均时间复杂度最坏时间复杂度空间复杂度稳定性原地性典型实现方式冒泡排序O(n²)O(n²)O(1)稳定是相邻交换选择排序O(n²)O(n²)O(1)不稳定是找最小/最大交换插入排序O(n²)O(n²)O(1)稳定是插入到合适位置希尔排序O(n log n) ~ O(n^1.5)O(n²)O(1)不稳定是分组插入归并排序O(n log n)O(n log n)O(n)稳定否分治合并堆排序O(n log n)O(n log n)O(1)不稳定是二叉堆调整快速排序O(n log n)O(n²)O(log n)~O(n)不稳定是划分递归计数排序O(nk)O(nk)O(k)稳定否计数后回填桶排序O(nk)O(n²)O(nk)稳定否分桶后排序基数排序O(d(nk))O(d(nk))O(nk)稳定否按位计数排序这个表列出来之后你会发现很多排序算法之间的差别其实是一层层叠加的。工程上挑算法本质就是在这几个维度之间做权衡。我在后面的实现和选型部分会反复回到这张表。2. 比较排序的核心实现与易错点逐个拆解2.1 冒泡、选择、插入三种 O(n²) 排序里谁值得留到生产环境先看最简单的三个。冒泡排序的实现逻辑就是把相邻元素中较大的那个一路“冒”到末尾每轮都让至少一个元素落在最终位置。我写一份带优化标志的版本def bubble_sort(arr): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: # 某一轮没有发生交换说明已经有序 break这个优化很关键如果输入已经有序第一轮扫描会发现swapped为False直接退出时间复杂度退化成 O(n)这就是它的自适应能力。但要注意冒泡排序的交换次数贼多平均情况下它的常数因子很大实际很少用。选择排序的思路是每轮在未排序部分找最小值和当前开头位置交换。代码很简单def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j arr[i], arr[min_idx] arr[min_idx], arr[i]很多人误以为选择排序是稳定的其实不是。考虑数组[5, 5, 2]第一轮找到最小值 2和第一个 5 交换结果变成[2, 5, 5]两个 5 的相对顺序不变因为它们是相邻的所以这里看不出问题。但如果你用[3, 3, 1]还是看不出。真正的问题场景是[2, 2, 1]这种也不明显。实际上选择排序的不稳定性出现在类似[3, 1, 3]这样的输入第一轮把 1 和第一个 3 交换变成[1, 3, 3]两个 3 的顺序没变化因为第二个3本来就在后面。再想一个场景[3A, 2, 3B]最小元素是2把它和第一个3A交换得到[2, 3A, 3B]也没有破坏。真正会破坏稳定性的情况是当有多个最小元素时选择一个立即交换可能把靠后的最小元素换到前面比如[3A, 2B, 1C, 2D]第一轮找最小值1C和第一个元素3A交换得到[1C, 2B, 3A, 2D]此时两个2的相对顺序是2B在2D前面没问题。但如果第一轮我们把最小值1C和它本来前面的元素交换之后第二轮继续在剩余部分找2此时剩余部分是[2B, 3A, 2D]找到最小元素2B和第二个位置交换但其实2B已经在第二个位置所以不变。所以单纯的直接选择排序在很多情况下看起来是稳定的但严格证明它不稳定原因在于交换操作可能是远距离交换把相同元素的相对顺序打乱。一个经典例子是[5, 8, 5, 2, 9]第一轮最小值2和第一个5交换得到[2, 8, 5, 5, 9]此时两个5的相对顺序颠倒了原来的第二个5现在在第三个位置原来的第一个5现在在第四个位置。所以结论是选择排序不稳定。你记住这个例子就可以文章后面讲稳定性测试时会验证。插入排序的思路则是维护一个有序前缀每次把当前元素插入到前面已排序部分的合适位置。这个算法我建议每个程序员都能熟练到闭眼默写因为很多高级排序算法在数据量小的时候都会回落成插入排序比如 C STL 中的std::sort在快排递归到小区间时就会切换到插入排序。代码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插入排序的核心理念是“整体移动元素”而不是反复交换。它同样是稳定的自适应性强最坏 O(n²) 但最好 O(n)。在生产环境里几十个元素的数组直接用它往往比快排还快因为快排递归压栈的开销在很小的数据量面前不划算。2.2 希尔排序让插入排序跨着大步跳希尔排序是对插入排序的改进。它先按一个增量序列把数组分成若干小组组内做插入排序然后逐步缩小增量最后为1时就是普通插入排序。这个思路的精髓是前几轮排序让数组变得“大致有序”最后一轮插入排序就快多了。用 Python 写一个简单版本def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): temp arr[i] j i while j gap and arr[j - gap] temp: arr[j] arr[j - gap] j - gap arr[j] temp gap // 2这里使用的是希尔增量不断对半实际还有 Hibbard 增量序列1, 3, 7, ...和 Sedgewick 增量序列它们的性能差异很大。希尔排序的时间复杂度分析非常复杂平均情况大概是 O(n^1.5) 左右最坏根据增量序列不同可以达到 O(n²)。它的稳定性是不行的因为分组排序会跨越很远的距离交换元素相等元素可能被换到不同小组。所以如果算法明确要求稳定不要选希尔排序。2.3 归并排序稳定、可预测但空间没那么“免费”归并排序采用分治策略把数组对半拆开分别排序再合并两个有序数组。递归版写起来非常直观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): i, j 0, 0 res [] 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这个实现最清晰但每次递归都创建新数组空间开销非常大。工程上写归并排序一般会用一个与原数组等长的临时数组对不同区间复用。关键在于merge时如果遇到left[i] right[j]就取左侧这样才能保证稳定性。如果写成那么相同元素会优先取右侧稳定性就没了。归并排序的最大优点是它完全不受输入数据初始顺序的影响任何情况下的最坏复杂度都是 O(n log n)而且稳定这一点让它在很多数据库外部排序、Java 对象排序中占据重要位置。缺点也很明确不是原地排序额外空间 O(n)。对于内存紧凑型系统这可能是个决定性的劣势。2.4 堆排序不需要递归但堆化容易写错堆排序是三个 O(n log n) 算法里唯一一个原地、最坏复杂度也是 O(n log n) 的。它分为两步先建堆通常是最大堆再循环把堆顶元素和末尾元素交换缩小堆范围后做堆化调整。这里最容易写错的是sift_down的边界条件我给出一个经过多次验证的版本def heap_sort(arr): n len(arr) # 建堆从最后一个非叶子节点开始向上调整 for i in range(n // 2 - 1, -1, -1): sift_down(arr, i, n - 1) # 逐个将堆顶最大值移到末尾 for end in range(n - 1, 0, -1): arr[0], arr[end] arr[end], arr[0] sift_down(arr, 0, end - 1) def sift_down(arr, start, end): root start while 2 * root 1 end: child 2 * root 1 if child 1 end and arr[child] arr[child 1]: child 1 if arr[root] arr[child]: arr[root], arr[child] arr[child], arr[root] root child else: break注意sift_down中的参数end表示当前堆的最后一个索引不是堆的大小。当交换堆顶和末尾后end要减 1这样被交换到末尾的最大元素就不参与后续调整了。很多人第一次写堆排序时会把end写成堆大小导致越界或者调整范围错误。堆排序的不稳定性体现在交换堆顶时会破坏相等元素顺序这也是堆排序无法被用于需要稳定排序场景的原因。2.5 快速排序平均最快但别让最坏情况杀死你快排是出场率最高的排序算法也是面试最容易问的。它的思路是选一个基准值pivot把数组划分成小于基准和大于基准两部分然后递归排序左右子区间。我通常用这个实现def quick_sort(arr, left, right): if left right: return pivot_index partition(arr, left, right) quick_sort(arr, left, pivot_index - 1) quick_sort(arr, pivot_index 1, right) def partition(arr, left, right): pivot arr[right] # 简单选最右元素做基准 store left for i in range(left, right): if arr[i] pivot: arr[store], arr[i] arr[i], arr[store] store 1 arr[store], arr[right] arr[right], arr[store] return store这是 Lomuto 划分法代码短但实际工程更喜欢 Hoare 划分法因为 Hoare 的常数更小且交换次数少。std::sort内部使用的就是类似 Hoare 划分。不过 Lomuto 理解起来简单面试能写出来已经不错了。快排的平均时间复杂度 O(n log n)但最坏会退化到 O(n²)根因就是每次选的基准都是当前区间的最小或最大值划分极其不平衡。解决思路有三个随机选基准、取首中尾三元素的中位数、或者在递归深度超过某个阈值时改用堆排序这就是 C 内省排序 introsort 的做法。快排不稳定这个应该很好理解在划分过程中 pivot的元素会被移来移去相同元素的顺序很容易被打破。我在调试快排时踩过一个非常隐蔽的坑使用 Lomuto 划分时如果arr里有很多重复元素比如全一样的数字那么arr[i] pivot会把所有元素除了最后一个都划到左边导致store一路走到right递归深度会到 n直接栈溢出。所以工程实现中通常会加上三路快排把等于 pivot 的元素单独放中间或者对重复元素做特殊处理。如果你面试时被问到“数组里有大量重复元素怎么办”答案就是三路快排。3. 非比较排序当数据条件满足时它们快到不合常理3.1 计数排序利用数据范围完成线性排序计数排序要求输入是非负整数并且最大值相对可控。它的做法是统计每个数值出现的次数然后根据次数计算出每个值应该放的下标范围再回填数组。为了保证稳定性回填时要倒序遍历原数组。代码def counting_sort(arr, max_val): n len(arr) counts [0] * (max_val 1) for v in arr: counts[v] 1 for i in range(1, max_val 1): counts[i] counts[i - 1] # 转换成前缀和 output [0] * n for v in reversed(arr): output[counts[v] - 1] v counts[v] - 1 arr[:] output这里前缀和的处理很关键。counts[i]表示小于等于 i 的元素个数倒序遍历原数组保证相同值的元素按照原顺序落位从而实现稳定性。如果没有稳定性需求也可以直接按值从小到大覆盖写法更简单但排序不会稳定。计数排序最怕遇到取值范围过大比如[100000000, 1, 2]计数数组就要开 100000001 个元素空间瞬间爆炸。碰到这种情况要么用哈希压缩要么换桶排序或基数排序。3.2 桶排序把数据分发到多个“小水桶”桶排序是计数排序的推广。它根据数据的分布区间把元素分到若干个桶里每个桶内部做排序一般用插入排序小数据量下最快也可以递归用快排最后按桶的顺序依次取出。例如要排序[0, 10)内的 100 个浮点数可以建 10 个桶每个桶存一个区间。实现大致如下def bucket_sort(arr, bucket_size5): if not arr: return arr min_val, max_val min(arr), max(arr) bucket_count (max_val - min_val) // bucket_size 1 buckets [[] for _ in range(bucket_count)] for v in arr: idx (v - min_val) // bucket_size buckets[idx].append(v) result [] for b in buckets: insertion_sort(b) result.extend(b) return result桶排序的平均复杂度是 O(n k)但最坏情况是所有元素都挤进同一个桶桶内排序退化成 O(n²)。因此在分桶时必须尽量让数据均匀分布。比如我们要排序均匀分布的随机数桶排序会展现出惊人的速度但如果数据集中在一个很窄的区间桶排序就会退化。我在实际处理日志时间戳时用过桶排序把一天内的请求按小时分桶再对每小时内的时间戳做插入排序效果非常好。3.3 基数排序按位熬出来的稳定排序基数排序的思路和计数排序是亲戚但它面对的是可以拆分成多个“位”的数据例如整数的个位、十位或者字符串的字符。常见的是最低位优先LSD先按个位桶排序再按十位桶排序直到最高位。因为计数排序是稳定的前面按低位排好的顺序会在后续高位排序中保持。一下是 LSD 排序的 Python 实现def radix_sort(arr): max_val max(arr) if arr else 0 exp 1 while max_val // exp 0: counting_sort_by_exp(arr, exp) exp * 10 def counting_sort_by_exp(arr, exp): n len(arr) counts [0] * 10 for v in arr: counts[(v // exp) % 10] 1 for i in range(1, 10): counts[i] counts[i - 1] output [0] * n for v in reversed(arr): digit (v // exp) % 10 output[counts[digit] - 1] v counts[digit] - 1 arr[:] output这里每次调用计数排序都是对某个“位”进行稳定排序。基数排序的时间复杂度是 O(d * (n k))d 是最大数字的位数。在数据位数较短时它比任何比较排序都快。但它只能处理有固定进制分解的数据对浮点数、对象数组不是那么方便除非人为构造出可分割的编码。非比较排序的共同点是空间换时间。它们都非常依赖数据本身的特征所以在通用排序库中你不会看到它们的身影但在数据库的专用排序节点、大数据分析框架里这类算法经常被用来做中间环节的排序优化。4. 工程实战标准库到底用的什么排序我们怎么选4.1 从sort()底层看工业级选型每个主流语言的标准库排序实现都不是一种算法打天下。比如 C 的std::sort用的是内省排序introsort它同时结合了快排、堆排序和插入排序开始用快排递归深度达到某个阈值通常是 2*log2(n)时改用堆排序来避免最坏情况在递归到小区间通常小于 16 个元素时改回插入排序。这一套组合拳保证了std::sort的最坏时间复杂度也是 O(n log n)而且常数很小。Java 对基本类型int[],double[]用的是双轴快排Dual-Pivot QuickSort因为基本类型不需要稳定性快排的性能优势最明显。对对象数组则用 Timsort这是归并排序和插入排序的混合体它会先扫描数据中已有的有序子序列称为 run然后用归并的方式把 run 合并起来。Timsort 充分利用了真实世界数据中常见的“部分有序”特性最坏 O(n log n)最好 O(n)而且稳定。Python 的list.sort()也使用 Timsort。所以你可以看到稳定性这个需求直接决定了底层排序的选择哪怕 Timsort 描述起来比快排复杂得多Java 依然心甘情愿地为对象排序承担这个复杂度因为对象排序中多级排序是常态不稳定的话后果会很严重。4.2 手写排序时怎么根据场景选如果今天需要你自己去实现一个排序我一般按下面的思路走数据量小于几十直接用插入排序。虽然理论上 O(n²)但常数极小没有递归栈开销实际比快排快。数据量较大、内存充足、要求稳定用归并排序。它是稳定且最坏 O(n log n) 的最佳平衡点。数据量较大、内存受限特殊嵌入式环境用堆排序。原地、最坏 O(n log n)但常数大实际速度不如快排。数据量较大、不要求稳定、甚至接受劣化概率用快速排序同时配合随机化基准。大多数通用场景首选。数据范围小、非负整数、可预知最大值用计数排序或者桶排序。数据可以按位拆分、位数固定用基数排序。但实际工程里有一个更隐晦的选型逻辑排序的稳定性有时候比你想象更重要。我维护过一个推荐系统后端需要按用户点击时间和物品优先级做两级排序。如果底层排序不稳定就会出现同一个物品以不同的相对顺序展示给用户导致线上行为分析异常。后来我把排序引擎从快排换成了稳定归并问题立刻消失。所以当你不确定是否需要稳定时默认优先选稳定排序总是更稳妥除非你明确知道不需要。4.3 多级排序的正确姿势在多级排序场景中稳定排序的价值体现得淋漓尽致。正确做法是先按次要字段排序再按主要字段排序。比如先排日期再排优先级因为稳定排序保证优先级相同的情况下日期顺序仍然是前一轮排序的结果。如果你被迫使用快排等不稳定排序就要自己处理复合比较逻辑把多个字段放在同一个比较器里。现代语言里这正是Comparator.thenComparing()之类的方法存在的原因。我建议你培养一个习惯手写排序时先问一句“我需不需要稳定性”而不是只问“快不快”。这个习惯能帮你避开大量隐性 bug。5. 我自己写的排序验证框架与几个反复踩坑后的经验5.1 如何保证排序实现是正确的排序代码写完不等于正确我写排序时一定会用测试来验证。下面是一个简单的随机排序测试脚本import random def test_sorter(sort_func, size1000, trials1000): for _ in range(trials): arr [random.randint(-1000, 1000) for _ in range(size)] expected sorted(arr) sort_func(arr) if arr ! expected: print(Mismatch!) print(arr) print(expected) return False return True测试时不要只测随机数据还要专门测边界情况空数组、单元素数组、逆序数组、所有元素都相等、极大极小值混合、甚至故意构造大量重复元素。在我自己踩坑的过程中大部分排序 bug 都不是在随机数据上爆发的而是在“全相等”或“逆序”时爆发。特别是快排的 Lomuto 划分在全相等数组上会直接退化到 O(n²)递归深度也爆炸。稳定性测试也很重要你可以通过包装对象来验证class Item: def __init__(self, key, tag): self.key key self.tag tag def __repr__(self): return f({self.key}, {self.tag}) def test_stability(sort_func): items [Item(1, a), Item(2, b), Item(2, c), Item(1, d)] sort_func(items, keylambda x: x.key) for t in [a, b, c, d]: # 检查相同 key 的 tag 顺序是否和最初一致 ...测试通过之后再谈性能。5.2 基准测试的坑不要忽略启动开销给排序做基准测试时最常见的误区是直接测小数组然后得出“某个排序速度差一点所以没用”的结论。正确的是准备多个规模梯度的数据每个规模测多轮取平均比如 100 轮并且注意在 Python 里避免用time.time()的精度不够用time.perf_counter()。还要注意 Python 的排序函数会对列表做原地排序所以每轮测试要拷贝一份原数组否则第二次测试时数组已经有序结果失真。以下是一个简单的基准测试模板import time, random def benchmark(sorter, arr): arr_copy arr[:] t0 time.perf_counter() sorter(arr_copy) t1 time.perf_counter() return t1 - t0 sizes [10, 100, 1000, 10000] for size in sizes: arr [random.randint(0, 10000) for _ in range(size)] print(fSize {size}: {benchmark(quick_sort, arr):.6f}s)在数据量 10000 左右快排通常比插入排序快上百倍但数据量小于 50 时插入排序可能比快排还要快。这也是标准库在小区间使用插入排序的原因。5.3 最容易让人抓狂的边界条件清单我根据自己多年经验整理了一个“排序算法边界自检清单”每次写完排序都要对照过一遍空数组任何排序都不应该报错。单元素不应该多此一举。逆序数组冒泡和插入会比较慢但逻辑必须正确。全等数组快排容易退化计数排序的max_val不能让数组越界。负数计数排序如果不做偏移处理就会出错。大整数基数排序要保证exp不超过整数范围。重复元素稳定性测试必须做很多边界 bug 都藏在重复里。另外如果用的是递归写法比如快排、归并一定要在测试中加大数组量比如 100 万看是否出现递归深度超限。Python 默认递归深度是 1000长排序数组很容易爆RecursionError。真要处理大数据我通常会把快排改成非递归版本或者直接用标准库。这也是为什么大厂面试有时候会让你手写非递归快排它考验的就是你对递归栈的理解。5.4 一个小技巧用断点或打印观察排序过程调试排序算法时如果测试不过但又看不出哪里错我会在原数组较小5~10 个元素的情况下在关键循环里print数组的状态。比如冒泡排序每轮结束打印一下就能看到第二轮的 j 范围是否还包含已排好的元素。这个方法虽然土但比脑内模拟强得多。我在调试归并排序时就是这么干的很快就发现合并时我用了而不是导致稳定性丢失。写到这里差不多把我能想到的关于排序算法分类和实现的经验都倒出来了。排序算法看着简单但每个实现里都有细节只有手写过一遍、测试过一遍、踩过坑才算真会。我的建议是不要只背代码最好自己建一个小文件夹把每种排序都实现一遍配上边界测试。以后面试也好工程上要写个特殊排序也好你都能稳稳拿出来。