八种排序算法深度解析：从原理到实战场景选择指南

1. 为什么我要把排序算法重新梳理一遍

做开发这些年，排序算法这东西就像厨房里的盐——平时炒菜不一定想起来，但真到用的时候，手边没有或者用错了，整道菜就废了。我最初学排序是大二的数据结构课，那时候背代码、记复杂度，考试完就还给老师了。后来真正在工作中踩了坑，才发现当年根本没学明白。

举个真实的例子。有一次处理一批日志数据，大概几十万条，需要按时间戳排序后再做聚合。我随手写了个冒泡排序，跑了两分钟没出结果，CPU风扇狂转。换成快速排序后，不到一秒就完事了。那一刻我才意识到，排序算法的选择不是学术问题，是实打实的性能问题。

这篇笔记是我自己重新系统梳理排序算法的记录，不是教科书式的罗列，而是从“什么场景该用什么排序”这个角度出发，把常见的八种排序算法——冒泡、选择、插入、希尔、归并、快速、堆排序、计数排序——挨个拆开讲清楚。每种算法我会说清楚它的核心思路、代码实现、复杂度分析，以及最重要的：什么时候该用它，什么时候千万别碰它。

适合谁看？如果你正在学数据结构，这篇可以帮你把排序这块串起来；如果你已经工作但排序知识有点模糊了，这篇可以当速查手册；如果你面试前想突击复习，这里面的对比表格和常见坑点应该能帮上忙。我尽量说人话，少堆公式，多用类比和实际场景来解释。

2. 排序算法的整体分类与选择思路

2.1 先搞清楚排序算法的两大阵营

排序算法看起来五花八门，但本质上就分两大类：比较类排序和非比较类排序。

比较类排序就是通过元素之间的两两比较来决定顺序，比如冒泡、快排、归并这些。这类算法有个理论下限：时间复杂度不可能低于O(n log n)。你可以这么理解——n个元素有n!种排列可能，每次比较最多把可能性砍一半，所以至少需要log₂(n!)次比较，算出来就是n log n级别。

非比较类排序不依赖元素比较，而是利用元素本身的特性来排序，比如计数排序利用数值范围、基数排序利用位数。这类算法可以突破O(n log n)的下限，达到O(n)，但代价是适用范围窄，对数据有额外要求。

注意：面试时如果面试官问“最快的排序算法是什么”，别直接说快排。要先反问数据特征——如果是小范围整数，计数排序就是O(n)；如果是通用数据，那快排的平均性能最好。没有万能的最快，只有最合适。

2.2 稳定性：一个容易被忽略但很关键的属性

稳定性指的是：如果两个元素值相等，排序后它们的相对位置是否保持不变。比如[{name:"A", score:90}, {name:"B", score:90}]，按分数排序后，A是否还在B前面。

为什么这个重要？举个实际场景：你先按姓名排了一遍员工列表，现在要按部门再排一次。如果用的排序算法是稳定的，那么同部门内的员工仍然保持姓名有序；如果不稳定，同部门内的姓名顺序就乱了。这就是所谓的多级排序，稳定性能帮你省掉很多麻烦。

各算法的稳定性情况：

2.3 一张表看懂所有排序算法的核心指标

这张表建议存下来，面试前扫一眼就能回忆起关键信息。但光背表没用，下面我会逐个拆开讲，让你真正理解每个数字背后的原因。

3. 八种排序算法逐个拆解

3.1 冒泡排序：最直观但最不该用的排序

冒泡排序的思路特别符合直觉：从左到右，相邻两个元素比较，大的往后挪。一轮下来，最大的元素就像气泡一样浮到了最右边。重复n-1轮，整个数组就有序了。

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 return arr

那个swapped标记是必须加的。如果某一轮没有任何交换，说明数组已经有序了，直接退出。对于近乎有序的数据，冒泡排序能降到O(n)。但说实话，即使加了优化，冒泡排序在实际工作中也几乎用不到——它的比较次数太多了，每次只消除一个逆序对。

我唯一会推荐用冒泡的场景是教学。因为它足够简单，能帮初学者建立“排序就是消除逆序对”的直觉。实际项目中，哪怕数据只有几十条，我也会用插入排序而不是冒泡。

3.2 选择排序：交换次数最少的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] return arr

选择排序的特点是交换次数特别少，最多n-1次。如果交换元素的成本很高（比如元素是很大的结构体），选择排序反而有优势。但它的比较次数固定是n(n-1)/2，不管数据是否有序，这一点不如插入排序灵活。

