面试里有个问题特别能暴露一个人的底子：“你讲一下排序。”看似谁都能说两句，但大多数人只能说出冒泡和快排，再往下就开始含糊。排序是数据结构课程里少有的、既有严格数学下界、又和工程实现深度绑定的主题，从408考研到日常写SQL、调前端表格，它一直都在。这篇文章我会从分类体系讲起，把七大经典比较排序、快排的进阶优化、三种线性非比较排序、工程库里的选型逻辑以及考研面试常考的证明方法全部串一遍，适合正在复习数据结构的学生、准备算法面试的开发者，以及那些“天天用sort却不知道sort背后在做什么”的工程实践者。
1. 排序的底层逻辑：比较模型的天花板、稳定性与被忽略的“原地性”
在讲具体算法之前，先建立一个坐标系。很多人学排序是“逐个背代码”，背完就忘，因为脑子里没有那张地图。其实排序算法一共就分两大类：比较排序和非比较排序。这个分类不是凭空的，它决定了算法复杂度的天花板，也决定了你为什么有时候能做出O(n)的排序、有时候再努力也只能是O(n log n)。
1.1 比较排序为什么有O(n log n)的天花板
比较排序指的是那种“通过两个元素之间的比较来决定先后顺序”的算法，冒泡、插入、选择、快排、堆排、归并都属于这一类。这里有一个很震撼的结论：任何基于比较的排序，在最坏情况下都不可能低于O(n log n)。
这个结论不是经验之谈，是信息论给的硬约束。n个互不相同的元素，可能的排列方式是n!种。每一次比较，相当于在两个可能的排列之间做一次二选一，也就是把问题空间砍掉一半。如果有n!种排列，最坏情况下至少需要log2(n!)次比较才能唯一确定真实的顺序。用斯特林公式展开一下，log2(n!)约等于n log2 n。所以，所有基于比较的排序算法，平均复杂度和最坏复杂度的下界就被钉死在这个位置。
这个结论有什么实际意义？它告诉你，快排、归并、堆排的O(n log n)已经是比较排序里的“满级”了，不需要再妄想一个O(n)的比较排序存在。也因此，“非比较排序”才有了存在的必要和价值。
1.2 稳定性：不是理论洁癖，是工程刚需
稳定性说的是，如果两个元素的值相等，排序之后它们的相对顺序会不会变。会变，就是不稳定的；不会变，就是稳定的。
有人觉得这个性质无所谓，反正值相等谁在前谁在后不都一样吗？不是。真实的排序场景里，“相等”往往是针对某一个字段而言的，但记录本身还有很多别的信息。经典的例子是：你有一张学生表，先按学号排好序，再按成绩排序。如果第二次排序不稳定，那么同分的学生内部学号顺序就会乱掉，而你原本是想让同分的人按学号升序展示的。
这个需求不是假的，多关键字排序到处都在用。SQL里的ORDER BY score DESC, id ASC本质上就是依赖每趟排序的稳定性。基数排序能成立，更是因为内部用的排序必须是稳定的，这个点到第4章还会再讲。
1.3 原地性与外部排序：排序不只是内存里的事
还有一个维度常被忽略：“原地性”，也就是额外空间使用量。插入、冒泡、选择、堆排、快排（普通版本）都是原地排序，额外空间是O(1)或者O(log n)。归并排序就不一样，它需要O(n)的辅助空间。这个差异在某些场景下是致命的：如果待排序数据有100GB，而内存只有8GB，任何需要O(n)辅助空间的算法都直接出局。
“外部排序”这个词可能很多人只在考试里见过。它就是为超大数据量设计的，核心思路是把大文件拆成若干能放进内存的小块，每块内部排序后写回磁盘，再用归并的方式逐步合并。你会发现，归并排序不只是考试里的分治标本，它还是外部排序的基石。数据量一大，合并有序序列这个操作就是一切。
2. 逐一拆解经典比较排序：插入类、交换类、选择类与归并范式
建立好坐标系之后，该面对具体算法了。我按“思考逻辑”而不是“热度”来分组：插入类靠“增量”，交换类靠“相邻/双向交换”，选择类靠“挑最小”，归并靠“分治合流”。然后把快排单独放进下一章，因为它值得更大篇幅。
2.1 插入排序：打扑克牌里诞生的增量算法
插入排序的思路一句话：把新元素插入到已经有序的序列里。你打扑克抓牌时，把新抓的牌插到手里正确的位置，就是这个过程。
void insertion_sort(int a[], int n) { for (int i = 1; i < n; i++) { int key = a[i]; int j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } }这段代码里有几个值得琢磨的地方。第一，它把“后移”和“最终插入”拆开了：先用key保存当前元素，前面比key大的全部后移一位，最后把key放进空出来的位置。第二，它的最好情况是O(n)——如果序列已经有序，每次while循环第一轮就失败，只做n-1次比较。第三，它的比较次数就是逆序对数量级别的，最坏情况下输入完全逆序，比较和移动次数都是n(n-1)/2。
关于循环不变量，这个算法的证明非常经典：外层循环第i轮结束时，子数组a[0..i]中元素已排好序，且保持它们在原数组中的相对顺序。初始化时i=0，单个元素当然有序；保持时，因为每次把key插入到正确位置，a[0..i]有序；终止时i=n-1，全数组有序。
插入排序的真实价值在于“几乎有序”的数据。你维护一个在线排行榜，新数据不断加入但老数据基本有序，插入排序就是最合适的，因为它可以边到达边插入，不需要等全部数据齐了再开始。
2.2 希尔排序：给插入排序先做“粗调”
希尔排序是插入排序的升级版，核心直觉是：插入排序在数据接近有序时很快，但“把远距离的逆序元素一步步挪过去”很慢。所以希尔排序先用大间隔gap把元素分组，组内做插入排序，让元素能够“跨大步”地接近它该在的位置，然后逐步缩小gap，最后gap=1时整个数组已经“基本有序”，再做一次普通插入排序收尾。
void shell_sort(int a[], int n) { for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int key = a[i], j = i - gap; while (j >= 0 && a[j] > key) { a[j + gap] = a[j]; j -= gap; } a[j + gap] = key; } } }注意里层循环不是只对gap个独立子序列做插入排序，而是从gap开始逐个元素往前走，相当于把所有子序列的插入排序“交织”在一起，这样代码干净且缓存更友好。希尔排序的时间复杂度跟gap序列强相关。gap每次除以2这种简单策略，最坏是O(n^2)；用Knuth序列（1, 4, 13, 40, 121...）可以把最坏降到O(n^(3/2))；更复杂的Sedgewick序列能到O(n^(4/3))左右。这说明一个道理：同一个算法框架，参数设计错了，性能天差地别。
2.3 冒泡排序：教学价值大于工程价值
冒泡排序人人都会：从头到尾相邻比较，大的往后冒，每轮至少把一个最大值送到最终位置。
void bubble_sort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int swapped = 0; for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { swap(&a[j], &a[j + 1]); swapped = 1; } } if (!swapped) break; } }很多教材没强调那个swapped标志。有了它，如果某轮没有任何交换，说明数组已经有序，可以直接终止，最好情况变成O(n)。这也是冒泡排序唯一值得被记住的优化点。但说实话，它的交换次数太多，每轮都可能进行大量无效的相邻交换，工程里基本没人用。它存在的意义是培养“比较-交换”的直觉，尤其适合初学者理解稳定排序的含义：冒泡只和相邻元素交换，相等元素永不跨过对方，所以它是稳定的。
2.4 简单选择排序：最慢但最好理解的“挑最小”
选择排序的思路就是每一轮从剩余元素里挑出最小的，放到当前正在填充的位置。
void selection_sort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int min_idx = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[min_idx]) min_idx = j; } if (min_idx != i) swap(&a[i], &a[min_idx]); } }它的优点是交换次数少，最多只有n-1次交换，适用于那种“一次交换代价极高”的场景。缺点是无论数据是什么样子，比较次数都固定为n(n-1)/2，不给任何好脸色。还有一个容易踩的坑：它不稳定。看这行代码，如果最小的元素在某个相等元素的后面，swap会把后面那个元素换到前面，破坏相对顺序。所以，选择排序的“简单”是有代价的，多关键字排序时用它会出问题。
2.5 堆排序：用完全二叉树做选择排序的加速器
前面说选择排序慢就慢在每轮都要扫描剩余全部元素找最小值。堆排序就是为了解决“扫描太慢”这个问题：用一个堆来维护剩余元素的最小值，每次取堆顶O(1)，删除堆顶后调整O(log n)，总复杂度O(n log n)。
堆可以完全存在数组里，不需要真的建一棵树。关键操作是shiftDown。建堆不需要一个个插入，而是从最后一个非叶子节点开始向下调整，整体建堆复杂度是O(n)。这个结论可能反直觉，但计算一下就知道：高度为h的节点最多n/2^(h+1)个，每个节点的向下调整代价是O(h)，求和结果是O(n)。
void heapify(int a[], int n, int i) { int largest = i; int l = 2 * i + 1, r = 2 * i + 2; if (l < n && a[l] > a[largest]) largest = l; if (r < n && a[r] > a[largest]) largest = r; if (largest != i) { swap(&a[largest], &a[i]); heapify(a, n, largest); } } void heap_sort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); for (int i = n - 1; i > 0; i--) { swap(&a[0], &a[i]); heapify(a, i, 0); } }堆排序的工程地位很微妙：它最坏也是O(n log n)，不像快排有退化风险，但它对缓存非常不友好，数组访问是跳跃式的，而且不稳定。它真正的舞台是“你需要一个稳定的最坏情况O(n log n)，又不想开O(n)辅助空间”的时候，以及Top-K问题里，“维护大小为K的堆”几乎是标准操作。
2.6 归并排序：分治与合并的教科书模板
归并排序的思路简单到让人怀疑：把数组对半拆，拆到只剩一个元素，然后再两两合并有序序列。
void merge(int a[], int l, int mid, int r) { int n1 = mid - l + 1, n2 = r - mid; int L[n1], R[n2]; for (int i = 0; i < n1; i++) L[i] = a[l + i]; for (int i = 0; i < n2; i++) R[i] = a[mid + 1 + i]; int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) a[k++] = L[i++]; else a[k++] = R[j++]; } while (i < n1) a[k++] = L[i++]; while (j < n2) a[k++] = R[j++]; }它的时间复杂度稳定在O(n log n)，而且稳定。代价是需要O(n)的辅助空间，这在高负载场景里可能成为瓶颈。归并排序的另一个价值是它“自上而下拆、自下而上合”的思想启发了外部排序，以及后面要讲的TimSort。写归并排序时最容易错的是边界：mid = (l + r) / 2时，左半是[l, mid]，右半是[mid+1, r]，左右区间不能重叠也不能漏。这个“区间划分”的细节，几乎每本教材的勘误表里都有读者踩坑记录。
3. 快速排序的进阶战场：枢纽选择、重复元素与混合策略
快排单独占一章，不是因为它的基础版本有多难，而是因为它在工程和面试里的地位和其他算法完全不在一个量级。理解了快排，你就理解了大部分sort函数的内部世界。
3.1 为什么所有默认排序函数都围绕快排转
先看一个基础版快排，用的Lomuto分区法，代码很直观：
int partition(int a[], int l, int r) { int pivot = a[r]; int i = l - 1; for (int j = l; j < r; j++) { if (a[j] < pivot) { i++; swap(&a[i], &a[j]); } } swap(&a[i + 1], &a[r]); return i + 1; } void quick_sort(int a[], int l, int r) { if (l >= r) return; int p = partition(a, l, r); quick_sort(a, l, p - 1); quick_sort(a, p + 1, r); }快排的平均复杂度是O(n log n)，但它被工程界青睐的核心原因不是这个——归并和堆也有这个复杂度。真正的原因是快排的平均常数特别小，而且它操作数据时是顺序扫描的局部访问，CPU缓存命中率比堆排高很多。堆排序虽然理论复杂度好看，但“理论上最快”和“实际上最快”从来不是一回事。
3.2 枢纽pivot选不好，快排会变“慢排”
快排最怕的是“每次分区只分掉一个元素”。如果待排序数组已经有序，你每次都选最右端元素当pivot，那么每次partition都把一个元素放到正确位置，剩下O(n-1)个继续递归，递归深度O(n)，总时间直接O(n^2)。攻击者甚至可以利用这个特性来构造数据集，把排序库拖慢——历史上确实有C++标准库某版本因此被DoS的例子。
常规解法有两个。第一是随机选pivot，让最坏情况的输入变得极难构造。第二是三数取中，从区间的左端、中间、右端取三个元素，用它们的中位数当pivot。三数取中的效果不只是防退化，它还能明显改善随机数据的平衡度。我在实际项目中很少写裸快排，最少也是“三数取中+递归深度限制”的组合。
3.3 双路和三路快排：如何拯救满是重复元素的数组
如果数组里有大量重复元素，比如一亿个元素里九成都是同一个值，普通快排会退化得很厉害：和pivot相等的元素被随机分到左边或右边，分区依然不平衡。这时候需要三路快排。三路快排把数组分成三块：小于pivot、等于pivot、大于pivot，递归只处理小于和大于的部分，等于的部分直接跳过。
一个经典写法是循环不变量驱动的：
void quick3(int a[], int l, int r) { if (l >= r) return; int lt = l, gt = r, i = l + 1; int pivot = a[l]; while (i <= gt) { if (a[i] < pivot) swap(&a[lt++], &a[i++]); else if (a[i] > pivot) swap(&a[i], &a[gt--]); else i++; } quick3(a, l, lt - 1); quick3(a, gt + 1, r); }这里lt表示“小于区的右边界”，gt表示“大于区的左边界”，i是当前扫描位置。写完这段我自己调试过很久，核心要领是：指针移动的三种情况里，只有“当前元素小于pivot”时i才前进，等于时i前进但lt不动，大于时i不动但要交换到gt。这个函数还有个衍生考点，就是著名的荷兰国旗问题——给你红白蓝三种球乱序排列，用一次O(n)扫描排成红白蓝顺序，本质就是三路分区的简化版。
3.4 introsort：量子速读C++ sort的兜底策略
工程排序库不会只靠快排。C++标准库里的std::sort，主流实现是introsort：它用快排为主，但在递归深度超过某个阈值时切换成堆排序，因为递归太深说明分区质量很差，继续快速排序极可能退化成O(n^2)，而堆排序能保证O(n log n)。同时，当分区后的小区间长度小于某个阈值（比如16）时，直接改用插入排序。
这个“混合策略”是排序工程化的教科书级示范：用快排的平均高性能，用堆排弥补最坏情况，用插入排序处理小区间减少递归调用。学排序如果只学单算法、不理解这种组合思路，很难说真正理解了工程排序。
3.5 小区间插入排序与递归深度控制
为什么小区间要用插入排序？因为快排的递归是函数调用，每次递归都有栈帧开销，而插入排序在小数组上的常数非常小。递归到16个元素时，剩余的“几乎有序”的小碎片，用插入排序几下就排完了。实验数据表明，cutoff取10到20之间通常效果最好，取太大了反而会因为插入排序的O(n^2)特性拖慢整体。
还有一点容易忽略：手动栈还是递归。如果你在嵌入式环境或者面试时被要求迭代实现快排，你要用显式栈保存待排序区间，本质是把递归转成循环。这个写法的难点同样是区间边界管理：每次弹出区间后分区，再按顺序把子区间压栈。想清楚“先压哪个、后压哪个”不影响正确性，只影响处理顺序，这个思想对理解递归和栈的关系很有帮助。
4. 线性时间的非比较排序：计数、基数与桶排的应用边界
比较排序有O(n log n)的天花板，但如果数据满足特定条件，我们可以绕过比较模型，直接利用数据的结构信息做到O(n)。这个“绕过”的思路是整章的核心。
4.1 计数排序：用桶换掉比较
计数排序的前提非常严格：数据必须是非负整数，且值域k不能太大。方法是先数一遍每个值出现了多少次，再算前缀和得到每个元素的最终位置，最后倒序扫描原数组放回结果数组。
def counting_sort(arr, k): n = len(arr) count = [0] * (k + 1) out = [0] * n for x in arr: count[x] += 1 for i in range(1, k + 1): count[i] += count[i - 1] for x in reversed(arr): count[x] -= 1 out[count[x]] = x return out为什么最后要倒序扫描？这是计数排序保持稳定性最关键的一步。前缀和之后，count[x]表示“小于等于x的元素数量”，也就是x应该占据的最后一个位置。倒序扫描时，相同值的元素会从后往前依次填入，它们的相对顺序就被保住了。如果正序扫，稳定性就丢了。时间复杂度O(n+k)，空间O(k)。典型应用是年龄排序、成绩排序这种值域几十上百的场景。如果k=10^9，你不可能开一个十亿的数组，所以计数值域必须可控。
4.2 基数排序：稳定排序的连环接力
基数排序的思想是“多趟稳定的低位优先排序”。对非负整数，先按个位做一次稳定排序，再按十位做一次稳定排序，依此类推，最高位完成后整个数组就有序了。为什么每趟必须稳定？因为个位排完后，十位相同的元素之间需要保持个位的相对顺序；如果某趟排序不稳定，前面所有趟的成果都被冲掉了。
实现时，每趟内部通常用计数排序来保证线性时间。总复杂度是O(d(n+r))，d是位数，r是基数的大小。如果你用256做基数，一次处理8位，一个32位整数只需要4趟。这就是字符串排序、日期排序、长整数排序的底层方案之一。关于r的选择：r越大，每趟的计数数组越大，但趟数d越小。权衡点在于内存带宽和cache，实践中取256常常是个不错的折中。
4.3 桶排序：均匀数据下的线性排序
桶排序更适合“浮点数”这类值域连续的数据。思路是把值域切成k个区间，把数据分到k个桶里，每个桶内部用插入排序或其他排序，最后按桶顺序输出。它的时间复杂度分析依赖数据分布：数据均匀分布时，每个桶内的数据量大约是n/k，总复杂度接近O(n)；数据集中分布时，所有数据挤进一个桶，复杂度退化为内部排序的复杂度，可能变O(n^2)。
一个很自然的应用是：考试成绩0到100分，你切成10个桶，每个桶内部排一下，比全局快排快不少。前端做柱状图排序、数据分析里对浮点数组预分桶，思路也是一样的。但桶排序有个麻烦点：桶内元素数量不能预先确定，需要动态扩容或用链表，实现比计数排序脏一些。
4.4 什么时候才该用非比较排序：三个实用判断
一，数据类型是否可离散化？整数、定长字符串、日期可以；任意浮点数先要分桶。二，值域是否可控？排序100万个0到99的整数，计数排序秒杀快排；排序100万个0到10^18的整数，计数排序直接内存爆炸。三，是否存在大规模重复？大量重复元素时，三路快排已经能到接近线性，非比较排序的“线性”优势会被缩小。很多教材把非比较排序讲成“快排的替代品”，这是误导。实际工程里它更像“特定数据集下的特种部队”，知道何时用、何时别用，比会写更重要。
5. 工程代码库里的排序真相：从sort函数到SQL排序的暗坑
真正写业务代码时，很少有人自己手写排序，但这不代表排序和你无关。复杂的是“哪个sort在跑我的数据”和“为什么数据库排序这么慢”。
5.1 C的qsort与C++的sort：函数指针与模板内联的分水岭
C语言的qsort是快排的标准库实现，但它接受一个函数指针作为比较器。每次比较都是一次间接函数调用，这个开销在数据量大时非常可观。我记得有人在百万级数据上测过，qsort比手写比较逻辑还要慢不少。
C++的std::sort则不同：它是模板函数，比较器在编译期就内联展开，不存在运行时函数指针跳转。加上introsort的混合策略，同样是“标准库快排”，真实性能能差出一个数量级。所以，如果你是C++用户，别自己手写快排，直接用std::sort就好；如果你必须用C，qsort能用，但要意识到它的性能上限。
5.2 Java和Python为什么默认用TimSort
Java的Arrays.sort对不同类型采取了完全不同的策略：基本类型用双基准快排，因为基本类型没有稳定性需求；对象类型用TimSort，因为对象排序通常依赖多个字段，稳定性是硬需求。Python内置排序也是TimSort。
TimSort是归并排序的工程化改良版。它先把数组拆分成一个个天然有序的run，短的run用插入排序拉长，然后按规则合并这些run。它的优势极其明显：如果数组本来就有部分有序结构，TimSort的复杂度可能远低于O(n log n)，甚至接近O(n)。这对真实世界的数据来说价值巨大，因为业务数据几乎从不随机，通常都存在明显的局部有序性。
我后来才想明白一件事：为什么很多面试题强调“排序算法要稳定”，因为实际生产中，对象排序的稳定性就是多字段排序正确性的一道保险。Java官方替你想好了，Python也替你想好了，反而是不少自以为自己懂排序的人，在项目里自己实现选择排序，把数据顺序排乱了。
5.3 SQL ORDER BY与ORM别名排序：索引才是亲爹
数据库里的排序，最核心的一条规则是：能走索引就尽量走索引。B+树索引的叶子节点本身就是有序的，MySQL如果发现ORDER BY字段正好有可用索引，直接按索引顺序扫描返回，不需要任何排序。而一旦没有索引，引擎就要用filesort：先把匹配的行放入sort buffer，在内存或磁盘上做排序，数据量超过sort buffer大小时，要写临时文件再做归并，慢得肉眼可见。
我在业务系统里处理过一个慢查询，ORDER BY created_at DESC LIMIT 50，表里有几百万行，每次查询将近一秒。加上(user_id, created_at)的联合索引后，直接秒回。原因就是索引让MySQL连排序都不做了。所以SQL排序优化第一优先级永远是索引设计，而不是去换什么高级排序算法。
ORM层面的坑也不能忽视。拿Sequelize举例，如果你在include里的模型上用别名排序，直接写order: [['alias', 'ASC']]，框架可能会把这个名字当成模型的字段名去转义，四川排序结果完全不对。常用的办法是：
order: sequelize.literal('COALESCE(alias, 0) ASC')或者用fn和col组合。核心原则是：当排序字段不是简单的模型属性，而是表达式、别名或嵌套属性时，要把“排序表达式”明确交给SQL引擎处理，而不是让ORM猜测。
5.4 表格头排序、pandas与字符串排序：数据处理场景的同款问题
前端点击表头排序是另一个翻车高发区。最常见的是默认的Array.prototype.sort()把数字字符串按字典序排：10排在2前面，因为在字符串比较中“1”小于“2”。解决方法是显式用(a, b) => Number(a) - Number(b)。
还有一个容易被忽视的点：多列排序时，需要序列中的每一步排序都是稳定的。前端很多排序方法是稳定的，但pandas默认不是。df.sort_values默认使用quicksort，它不是稳定排序。如果你需要按A列排完再按B列排，并且希望A的优先级体现在最终结果里，应该明确指定kind='mergesort'或使用stable参数，否则第二次排序可能打乱第一次相同组的顺序。
字符串排序就更隐蔽了。你以为是“按字符集的码点排”，其实数据库是按校对规则collation排的，不同collation对中文、大小写、重音字符的处理完全不一样。两个看起来一样的中文排序需求，在utf8mb4_general_ci和utf8mb4_unicode_ci下结果可能不同。做多语言平台时，字符串排序规则最好明确写入配置，不要靠默认值猜。
5.5 数据库索引与B+树：为什么有序结构能白送排序
为什么数据库一提到排序就绕不开索引？因为B+树的叶子节点用链表串起来，天然有序。插入时维护有序性的开销由索引自己承担，查询时你可以免费享受顺序遍历。
这也是数据结构知识面最“出圈”的时刻：学排序不只是会写几行算法，而是要明白“一旦数据维护成有序结构，读的时候就省掉排序这一步”。数据结构的各种树、堆、跳表、链表的本质之一，就是在写的时候多费一点工，读的时候省一大笔钱。理解了这一点，你再看各种“排序优化最佳实践”，本质都不是什么高深的算法，而是在恰当的场景里选择了恰当的有序结构。
6. 考研与面试视角：复杂度速查、不变量证明与我的学习建议
这一章是给正在备考和准备面试的人准备的，也是全文最后一块拼图。前面的内容如果说是“要把排序讲明白”，这里就是“怎么把学到的讲给别人听、写在卷子上”。
6.1 一张表终结复杂度与稳定性记忆
先放总表。这张表背下来不难，难的是理解为什么是这些数。
| 排序算法 | 最好时间 | 平均时间 | 最坏时间 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n log n)附近 | 与步长序列有关 | O(n^2)或O(n^(3/2)) | O(1) | 不稳定 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 快排 | O(n log n) | O(n log n) | O(n^2) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 |
| 桶排序 | O(n+k) | O(n+k) | O(n^2) | O(n+k) | 看内部排序 |
记忆技巧：不稳定家族就是“选择、希尔、快排、堆排”这四个，口诀可以是“选块堆奇”。其余的插入、冒泡、归并都是稳定的。为什么它们稳定？因为它们都只调整相邻元素的顺序，不会跨过相等元素。
6.2 循环不变量证明示范：以选择排序为例
这部分直接回应很多考研资料里“clrs选择排序循环不变量证明”的高频考点。循环不变量证明分三步：初始化、保持、终止。
以选择排序为例，循环不变量的形式是：在外层循环每次迭代开始时，子数组a[0..i-1]已经排好序，并且其中所有元素都不大于剩余子数组a[i..n-1]中的任何元素。
- 初始化：i=0时，a[0..-1]是空数组，条件自然成立。
- 保持：假设迭代开始时条件成立，循环体会在a[i..n-1]中找出最小值minIdx，并与a[i]交换。于是a[0..i]中，a[i]是剩余部分的最小值，整段仍然有序，且不大于后面剩余元素。下一次迭代前，条件对新的i成立。
- 终止：i=n时，a[0..n-1]已经全部排好，算法正确结束。
这套证明模板能用在很多地方。归并排序的分治正确性可以用主定理和循环不变量组合证明，插入排序的不变量和选择排序类似但表述是“前j个已排序”。面试时不用整段背，能现场讲出“初始化、保持、终止”这个三段式，就足够让面试官放心了。
6.3 排序问题的高频考法：手撕快排、Top-K、荷兰国旗、外部排序
简单列一下我在笔试和面试里见过最多的问题类型。手撕快排是最高频的，最好能做到闭着眼睛写出无bug的Lomuto分区或Hoare分区。Top-K问题，经典解法是“堆维护”和“快排partition剪枝”，后者是平均O(n)的quickselect思想。荷兰国旗问题就是三路快排的简化。外部排序考的是归并分阶段思路和磁盘IO优化。408考纲里图和数组部分也会和排序联动，比如最小生成树算法要先把边按权重排序，稀疏数组排序后做二分查找等。
对于备考的人，我的建议是：不要只背代码。把“为什么外层循环是n-1次”“为什么内层循环的右边界是递减的”想清楚，哪怕题目换一种语言、换一种数据结构，你也照样能写出来。写实验报告的时候，复杂度推导、边界条件测试用例（有序、逆序、随机、大量重复）这三样必须齐，否则实验报告就是空壳。
6.4 关于学习路线和踩坑的一些实在话
如果只让我推荐一个顺序，我会这样排：先学插入排序和选择排序，因为它们最贴近人的直觉；再学冒泡和归并，前者是稳定性的标本，后者是分治的入门；然后重点学快排和堆排，这一对是面试的主力；最后扩展希尔排序和三种非比较排序。
我自己踩过最大的坑，是快排partition的边界条件。写出的代码有时在数组长度为2时崩溃，有时在重复元素上死循环。后来我给自己定了一条规矩：分区区间一律用闭区间[l, r]，移动指针时先处理右指针再处理左指针，循环退出后记得判断指针越界。这套习惯帮我避免了很多脏调试。
如果想再进阶，可以看一眼并行排序领域，比如Batcher的双调排序网络，那是把排序大规模并行化的硬件友好方案。排序算法学的不是那几段代码，而是“如何利用数据特征、结构、分治、并行”来组织信息。把这条线想通了，后面学图算法、学数据库、学分布式框架，都会顺很多。
最后想说的是：不要嫌弃那些“太简单”的排序。插入排序在近乎有序的数据上就是比快排快，归并排序在稳定性需求面前是不可替代的，选择排序让初学者第一次看到循环不变量是什么。每种排序都是一类思想在特定条件下的最优解。你真正掌握了它们各自“在什么条件下、为什么最优”，才算是把排序这个主题吃透了。以后不管是在群里讨论算法题，还是在代码评审时指出排序方案的隐患，你都比当年那个只会冒泡的自己强了很多。
