常用排序算法全解析：原理、复杂度与工程选型实战

排序算法大概是每个程序员最早接触、也最容易被问“懂没懂”的一大类基础题。我刚工作那会儿，面试官让我手写快速排序，写完还追问了一句：“如果数据里全是重复元素，你的写法会退化吗？”当时我愣了一下，后来实际调过性能才发现，这个问题问得一点都不多余。排序算法背下来很容易，但真到了项目里，根据数据特征、内存限制、稳定性要求去选对算法、写对边界、调出性能，又是另一回事。

这篇文章把冒泡、选择、插入、归并、快速、堆、计数、基数、桶排序这几种常用算法放在一起，从“它们到底在解决什么问题”讲起，把每种算法的核心思想、实现要点、适用边界和实际项目中容易踩的坑都过一遍。适合正在复习算法的学生，准备面试的开发者，以及要在项目里处理数据排序、正在纠结选型的工程师。

排序的应用面不用多讲，数据库索引维护、排行榜计算、搜索结果的排序输出、数据分析前的预处理，处处都有它。很多人学完就忘，是因为只背了代码，没理解每种算法背后的“性能账”和“场景账”。这篇文章想把这笔账一起算清楚。

1. 先搞清一个前提：没有完美的排序算法

1.1 排序问题本质上是“搬数据”的效率问题

很多人有个误解，觉得排序就是“把数字从小到大排一遍”，只要结果对就行。但实际工程里，排序消耗的不只是时间，还有内存、缓存命中率、交换次数、稳定性，以及递归栈的深度。一个排序算法在生产环境里跑得慢，往往不是“比较大小”本身慢，而是数据搬移的次数太多，或者内存分配太频繁。

举个例子，如果排序的对象是简单的整数数组，那么复制一个元素的开销很小，快排的指针交换方案几乎无敌。但如果排序对象是一条条包含几十个字段的结构体记录，交换一次要拷贝一大块内存，这时候交换次数最少的算法就可能反超。我做过一次模拟测试，对100万条记录按某个字段排序，用“交换次数极多的鸡尾酒排序”内存分配开销极大，换成“交换次数最少的堆排序”后耗时下降了近一半。这个经验让我意识到，分析算法时不能只盯着大O复杂度，要连数据的“搬运成本”一起算。

所以，学习排序算法的关键不是记住“哪个是O(n log n)”，而是建立一套独立的判断框架：数据规模多大、元素是否可随机访问、内存够不够、要不要稳定排序、数据本身是不是基本有序。带着这些前提去选算法，才是真实项目里的思考方式。

注意：网上的时间复杂度表格只是理论值。实际性能受数据规模、元素大小、缓存友好度、编译器优化影响很大，最终选型一定要结合自己的业务数据做基准测试。

1.2 用三个维度给算法分类，比背复杂度更实用

我习惯把常用排序算法按三个维度分成几个抽屉，需要的时候直接对应拉取。

第一个维度是“比较类/非比较类”。比较类算法依靠元素之间的“大于/小于”关系做判断，比如快排、归并、堆；非比较类算法利用元素本身的取值结构直接放置，比如计数排序、基数排序、桶排序。非比较类通常快，但对数据范围或分布有严格要求，泛用性差。

第二个维度是“稳定/不稳定”。稳定排序能保持相等元素的原始相对顺序。这个需求在业务里特别常见，比如先按销量排序，再把销量相同的记录按上架时间保持原来的先后顺序，这时候必须用稳定排序。归并排序就是最常见的稳定排序代表；快排和堆排序实现不好就很容易破坏稳定性。

第三个维度是“原地/非原地”。原地排序只需要常量级额外空间，比如快排、堆排；非原地排序需要临时的额外数组或容器，比如归并排序需要O(n)的辅助空间。内存受限的嵌入式环境、超大文件的外部排序场景，对空间的要求往往比时间更苛刻。

有了这三个维度，分析一个排序算法的优劣就有了框架。接下来逐个看具体算法时，我也都会带着维度标签来聊，方便对比。

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_count=10): 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几轮，你对排序的感觉会从“背代码”变成“真正会选、会用”。