实操心得：选择排序不稳定。举个例子[5, 5, 3]，第一轮会把第一个5和3交换，变成[3, 5, 5]，两个5的相对顺序就变了。如果你需要稳定性，别用选择排序。

3.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

插入排序在数据量小或者近乎有序时非常快。很多标准库的排序实现里，当子数组长度小于某个阈值（通常是7到16）时，就会切换到插入排序。比如Java的Arrays.sort和Python的Timsort都这么干。

为什么？因为插入排序的常数因子小，没有递归开销，对于小数组来说比快排和归并更快。而且它是稳定的，这在多级排序时很有用。

我实测过，对100条以内的数据，插入排序比快排还快。所以别看不起O(n²)的算法，关键看用在哪。

3.4 希尔排序：插入排序的进化版

希尔排序是插入排序的改进版。插入排序每次只能把元素往前挪一位，如果最小值在最后面，就得挪n-1次。希尔排序的做法是：先用一个较大的间隔（gap）把数组分成若干组，每组内做插入排序，让元素能大步跳跃地接近最终位置；然后逐渐缩小gap，最后gap=1时做一次标准插入排序。

def shell_sort(arr): n = len(arr) gap = n // 2 while gap > 0: for i in range(gap, n): key = arr[i] j = i while j >= gap and arr[j - gap] > key: arr[j] = arr[j - gap] j -= gap arr[j] = key gap //= 2 return arr

gap的选取是个学问。最简单的就是每次折半，但这样最坏情况还是O(n²)。比较常用的增量序列是Knuth序列：1, 4, 13, 40...，递推公式是h = 3h + 1。用Knuth序列，时间复杂度能到O(n^1.5)。

希尔排序的价值在于：它是唯一一个平均时间复杂度优于O(n²)但空间复杂度为O(1)的算法。如果你内存极其受限，又需要比插入排序更快的性能，希尔排序是唯一选择。

3.5 归并排序：稳定且可预测的优等生

归并排序是分治思想的典型代表：把数组从中间劈成两半，分别排序，然后把两个有序数组合并成一个。

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 log n)。快排最坏会退化到O(n²)，但归并不会。而且它是稳定的。

代价是需要O(n)的额外空间。这个空间开销在大多数场景下可以接受，但在内存极度受限的嵌入式环境里就是问题了。

归并排序还有一个独特优势：外部排序。当数据大到内存装不下时，可以把数据分成若干块，每块排好后写到磁盘，然后多路归并。这是大数据处理里的标准做法。

3.6 快速排序：平均性能最好的通用排序

快速排序的思路是：选一个基准元素（pivot），把比它小的放左边，比它大的放右边，然后对左右两边递归。

def quick_sort(arr, low=0, high=None): if high is None: high = len(arr) - 1 if low < high: pivot_idx = partition(arr, low, high) quick_sort(arr, low, pivot_idx - 1) quick_sort(arr, pivot_idx + 1, high) return arr 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

快排的核心在partition函数。上面用的是Lomuto分区方案，简单但效率一般。更高效的是Hoare分区方案，双向扫描，交换次数更少。

快排最怕什么？已经有序的数据。如果每次选最后一个元素做基准，而数组已经有序，那每次分区都只能分出一个元素，递归深度变成n，时间复杂度退化成O(n²)。解决方案是随机选基准，或者用三数取中法（取首、中、尾三个元素的中位数）。

实操心得：标准库里的快排实现通常会在递归深度超过2log n时切换到堆排序，这就是所谓的Introsort。这样既保留了快排的平均性能，又避免了最坏情况。自己实现快排时，至少要做随机化基准。

3.7 堆排序：Top K问题的利器

堆排序利用二叉堆的性质：大顶堆的根节点是最大值。先把数组构建成大顶堆，然后反复把堆顶元素和末尾元素交换，再调整堆。

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[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0) return arr 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(1)，看起来很美。但实际测试中，堆排序通常比快排慢，因为它的访存模式对CPU缓存不友好——每次调整堆都是跳跃式访问。

堆排序真正的用武之地是Top K问题：从n个元素中找出最大的k个。维护一个大小为k的小顶堆，遍历数组，比堆顶大的就替换堆顶并调整。时间复杂度O(n log k)，空间O(k)。这比全排序再取前k个高效得多。

3.8 计数排序：特定场景下的降维打击

计数排序不比较元素，而是统计每个值出现的次数，然后直接按顺序输出。

def counting_sort(arr): if not arr: return arr max_val = max(arr) min_val = min(arr) range_size = max_val - min_val + 1 count = [0] * range_size for num in arr: count[num - min_val] += 1 # 前缀和，确定每个元素的最终位置 for i in range(1, range_size): count[i] += count[i - 1] result = [0] * len(arr) # 倒序填充，保证稳定性 for num in reversed(arr): count[num - min_val] -= 1 result[count[num - min_val]] = num return result

计数排序的时间复杂度是O(n+k)，k是数值范围。当k远小于n时，比如给几百万个0到100的分数排序，计数排序就是O(n)级别，吊打所有比较类排序。

但它的限制也很明显：只能排整数，而且数值范围不能太大。如果范围是0到10亿，那count数组就要10亿个元素，内存直接爆掉。

注意：计数排序的稳定性依赖于倒序填充。如果正序填充，相同值的元素顺序会反转。需要稳定排序时，一定要倒序遍历原数组。

4. 实际场景中怎么选排序算法

4.1 按数据规模选

数据量小于100：直接用插入排序。常数小，没有递归开销，实际最快。

数据量在100到10000之间：快排或归并都行。如果要求稳定就用归并，否则快排。

数据量大于10000：快排优先，但要注意随机化基准。如果内存充足且要求稳定，归并排序。

数据量极大需要外部排序：归并排序的多路归并版本。

4.2 按数据特征选

数据近乎有序：插入排序或冒泡排序（加了swapped优化的），能降到O(n)。

数据是整数且范围小：计数排序，O(n)级别。

数据有大量重复元素：三路快排（把数组分成小于、等于、大于三部分），避免重复元素导致的性能退化。

需要求Top K：堆排序，维护大小为k的堆。

4.3 按约束条件选

内存极度受限：堆排序或希尔排序，空间O(1)。

要求稳定排序：归并排序或计数排序。

需要并行化：归并排序天然适合并行，左右两半可以独立排序。

5. 常见问题与排查技巧实录

5.1 快排栈溢出怎么办

递归实现的快排在数据量很大时可能栈溢出。解决方案有两个：一是改用迭代实现，手动维护栈；二是先递归较小的一半，较大的一半用循环处理，这样递归深度最多log n。

def quick_sort_optimized(arr, low, high): while low < high: pivot_idx = partition(arr, low, high) # 先处理较小的一半 if pivot_idx - low < high - pivot_idx: quick_sort_optimized(arr, low, pivot_idx - 1) low = pivot_idx + 1 else: quick_sort_optimized(arr, pivot_idx + 1, high) high = pivot_idx - 1 return arr

5.2 归并排序的额外空间能省吗

可以。有一种原地归并算法，空间复杂度能降到O(1)，但实现复杂且常数因子大，实际性能反而下降。大多数场景下，O(n)的额外空间是可以接受的。如果实在不能接受，考虑用堆排序替代。

5.3 排序算法的常见Bug速查表

5.4 面试中排序算法的常见追问

面试官问排序，往往不是让你默写代码，而是考察你对场景的理解。常见的追问包括：

“快排最坏情况是什么，怎么避免？”——回答随机化基准或三数取中。

“归并排序的空间复杂度能优化吗？”——回答可以原地归并但性能下降，或者用堆排序替代。

“为什么标准库用Timsort而不是快排？”——回答Timsort结合了归并和插入排序，对真实数据（通常有部分有序片段）更高效，且稳定。

“一亿个整数怎么排序？”——回答外部排序，分块后多路归并。

6. 我个人的一些实操体会

排序算法这东西，光看不动手是学不会的。我建议你至少把快排、归并、堆排序这三个手写一遍，不用看参考，凭理解写出来。写完跑几个测试用例，包括空数组、单元素、已有序、逆序、大量重复元素这些边界情况。你会发现很多细节问题只有自己写了才会暴露。

另外，别迷信复杂度分析。O(n log n)的算法不一定比O(n²)的快，关键看数据规模和常数因子。插入排序在小数据上就是比快排快，这是实测出来的。理解理论，但尊重实测。

最后分享一个我常用的调试技巧：在排序函数里加一个assert，每次交换后检查数组是否仍然是原数组的一个排列。这能帮你快速定位是逻辑错误还是索引错误。虽然会拖慢速度，但调试阶段非常有用。

这个笔记后续还可以继续扩展，比如基数排序、桶排序、TimSort的详细分析，以及并行排序的实现。排序这个主题，往深了挖还有很多东西。