尧图网页设计 
写业务代码这些年真正从头手写排序的次数一只手数得过来但每次被问到、每次要调优一段跑得慢的代码最后拼的都是这十个算法里攒下的底子。冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数——十个名字背后其实是五类截然不同的思路交换、插入、选择、分治、桶思想。很多人背下了复杂度和代码模板却说不清为什么快排要比归并快为什么 Java 对基本类型和对象用了两套排序为什么明明有库函数还要自己写。这篇笔记我按数据怎么动这条线把十大排序算法重新捋一遍每个算法给算法思想、给能看懂的文字图解、给可直接跑的代码重点讲清工程里真正会踩的坑基准怎么取、边界怎么写、什么时候快排会退化成 O(n²)、稳定性在什么场景下会咬你一口。适合正在准备数据结构与算法笔记的同学也适合写了几年代码想把底层逻辑补回来的开发者。读完之后你至少应该能做到三件事看到一组数据能立刻判断该用哪个算法、能手写快排和归并不出错、能解释每个优化点的来龙去脉。1. 按数据是怎么移动的把十个算法分成五族大多数人记排序算法是靠口诀硬背背完就忘。我自己的经验是先记住数据在数组里是怎么挪位置的剩下的一切都能推出来。这一层想通了复杂度、稳定性、适用场景基本都是自然结论不需要单独背。1.1 五族分类交换、插入、选择、分治、桶交换族冒泡排序、快速排序。核心动作是把两个元素对调直到所有逆序对消失。冒泡是相邻交换快排是远距离交换——这个差别直接决定了两者一个是 O(n²)一个是 O(n log n)。插入族直接插入排序、希尔排序。核心动作是把一个元素插到前面已经有序的序列里合适的位置。希尔排序就是带步长的插入排序先让远距离的元素有序减少后面的搬移量。选择族简单选择排序、堆排序。核心动作是每一轮从待排区域里挑出最值放到已排区域的末端。堆排序之所以快是因为它用堆结构把挑最值从 O(n) 降到了 O(log n)。分治族归并排序。核心动作是先切半、各自排好、再合并。它的贵在于要额外空间稳在于合并过程天然稳定。桶族计数排序、桶排序、基数排序。这三个是不比较元素大小的排序靠把元素丢进对应的桶完成。它们的下限能突破 O(n log n)代价是对数据分布有要求。把这五族记住你会发现面试官问快排和归并的区别本质上是在问交换族和分治族的取舍问堆排序和选择排序的关系就是在问选择族里 O(n) 挑选怎么变成 O(log n)。用族的概念去组织记忆比零散地背十个算法牢固得多。1.2 十大排序算法速查表下面这张表我建议直接抄进笔记首页它是所有讨论的起点。表里的平均时间复杂度、最坏情况、空间、稳定性四项是选型时最先看的指标。算法平均时间最坏时间最好时间空间稳定性是否比较冒泡排序O(n²)O(n²)O(n)O(1)稳定是选择排序O(n²)O(n²)O(n²)O(1)不稳定是插入排序O(n²)O(n²)O(n)O(1)稳定是希尔排序O(n^1.3)O(n²)O(n)O(1)不稳定是归并排序O(n log n)O(n log n)O(n log n)O(n)稳定是快速排序O(n log n)O(n²)O(n log n)O(log n)不稳定是堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定是计数排序O(n k)O(n k)O(n k)O(k)稳定否桶排序O(n k)O(n²)O(n)O(n k)稳定否基数排序O(d(n k))O(d(n k))O(d(n k))O(n k)稳定否表里有几个容易被忽略的细节值得单独拎出来说。快排的空间复杂度不是 O(1)虽然它没有额外开数组但递归调用栈要占 O(log n)最坏情况下递归深度到 n栈空间就是 O(n)。希尔排序的最好情况是 O(n)因为当数组已经基本有序时插入排序本身就接近线性。桶排序的最坏情况是 O(n²)这个反直觉——如果有人故意把数据全塞进同一个桶那就退化成了桶内做插入排序等于什么都没优化。1.3 稳定性不是学术概念它会实实在在咬你一口稳定性的定义是对于值相等的两个元素排序后它们的相对次序保持不变。为什么这件事重要举个最常见的业务场景——电商列表先按销量降序排再按价格升序排。如果用的是不稳定的排序第二次排序会把第一次排好的销量顺序打乱结果就是同价格的商品销量顺序乱了。用稳定排序就不会有这个问题因为价格相同的元素会保留上一轮的销量顺序。再比如 Python 里对一组元组排序sorted(data, keylambda x: x[2])Python 用的是 TimSort归并插入的混合算法是稳定排序所以相同 key 的记录会保持原有顺序。这个特性在数据处理里非常有用等于免费拿到多级排序的能力。反过来Java 的Arrays.sort(int[])用的是双轴快速排序不稳定而Arrays.sort(Object[])用的是 TimSort稳定。同一门语言里两套策略背后的考量就是基本类型不需要区分相等的两个 3而对象可能需要。顺着这个思路去理解为什么要分成两套实现比死记结论强。2. 冒泡、选择、插入入门三件套的真实差距这三个算法代码最短但恰恰是被讲得最浅的。很多人的笔记里三者的区别只有复杂度一样、写法不同。实际上它们的常数因子、对数据初始状态的敏感度、以及能不能在线处理差别非常大。2.1 冒泡排序提前退出优化才是它唯一的价值冒泡排序的算法思想很直观每一轮从头到尾比较相邻两个元素逆序就交换一轮下来最大的元素就冒到了末尾。如果写成硬循环它永远是 O(n²)没有任何亮点。真正值得学的是那个提前退出的优化。def bubble_sort(a): n len(a) for i in range(n - 1): swapped False for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] swapped True if not swapped: # 这一轮没有任何交换说明已经有序 break return a加上swapped标记之后对已经有序的数组冒泡排序只需要跑一轮就能退出时间复杂度降到 O(n)。这里有个细节很多人会写错swapped必须定义在外层循环内部每轮重置一次如果定义在外面第二轮之后就再也不会为真提前退出会失效。还有一个更进一步的优化思路记录每一轮最后一次交换发生的位置因为这个位置之后的元素已经有序了下一轮只需要扫到这个位置就行。不过说实话冒泡排序交换次数等于数组的逆序对数量这个性质在统计数据有多乱时挺有用但拿它来实际排序性能上真的没有竞争力。我个人的态度是冒泡排序是用来理解排序的教具写业务代码时不要用它。2.2 选择排序为什么它天生不稳定选择排序的思路是每一轮在未排序区间里找最小值和未排序区间的第一个元素交换。找最小值是 O(n)做 n 轮所以无论如何都是 O(n²)最好最坏都一样不受数据初始状态影响。代码大概是这样public static void selectionSort(int[] a) { int n a.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) { minIdx j; } } if (minIdx ! i) { int t a[i]; a[i] a[minIdx]; a[minIdx] t; } } }它不稳定的原因就藏在交换这个动作里。举个例子数组是[5, 5, 2]第一轮找到的最小值是 2位置在索引 2把它和索引 0 的 5 交换数组变成[2, 5, 5]——原来的第一个 5 跑到后面去了两个 5 的相对顺序变了。同样是 O(n²)插入排序稳定而选择排序不稳定差别就在于插入排序用的是逐个后移后移不会改变相等元素的相对位置。选择排序唯一的优势是交换次数最少最多交换 n-1 次。如果排序对象的交换成本极高比如大结构体选择排序有它的用武之地。但这种场景现在基本被指针排序覆盖了所以它的实际用途也很有限。2.3 插入排序小数组里的隐形冠军插入排序的思路是把手里的牌一张张插到合适位置。它的复杂度分析特别有意思元素如果离它最终位置很近搬移量就小。数组越接近有序插入排序越快完全有序时它是 O(n)。def insertion_sort(a): for i in range(1, len(a)): key a[i] j i - 1 while j 0 and a[j] key: a[j 1] a[j] j - 1 a[j 1] key return a注意while里用的是a[j] key而不是这个符号直接决定了稳定性用时相等的元素不会被搬走插入到相等元素后面保持稳定用就会把相等元素往前插破坏稳定性。这是个很小的细节但面试里被问你怎么保证插入排序是稳定的答案就是这个比较符号。插入排序真正重要的地位在于它是所有工业级排序算法的收尾选手。Python 的 TimSort、Java 的 TimSort、C 的 introsort在数组被切到很小通常是 16 到 32 个元素之后都会切换成插入排序。原因是插入排序常数项小没有函数调用开销对小数组比快速排序还快。这个阈值不是随便定的常见取值是 16可以在 JDK 源码里看到INSERTION_SORT_THRESHOLD 32这样的常量。理解这一点比单纯记住插入排序是 O(n²)有价值得多——在真实工程里插入排序每天都在被高频调用。3. 希尔与归并两条跳出 O(n²) 的路从这一节开始我们进入真正有工程价值的算法。希尔排序是插入排序的加强版归并排序是分治思想的代表作它们代表了两种完全不同的破局思路。3.1 希尔排序给插入排序装上一个放大镜插入排序慢在哪慢在每次只能挪一格如果一个小元素在数组末尾它要挪 n 步才能到前面。希尔排序的想法就是先用一个大的步长gap把元素分成若干组组内做插入排序让小的元素能跨大步往前走然后逐步缩小 gap最后 gap1 时做一次普通插入排序。因为此时数组已经基本有序了最后这一趟会非常快。文字图解一下对[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]走 gap5 的过程分组下标相差 5 的在一组: 组1: 8, 3 - 3, 8 组2: 9, 5 - 5, 9 组3: 1, 4 - 1, 4 组4: 7, 6 - 6, 7 组5: 2, 0 - 0, 2 一轮后: [3, 5, 1, 6, 0, 8, 9, 4, 7, 2] 可以看到最小的 0 已经从末尾跑到第 5 位一步跨了 5 格。def shell_sort(a): n len(a) gap 1 while gap n // 3: # Knuth 增量序列: 1, 4, 13, 40, ... gap gap * 3 1 while gap 1: for i in range(gap, n): key a[i] j i - gap while j 0 and a[j] key: a[j gap] a[j] j - gap a[j gap] key gap // 3 return a增量序列的选择直接决定性能。经典的希尔增量n/2, n/4, ..., 1最坏能退化到 O(n²)Knuth 的3h1序列可以把平均复杂度压到 O(n^1.5) 左右还有更激进的 Sedgewick 序列能把最坏情况压到 O(n^(4/3))。我在笔记里习惯把希尔排序的复杂度写成约 O(n^1.3)取决于增量序列因为给一个确定的数字是不严谨的。希尔排序不稳定原因和插入排序一样——它是跨步长移动的两个相等的元素可能因为分在不同的组里被调换顺序。这一点在面试里经常被追问值得记住。3.2 归并排序先切再合合并是灵魂归并排序的分治三部曲分解——把数组从中间切成两半解决——递归地对两半分别排序合并——把两个有序数组合并成一个有序数组。前两步是递归框架真正干活的是第三步。合并两个有序数组的过程用文字图解最清楚。假设左半是[1, 5, 9]右半是[2, 6, 7]i0(指1) j0(指2) 结果[] 比较 1 2 - 取 1, i 后移 结果[1] 比较 5 2 - 取 2, j 后移 结果[1,2] 比较 5 6 - 取 5, i 后移 结果[1,2,5] 比较 9 6 - 取 6, j 后移 结果[1,2,5,6] 比较 9 7 - 取 7, j 后移 结果[1,2,5,6,7] 右边耗尽, 左半剩余整体接上 结果[1,2,5,6,7,9]def merge_sort(a): if len(a) 1: return a mid len(a) // 2 left merge_sort(a[:mid]) right merge_sort(a[mid:]) return merge(left, right) def merge(left, right): res [] i j 0 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合并时left[i] right[j]里的等号是稳定性的关键当两边元素相等时优先取左边的左边本来就在前面相对顺序得以保持。如果把等号去掉写成右半相等元素就会抢先稳定性就没了。这个细节在很多教程里被省略但恰恰是面试的常考点。3.3 归并的空间换时间和它在链表、外部排序里的独特地位归并排序的代价很直白每次合并都要开一个临时数组空间 O(n)。这是它输给快排的主要原因。但它在两个场景里无可替代。第一个场景是链表排序。数组的归并需要额外空间因为合并时要同时保存两段数据而链表的节点可以随时改指针合并两个有序链表只需要 O(1) 的额外空间直接原地串起来就行。所以LeetCode 148. 排序链表的标准解法就是归并排序快排反而不好写——链表没有随机访问快排找基准和分区的效率都很差。第二个场景是外部排序。当数据大到内存放不下时思路是把大文件切成若干能塞进内存的块每块内部排序后写回磁盘得到若干个有序的小文件然后再用多路归并把它们合并成一个大文件。整个流程的核心就是归并这是数据库和大数据处理里的基础操作。理解了这一层你就能明白为什么归并排序在数据量超过内存的场景下依然不可替代。还有一点值得提归并排序是唯一一个稳定且最坏情况也是 O(n log n)的比较类排序。快排最坏是 O(n²)堆排序不稳定计数类排序有适用范围。要求稳定 最坏 O(n log n) 不挑数据只有归并满足。Java 里对对象排序用 TimSort 而不是快排本质就是这个考量。4. 快速排序被用得最多也被问得最细快排是十个算法里被问得最多的一个因为它的工程实践最复杂分区怎么写、基准怎么取、重复元素怎么处理、什么时候会退化每一个点都能展开讲半小时。它也是我见过的代码看起来对、实际有 bug发生率最高的算法。4.1 分区的两种写法挖坑法和双指针快排的核心是分区partition选一个基准值 pivot把数组分成左边全小于等于 pivot、右边全大于等于 pivot两部分然后对两部分递归。挖坑法的思路是先把基准值取出来存起来基准位置就成了第一个坑从右边找一个比基准小的数填进左边的坑这个数的原位置变成新坑再从左边找一个比基准大的数填进右边的坑如此往复直到左右指针相遇把基准值填进最后的坑。public static void quickSort(int[] a, int low, int high) { if (low high) return; int pivot a[low]; // 挖出第一个坑 int i low, j high; while (i j) { while (i j a[j] pivot) j--; // 从右往左找比基准小的 if (i j) a[i] a[j]; // 填左坑, 右位置成新坑 while (i j a[i] pivot) i; // 从左往右找比基准大的 if (i j) a[j--] a[i]; // 填右坑 } a[i] pivot; // 基准归位 quickSort(a, low, i - 1); quickSort(a, i 1, high); }这段代码有两个高频错误点我当年都踩过。第一个是右边先走还是左边先走的问题。用挖坑法且基准取最左边时必须先动右指针。原因是如果先动左指针最后相遇的位置可能是一个比基准大的元素把它和基准交换后左边就出现了比基准大的值分区就错了。第二个是内层while里的i j判断不能省否则数组里有大量重复元素时指针会越界。双指针法也叫前后指针法是另一种思路用一个i表示小于等于基准区域的右边界用j从左到右扫描遇到比基准小的就把它换到i的位置并让i前进。def partition(a, low, high): pivot a[high] # 基准取最后 i low for j in range(low, high): if a[j] pivot: a[i], a[j] a[j], a[i] i 1 a[i], a[high] a[high], a[i] return i双指针法代码更短、边界更少、不容易写错我个人更推荐这个版本作为手写模板。注意它用的是a[j] pivot而不是用能让等于基准的元素留在右边配合最后把基准换到中间可以避免一部分极端情况。4.2 基准选择、小区间优化和三路快排基准选择决定了快排的下限。取第一个元素或最后一个元素为基准代码最省事但遇到已经有序的数组会立刻退化。取中间元素稍好一些但也能被构造出退化用例。工业界的标准做法是三数取中取low、mid、high三个位置的中位数作为基准。def median_of_three(a, low, high): mid low (high - low) // 2 # 这样写避免 lowhigh 溢出 if a[low] a[mid]: a[low], a[mid] a[mid], a[low] if a[low] a[high]: a[low], a[high] a[high], a[low] if a[mid] a[high]: a[mid], a[high] a[high], a[mid] a[mid], a[high - 1] a[high - 1], a[mid] # 把中位数藏到 high-1 位置 return a[high - 1]这里有个小技巧值得记把选好的中位数换到high - 1的位置因为low一定比它小、high一定比它大后续分区的循环边界就可以直接跳过这两端减少比较次数。这是《数据结构与算法分析》里推荐的写法。小区间优化。递归到子数组长度很小的时候快排的函数调用开销开始超过排序本身的开销。所以标准做法是当子数组长度小于某个阈值常见是 16 或 32时直接调用插入排序然后返回。def quick_sort(a, low, high): while low high: if high - low 1 16: insertion_sort_range(a, low, high) return p partition(a, low, high) quick_sort(a, low, p - 1) low p 1 # 尾递归优化: 右半用循环处理, 减小递归深度注意最后那行low p 1。这是尾递归优化对右半部分不再递归调用而是用循环继续处理这样递归深度从最坏的 O(n) 降到了 O(log n) 量级。加上每次先递归较短的一边的写法可以把栈深度稳定压在 O(log n)。这个优化在实际服务里很重要我见过线上因为快排递归过深导致栈溢出的案例日志里就是一堆重复的 quickSort 栈帧。三路快排是为了解决大量重复元素这个场景。普通分区遇到一堆相同值时分区做得极不平衡可能退化成 O(n²)。三路快排把数组分成 pivot、 pivot、 pivot三段等于基准的那段直接不用再排了。def quick_sort_3way(a, low, high): if low high: return pivot a[low] lt, i, gt low, low 1, high while i gt: if a[i] pivot: a[lt], a[i] a[i], a[lt] lt 1 i 1 elif a[i] pivot: a[i], a[gt] a[gt], a[i] gt - 1 else: i 1 quick_sort_3way(a, low, lt - 1) quick_sort_3way(a, gt 1, high)具体点说如果数组是[3,3,3,3,...,3,1]这种形态两路分区每次只能确定一个元素的位置要递归 n 次三路快排一趟就把所有 3 归位到中间只需要处理那个 1差距非常明显。这个算法也叫荷兰国旗问题是算法题里的高频考点。4.3 快排究竟在什么时候退化成 O(n²)想清楚这个问题比背结论重要。快排的复杂度取决于递归树的高度。如果每次分区都能把数组对半分树高是 log n每层总比较次数是 n总复杂度 O(n log n)。如果每次都分成 1 和 n-1树高就是 n每层还是 n 次比较总复杂度 O(n²)。具体触发退化的场景有两个一是数据已经有序或逆序而基准取的是首元素或尾元素二是数据里有大量重复元素而用的是两路分区。第一个问题用三数取中或随机化基准解决第二个问题用三路快排解决。另外还有一个隐蔽的坑数据是近似有序的比如已经排过一遍、只改了几个元素的数据如果基准选得不好也会触发退化。所以我现在写快排的默认配置是三数取中 小区间插入 尾递归优化这三个加起来基本能挡住绝大多数退化场景。5. 堆排序与桶族一个靠结构一个靠分布剩下四个算法分两类。堆排序是比较类排序里唯一一个最坏也是 O(n log n) 且空间 O(1)的算法很硬核计数、桶、基数三个是非比较排序它们能不能用完全取决于数据分布用对了非常快用错了比冒泡还惨。5.1 堆的下标关系和建堆为什么是 O(n)堆排序的基础是完全二叉树的数组表示。下标从 0 开始的话节点 i 的左孩子是2i1右孩子是2i2父节点是(i-1)/2。这个映射关系一定要记牢因为堆排序的代码全是下标运算写错一个就全乱。堆排序分两步。第一步建堆从最后一个非叶子节点下标n/2 - 1开始依次向前对每个节点做下沉操作保证每个节点都不小于它的孩子。第二步排序反复把堆顶最大值和末尾元素交换然后缩小堆的范围对堆顶做一次下沉。public static void heapSort(int[] a) { int n a.length; for (int i n / 2 - 1; i 0; i--) { siftDown(a, i, n); } for (int i n - 1; i 0; i--) { int t a[0]; a[0] a[i]; a[i] t; siftDown(a, 0, i); } } private static void siftDown(int[] a, int i, int size) { while (true) { int l 2 * i 1, r 2 * i 2, largest i; if (l size a[l] a[largest]) largest l; if (r size a[r] a[largest]) largest r; if (largest i) break; int t a[i]; a[i] a[largest]; a[largest] t; i largest; } }建堆是 O(n) 而不是 O(n log n)这个结论经常被误解。每个节点下沉一次看起来最多 log n 步n 个节点就是 O(n log n)。但真实情况是越靠近底层的节点越多而它们的下沉深度越浅。具体说高度为 h 的节点大约有 n/2^(h1) 个每个最多下沉 h 步把它们乘起来求和结果收敛到 O(n)。这个推导过程值得自己动手算一遍算过一次就再也不会忘。相反如果是从空堆开始逐个插入元素每次插入是 O(log n)那才是真的 O(n log n)。堆排序的工程价值在于它是唯一没有最坏情况陷阱的原地比较排序。快排怕退化归并要额外空间堆排序两样都不怕代价是常数因子偏大、缓存不友好访问下标跳跃实际跑起来常常比快排慢一截。另外堆结构本身比堆排序更有价值求 Top K 大元素用大小为 K 的小顶堆求中位数用一个大顶堆加一个小顶堆这些都是堆的应用比手写堆排序要常用得多。5.2 计数排序范围小的时候它是降维打击计数排序的思路是用值当下标。先扫一遍数组统计每个值出现的次数然后按值的顺序把元素填回去。它不做任何比较所以能突破 O(n log n) 的下限达到 O(n k)k 是值的范围。def counting_sort(a): if not a: return a lo, hi min(a), max(a) size hi - lo 1 count [0] * size for x in a: count[x - lo] 1 for i in range(1, size): # 前缀和, 变成最后一个位置 count[i] count[i - 1] res [0] * len(a) for x in reversed(a): # 倒序遍历, 保证稳定性 count[x - lo] - 1 res[count[x - lo]] x return res代码里有三个容易错的地方。第一偏移量的处理数组里可能有负数直接用值当下标会崩所以统一减去最小值lo做偏移。这个问题在面试里很常见很多人写完才发现负数处理不了。第二倒序遍历保证稳定性填回结果数组时从后往前扫这样相同值的元素中原数组里靠后的会放在后面相对顺序保持不变。如果正序遍历稳定性就没了。第三空间是 O(k) 不是 O(n)当值域 k 远大于 n 时比如数组里只有 10 个数但是最大值是 10 亿直接开 10 亿的数组显然不行。所以计数排序的适用条件很明确数据范围小且相对集中。比如统计考试成绩0 到 100、统计年龄0 到 150、统计某个区间内的整数这种场景用计数排序比快排快一个数量级。值域大就不合适了得换基数排序。5.3 基数排序与桶排序从低位到高位的分配收集基数排序解决的就是值域太大的问题。它不直接按整个值排序而是按每一位来排先按个位排再按十位排再按百位排直到最高位。因为每一轮用的都是稳定排序通常是计数排序所以低位排好的顺序会被高位保留最终结果是正确的。原始: [170, 45, 75, 90, 802, 24, 2, 66] 按个位分桶: 桶0: 170, 90 桶2: 802, 2 桶4: 24 桶5: 45, 75 桶6: 66 收集后: [170, 90, 802, 2, 24, 45, 75, 66] 按十位分桶: 桶0: 802, 2 桶4: 45 桶6: 66 桶7: 170, 75 桶9: 90 收集后: [802, 2, 24, 45, 66, 170, 75, 90] 按百位分桶: 桶0: 2, 24, 45, 66, 75, 90 桶1: 170 桶8: 802 收集后: [2, 24, 45, 66, 75, 90, 170, 802]def radix_sort(a): if not a: return a max_val max(a) exp 1 while max_val // exp 0: buckets [[] for _ in range(10)] for x in a: buckets[(x // exp) % 10].append(x) a [x for b in buckets for x in b] exp * 10 return a基数排序的稳定性要求是刚性的。因为低位排序的结果必须被保留如果某一位的排序不稳定前面几轮的工作就全白做了。它用的是 LSD从低位到高位方案适合整数和定长字符串。复杂度 O(d(nk))d 是最大值的位数。桶排序的思路介于归并和计数之间按值域把数据分成若干个区间桶每个桶内部再用其他排序算法排最后把桶按顺序拼起来。它的性能对数据分布极度敏感——数据均匀分布时每桶元素数量接近复杂度接近 O(n)数据全挤在一个桶里就退化成桶内排序的复杂度最坏 O(n²)。现实中桶排序用得不多主要是它需要事先知道数据的分布但基数排序可以看成桶排序的特例桶的数量固定为 10按位分配理解了这层关系两者的边界就清楚了。6. 工程选型把算法用对比会写更重要到这十个算法都讲完了但真正的难点在于什么场景用哪个。我在实际项目里见过的排序相关性能问题九成不是算法写错了而是选错了。6.1 主流语言内置排序用的都是混合算法不要自己手写排序去处理业务数据这是第一条经验。各大语言的标准库已经把混合算法的优势发挥到极致语言/方法底层算法稳定性说明JavaArrays.sort(int[])双轴快速排序不稳定基本类型不需要稳定, 追求速度JavaArrays.sort(Object[])TimSort稳定对象排序需要保留相对顺序JavaCollections.sortTimSort稳定委托给Arrays.sort(Object[])Pythonsorted/list.sortTimSort稳定归并插入, 专为真实数据优化Cstd::sortintrosort不稳定快排堆排插入, 三者混用Cstd::stable_sort归并排序稳定需要稳定时显式调用这里面的设计思路很值得琢磨。TimSort 的核心洞察是真实数据往往已经部分有序它会先在数组里找连续递增或严格递减的段叫 run把递减段直接反转然后用归并的方式把各个 run 合起来。对部分有序的真实数据它比纯快排快很多。而introsort 的核心是防退化先用快排当递归深度超过2 * log n时自动切换成堆排序避免最坏情况小区间再切换成插入排序。三个算法各管一段这才是工程级的答案。6.2 手写排序时的高频坑清单即便是为了面试或笔记手写也有几个坑必须提前知道。我把它们在下面列全这些都是我在实际调试中踩过的mid的计算要防溢出。(low high) / 2在 low 和 high 都很大时会溢出成负数正确写法是low (high - low) / 2。这个坑在归并排序和快排里都要注意。递归的终止条件写错。快排里写if (low high) return;而不是if (low high)因为 low 有可能大于 high空区间。用更安全。快排的左右先后顺序。挖坑法配最左基准时必须先动右指针这一点前面强调过是最高频的错误。归并排序的临时数组反复创建。递归里每次都new int[n]会造成大量 GC 压力正确做法是在递归外面创建一个和原数组等大的临时数组通过参数传进去复用。稳定性相关的比较符号。插入排序用a[j] key归并合并用left[i] right[j]这两处符号写反就会破坏稳定性而且排序结果看起来还是对的极难发现。要排序的是对象数组还是基本类型。如果排序的是自定义对象一定要明确是否需要稳定排序需要就用归并或者想办法把比较键扩展成多级 key别指望不稳定的快排。6.3 从排序延伸出去的几个高频考点排序是很多算法的地基往下延伸能牵出一串高频问题这也是我建议把排序学扎实的原因。求第 K 大元素用快排的分区思想不需要完整排序。每次分区后看基准的位置 p如果 p 正好是 K-1答案就是它如果 p 比 K-1 大就在左半找否则在右半找。平均复杂度 O(n)这叫快速选择算法。**求最大的 K 个元素Top K**用大小为 K 的小顶堆。遍历数组堆不满就插入堆满后比较堆顶比堆顶大就替换堆顶再下沉。总复杂度 O(n log K)比完整排序 O(n log n) 快尤其在 n 很大 K 很小的时候优势明显。这个模式在处理海量日志、排行榜时非常常用。统计逆序对数量用归并排序。在合并两个有序段时如果右半的元素先被取出说明它比左半剩下的所有元素都小此时左半剩余元素个数就是这批逆序对的数量。这个技巧只在归并的合并步骤里加两行代码非常巧妙。外部排序前面提过核心是多路归并是处理超大数据集的基础套路。我在实际使用中的体会是这十个算法的真正价值不在于能默写出来而在于它们提供了五套不同的思维工具交换的思维、插入的思维、选择的思维、分治的思维、按分布组织的思维。后面遇到的很多问题比如调度、聚合、去重本质上都能映射回某一个排序的思路上去。最后分享一个练习方法拿同一组十万条随机数据把这十个算法都跑一遍并打印耗时再换成已经基本有序和大量重复两种数据各跑一遍你会对每一栏参数产生实感这比看十遍表格都管用。 十大排序算法详解：从原理到实战选型
写业务代码这些年真正从头手写排序的次数一只手数得过来但每次被问到、每次要调优一段跑得慢的代码最后拼的都是这十个算法里攒下的底子。冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数——十个名字背后其实是五类截然不同的思路交换、插入、选择、分治、桶思想。很多人背下了复杂度和代码模板却说不清为什么快排要比归并快为什么 Java 对基本类型和对象用了两套排序为什么明明有库函数还要自己写。这篇笔记我按数据怎么动这条线把十大排序算法重新捋一遍每个算法给算法思想、给能看懂的文字图解、给可直接跑的代码重点讲清工程里真正会踩的坑基准怎么取、边界怎么写、什么时候快排会退化成 O(n²)、稳定性在什么场景下会咬你一口。适合正在准备数据结构与算法笔记的同学也适合写了几年代码想把底层逻辑补回来的开发者。读完之后你至少应该能做到三件事看到一组数据能立刻判断该用哪个算法、能手写快排和归并不出错、能解释每个优化点的来龙去脉。1. 按数据是怎么移动的把十个算法分成五族大多数人记排序算法是靠口诀硬背背完就忘。我自己的经验是先记住数据在数组里是怎么挪位置的剩下的一切都能推出来。这一层想通了复杂度、稳定性、适用场景基本都是自然结论不需要单独背。1.1 五族分类交换、插入、选择、分治、桶交换族冒泡排序、快速排序。核心动作是把两个元素对调直到所有逆序对消失。冒泡是相邻交换快排是远距离交换——这个差别直接决定了两者一个是 O(n²)一个是 O(n log n)。插入族直接插入排序、希尔排序。核心动作是把一个元素插到前面已经有序的序列里合适的位置。希尔排序就是带步长的插入排序先让远距离的元素有序减少后面的搬移量。选择族简单选择排序、堆排序。核心动作是每一轮从待排区域里挑出最值放到已排区域的末端。堆排序之所以快是因为它用堆结构把挑最值从 O(n) 降到了 O(log n)。分治族归并排序。核心动作是先切半、各自排好、再合并。它的贵在于要额外空间稳在于合并过程天然稳定。桶族计数排序、桶排序、基数排序。这三个是不比较元素大小的排序靠把元素丢进对应的桶完成。它们的下限能突破 O(n log n)代价是对数据分布有要求。把这五族记住你会发现面试官问快排和归并的区别本质上是在问交换族和分治族的取舍问堆排序和选择排序的关系就是在问选择族里 O(n) 挑选怎么变成 O(log n)。用族的概念去组织记忆比零散地背十个算法牢固得多。1.2 十大排序算法速查表下面这张表我建议直接抄进笔记首页它是所有讨论的起点。表里的平均时间复杂度、最坏情况、空间、稳定性四项是选型时最先看的指标。算法平均时间最坏时间最好时间空间稳定性是否比较冒泡排序O(n²)O(n²)O(n)O(1)稳定是选择排序O(n²)O(n²)O(n²)O(1)不稳定是插入排序O(n²)O(n²)O(n)O(1)稳定是希尔排序O(n^1.3)O(n²)O(n)O(1)不稳定是归并排序O(n log n)O(n log n)O(n log n)O(n)稳定是快速排序O(n log n)O(n²)O(n log n)O(log n)不稳定是堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定是计数排序O(n k)O(n k)O(n k)O(k)稳定否桶排序O(n k)O(n²)O(n)O(n k)稳定否基数排序O(d(n k))O(d(n k))O(d(n k))O(n k)稳定否表里有几个容易被忽略的细节值得单独拎出来说。快排的空间复杂度不是 O(1)虽然它没有额外开数组但递归调用栈要占 O(log n)最坏情况下递归深度到 n栈空间就是 O(n)。希尔排序的最好情况是 O(n)因为当数组已经基本有序时插入排序本身就接近线性。桶排序的最坏情况是 O(n²)这个反直觉——如果有人故意把数据全塞进同一个桶那就退化成了桶内做插入排序等于什么都没优化。1.3 稳定性不是学术概念它会实实在在咬你一口稳定性的定义是对于值相等的两个元素排序后它们的相对次序保持不变。为什么这件事重要举个最常见的业务场景——电商列表先按销量降序排再按价格升序排。如果用的是不稳定的排序第二次排序会把第一次排好的销量顺序打乱结果就是同价格的商品销量顺序乱了。用稳定排序就不会有这个问题因为价格相同的元素会保留上一轮的销量顺序。再比如 Python 里对一组元组排序sorted(data, keylambda x: x[2])Python 用的是 TimSort归并插入的混合算法是稳定排序所以相同 key 的记录会保持原有顺序。这个特性在数据处理里非常有用等于免费拿到多级排序的能力。反过来Java 的Arrays.sort(int[])用的是双轴快速排序不稳定而Arrays.sort(Object[])用的是 TimSort稳定。同一门语言里两套策略背后的考量就是基本类型不需要区分相等的两个 3而对象可能需要。顺着这个思路去理解为什么要分成两套实现比死记结论强。2. 冒泡、选择、插入入门三件套的真实差距这三个算法代码最短但恰恰是被讲得最浅的。很多人的笔记里三者的区别只有复杂度一样、写法不同。实际上它们的常数因子、对数据初始状态的敏感度、以及能不能在线处理差别非常大。2.1 冒泡排序提前退出优化才是它唯一的价值冒泡排序的算法思想很直观每一轮从头到尾比较相邻两个元素逆序就交换一轮下来最大的元素就冒到了末尾。如果写成硬循环它永远是 O(n²)没有任何亮点。真正值得学的是那个提前退出的优化。def bubble_sort(a): n len(a) for i in range(n - 1): swapped False for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] swapped True if not swapped: # 这一轮没有任何交换说明已经有序 break return a加上swapped标记之后对已经有序的数组冒泡排序只需要跑一轮就能退出时间复杂度降到 O(n)。这里有个细节很多人会写错swapped必须定义在外层循环内部每轮重置一次如果定义在外面第二轮之后就再也不会为真提前退出会失效。还有一个更进一步的优化思路记录每一轮最后一次交换发生的位置因为这个位置之后的元素已经有序了下一轮只需要扫到这个位置就行。不过说实话冒泡排序交换次数等于数组的逆序对数量这个性质在统计数据有多乱时挺有用但拿它来实际排序性能上真的没有竞争力。我个人的态度是冒泡排序是用来理解排序的教具写业务代码时不要用它。2.2 选择排序为什么它天生不稳定选择排序的思路是每一轮在未排序区间里找最小值和未排序区间的第一个元素交换。找最小值是 O(n)做 n 轮所以无论如何都是 O(n²)最好最坏都一样不受数据初始状态影响。代码大概是这样public static void selectionSort(int[] a) { int n a.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) { minIdx j; } } if (minIdx ! i) { int t a[i]; a[i] a[minIdx]; a[minIdx] t; } } }它不稳定的原因就藏在交换这个动作里。举个例子数组是[5, 5, 2]第一轮找到的最小值是 2位置在索引 2把它和索引 0 的 5 交换数组变成[2, 5, 5]——原来的第一个 5 跑到后面去了两个 5 的相对顺序变了。同样是 O(n²)插入排序稳定而选择排序不稳定差别就在于插入排序用的是逐个后移后移不会改变相等元素的相对位置。选择排序唯一的优势是交换次数最少最多交换 n-1 次。如果排序对象的交换成本极高比如大结构体选择排序有它的用武之地。但这种场景现在基本被指针排序覆盖了所以它的实际用途也很有限。2.3 插入排序小数组里的隐形冠军插入排序的思路是把手里的牌一张张插到合适位置。它的复杂度分析特别有意思元素如果离它最终位置很近搬移量就小。数组越接近有序插入排序越快完全有序时它是 O(n)。def insertion_sort(a): for i in range(1, len(a)): key a[i] j i - 1 while j 0 and a[j] key: a[j 1] a[j] j - 1 a[j 1] key return a注意while里用的是a[j] key而不是这个符号直接决定了稳定性用时相等的元素不会被搬走插入到相等元素后面保持稳定用就会把相等元素往前插破坏稳定性。这是个很小的细节但面试里被问你怎么保证插入排序是稳定的答案就是这个比较符号。插入排序真正重要的地位在于它是所有工业级排序算法的收尾选手。Python 的 TimSort、Java 的 TimSort、C 的 introsort在数组被切到很小通常是 16 到 32 个元素之后都会切换成插入排序。原因是插入排序常数项小没有函数调用开销对小数组比快速排序还快。这个阈值不是随便定的常见取值是 16可以在 JDK 源码里看到INSERTION_SORT_THRESHOLD 32这样的常量。理解这一点比单纯记住插入排序是 O(n²)有价值得多——在真实工程里插入排序每天都在被高频调用。3. 希尔与归并两条跳出 O(n²) 的路从这一节开始我们进入真正有工程价值的算法。希尔排序是插入排序的加强版归并排序是分治思想的代表作它们代表了两种完全不同的破局思路。3.1 希尔排序给插入排序装上一个放大镜插入排序慢在哪慢在每次只能挪一格如果一个小元素在数组末尾它要挪 n 步才能到前面。希尔排序的想法就是先用一个大的步长gap把元素分成若干组组内做插入排序让小的元素能跨大步往前走然后逐步缩小 gap最后 gap1 时做一次普通插入排序。因为此时数组已经基本有序了最后这一趟会非常快。文字图解一下对[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]走 gap5 的过程分组下标相差 5 的在一组: 组1: 8, 3 - 3, 8 组2: 9, 5 - 5, 9 组3: 1, 4 - 1, 4 组4: 7, 6 - 6, 7 组5: 2, 0 - 0, 2 一轮后: [3, 5, 1, 6, 0, 8, 9, 4, 7, 2] 可以看到最小的 0 已经从末尾跑到第 5 位一步跨了 5 格。def shell_sort(a): n len(a) gap 1 while gap n // 3: # Knuth 增量序列: 1, 4, 13, 40, ... gap gap * 3 1 while gap 1: for i in range(gap, n): key a[i] j i - gap while j 0 and a[j] key: a[j gap] a[j] j - gap a[j gap] key gap // 3 return a增量序列的选择直接决定性能。经典的希尔增量n/2, n/4, ..., 1最坏能退化到 O(n²)Knuth 的3h1序列可以把平均复杂度压到 O(n^1.5) 左右还有更激进的 Sedgewick 序列能把最坏情况压到 O(n^(4/3))。我在笔记里习惯把希尔排序的复杂度写成约 O(n^1.3)取决于增量序列因为给一个确定的数字是不严谨的。希尔排序不稳定原因和插入排序一样——它是跨步长移动的两个相等的元素可能因为分在不同的组里被调换顺序。这一点在面试里经常被追问值得记住。3.2 归并排序先切再合合并是灵魂归并排序的分治三部曲分解——把数组从中间切成两半解决——递归地对两半分别排序合并——把两个有序数组合并成一个有序数组。前两步是递归框架真正干活的是第三步。合并两个有序数组的过程用文字图解最清楚。假设左半是[1, 5, 9]右半是[2, 6, 7]i0(指1) j0(指2) 结果[] 比较 1 2 - 取 1, i 后移 结果[1] 比较 5 2 - 取 2, j 后移 结果[1,2] 比较 5 6 - 取 5, i 后移 结果[1,2,5] 比较 9 6 - 取 6, j 后移 结果[1,2,5,6] 比较 9 7 - 取 7, j 后移 结果[1,2,5,6,7] 右边耗尽, 左半剩余整体接上 结果[1,2,5,6,7,9]def merge_sort(a): if len(a) 1: return a mid len(a) // 2 left merge_sort(a[:mid]) right merge_sort(a[mid:]) return merge(left, right) def merge(left, right): res [] i j 0 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合并时left[i] right[j]里的等号是稳定性的关键当两边元素相等时优先取左边的左边本来就在前面相对顺序得以保持。如果把等号去掉写成右半相等元素就会抢先稳定性就没了。这个细节在很多教程里被省略但恰恰是面试的常考点。3.3 归并的空间换时间和它在链表、外部排序里的独特地位归并排序的代价很直白每次合并都要开一个临时数组空间 O(n)。这是它输给快排的主要原因。但它在两个场景里无可替代。第一个场景是链表排序。数组的归并需要额外空间因为合并时要同时保存两段数据而链表的节点可以随时改指针合并两个有序链表只需要 O(1) 的额外空间直接原地串起来就行。所以LeetCode 148. 排序链表的标准解法就是归并排序快排反而不好写——链表没有随机访问快排找基准和分区的效率都很差。第二个场景是外部排序。当数据大到内存放不下时思路是把大文件切成若干能塞进内存的块每块内部排序后写回磁盘得到若干个有序的小文件然后再用多路归并把它们合并成一个大文件。整个流程的核心就是归并这是数据库和大数据处理里的基础操作。理解了这一层你就能明白为什么归并排序在数据量超过内存的场景下依然不可替代。还有一点值得提归并排序是唯一一个稳定且最坏情况也是 O(n log n)的比较类排序。快排最坏是 O(n²)堆排序不稳定计数类排序有适用范围。要求稳定 最坏 O(n log n) 不挑数据只有归并满足。Java 里对对象排序用 TimSort 而不是快排本质就是这个考量。4. 快速排序被用得最多也被问得最细快排是十个算法里被问得最多的一个因为它的工程实践最复杂分区怎么写、基准怎么取、重复元素怎么处理、什么时候会退化每一个点都能展开讲半小时。它也是我见过的代码看起来对、实际有 bug发生率最高的算法。4.1 分区的两种写法挖坑法和双指针快排的核心是分区partition选一个基准值 pivot把数组分成左边全小于等于 pivot、右边全大于等于 pivot两部分然后对两部分递归。挖坑法的思路是先把基准值取出来存起来基准位置就成了第一个坑从右边找一个比基准小的数填进左边的坑这个数的原位置变成新坑再从左边找一个比基准大的数填进右边的坑如此往复直到左右指针相遇把基准值填进最后的坑。public static void quickSort(int[] a, int low, int high) { if (low high) return; int pivot a[low]; // 挖出第一个坑 int i low, j high; while (i j) { while (i j a[j] pivot) j--; // 从右往左找比基准小的 if (i j) a[i] a[j]; // 填左坑, 右位置成新坑 while (i j a[i] pivot) i; // 从左往右找比基准大的 if (i j) a[j--] a[i]; // 填右坑 } a[i] pivot; // 基准归位 quickSort(a, low, i - 1); quickSort(a, i 1, high); }这段代码有两个高频错误点我当年都踩过。第一个是右边先走还是左边先走的问题。用挖坑法且基准取最左边时必须先动右指针。原因是如果先动左指针最后相遇的位置可能是一个比基准大的元素把它和基准交换后左边就出现了比基准大的值分区就错了。第二个是内层while里的i j判断不能省否则数组里有大量重复元素时指针会越界。双指针法也叫前后指针法是另一种思路用一个i表示小于等于基准区域的右边界用j从左到右扫描遇到比基准小的就把它换到i的位置并让i前进。def partition(a, low, high): pivot a[high] # 基准取最后 i low for j in range(low, high): if a[j] pivot: a[i], a[j] a[j], a[i] i 1 a[i], a[high] a[high], a[i] return i双指针法代码更短、边界更少、不容易写错我个人更推荐这个版本作为手写模板。注意它用的是a[j] pivot而不是用能让等于基准的元素留在右边配合最后把基准换到中间可以避免一部分极端情况。4.2 基准选择、小区间优化和三路快排基准选择决定了快排的下限。取第一个元素或最后一个元素为基准代码最省事但遇到已经有序的数组会立刻退化。取中间元素稍好一些但也能被构造出退化用例。工业界的标准做法是三数取中取low、mid、high三个位置的中位数作为基准。def median_of_three(a, low, high): mid low (high - low) // 2 # 这样写避免 lowhigh 溢出 if a[low] a[mid]: a[low], a[mid] a[mid], a[low] if a[low] a[high]: a[low], a[high] a[high], a[low] if a[mid] a[high]: a[mid], a[high] a[high], a[mid] a[mid], a[high - 1] a[high - 1], a[mid] # 把中位数藏到 high-1 位置 return a[high - 1]这里有个小技巧值得记把选好的中位数换到high - 1的位置因为low一定比它小、high一定比它大后续分区的循环边界就可以直接跳过这两端减少比较次数。这是《数据结构与算法分析》里推荐的写法。小区间优化。递归到子数组长度很小的时候快排的函数调用开销开始超过排序本身的开销。所以标准做法是当子数组长度小于某个阈值常见是 16 或 32时直接调用插入排序然后返回。def quick_sort(a, low, high): while low high: if high - low 1 16: insertion_sort_range(a, low, high) return p partition(a, low, high) quick_sort(a, low, p - 1) low p 1 # 尾递归优化: 右半用循环处理, 减小递归深度注意最后那行low p 1。这是尾递归优化对右半部分不再递归调用而是用循环继续处理这样递归深度从最坏的 O(n) 降到了 O(log n) 量级。加上每次先递归较短的一边的写法可以把栈深度稳定压在 O(log n)。这个优化在实际服务里很重要我见过线上因为快排递归过深导致栈溢出的案例日志里就是一堆重复的 quickSort 栈帧。三路快排是为了解决大量重复元素这个场景。普通分区遇到一堆相同值时分区做得极不平衡可能退化成 O(n²)。三路快排把数组分成 pivot、 pivot、 pivot三段等于基准的那段直接不用再排了。def quick_sort_3way(a, low, high): if low high: return pivot a[low] lt, i, gt low, low 1, high while i gt: if a[i] pivot: a[lt], a[i] a[i], a[lt] lt 1 i 1 elif a[i] pivot: a[i], a[gt] a[gt], a[i] gt - 1 else: i 1 quick_sort_3way(a, low, lt - 1) quick_sort_3way(a, gt 1, high)具体点说如果数组是[3,3,3,3,...,3,1]这种形态两路分区每次只能确定一个元素的位置要递归 n 次三路快排一趟就把所有 3 归位到中间只需要处理那个 1差距非常明显。这个算法也叫荷兰国旗问题是算法题里的高频考点。4.3 快排究竟在什么时候退化成 O(n²)想清楚这个问题比背结论重要。快排的复杂度取决于递归树的高度。如果每次分区都能把数组对半分树高是 log n每层总比较次数是 n总复杂度 O(n log n)。如果每次都分成 1 和 n-1树高就是 n每层还是 n 次比较总复杂度 O(n²)。具体触发退化的场景有两个一是数据已经有序或逆序而基准取的是首元素或尾元素二是数据里有大量重复元素而用的是两路分区。第一个问题用三数取中或随机化基准解决第二个问题用三路快排解决。另外还有一个隐蔽的坑数据是近似有序的比如已经排过一遍、只改了几个元素的数据如果基准选得不好也会触发退化。所以我现在写快排的默认配置是三数取中 小区间插入 尾递归优化这三个加起来基本能挡住绝大多数退化场景。5. 堆排序与桶族一个靠结构一个靠分布剩下四个算法分两类。堆排序是比较类排序里唯一一个最坏也是 O(n log n) 且空间 O(1)的算法很硬核计数、桶、基数三个是非比较排序它们能不能用完全取决于数据分布用对了非常快用错了比冒泡还惨。5.1 堆的下标关系和建堆为什么是 O(n)堆排序的基础是完全二叉树的数组表示。下标从 0 开始的话节点 i 的左孩子是2i1右孩子是2i2父节点是(i-1)/2。这个映射关系一定要记牢因为堆排序的代码全是下标运算写错一个就全乱。堆排序分两步。第一步建堆从最后一个非叶子节点下标n/2 - 1开始依次向前对每个节点做下沉操作保证每个节点都不小于它的孩子。第二步排序反复把堆顶最大值和末尾元素交换然后缩小堆的范围对堆顶做一次下沉。public static void heapSort(int[] a) { int n a.length; for (int i n / 2 - 1; i 0; i--) { siftDown(a, i, n); } for (int i n - 1; i 0; i--) { int t a[0]; a[0] a[i]; a[i] t; siftDown(a, 0, i); } } private static void siftDown(int[] a, int i, int size) { while (true) { int l 2 * i 1, r 2 * i 2, largest i; if (l size a[l] a[largest]) largest l; if (r size a[r] a[largest]) largest r; if (largest i) break; int t a[i]; a[i] a[largest]; a[largest] t; i largest; } }建堆是 O(n) 而不是 O(n log n)这个结论经常被误解。每个节点下沉一次看起来最多 log n 步n 个节点就是 O(n log n)。但真实情况是越靠近底层的节点越多而它们的下沉深度越浅。具体说高度为 h 的节点大约有 n/2^(h1) 个每个最多下沉 h 步把它们乘起来求和结果收敛到 O(n)。这个推导过程值得自己动手算一遍算过一次就再也不会忘。相反如果是从空堆开始逐个插入元素每次插入是 O(log n)那才是真的 O(n log n)。堆排序的工程价值在于它是唯一没有最坏情况陷阱的原地比较排序。快排怕退化归并要额外空间堆排序两样都不怕代价是常数因子偏大、缓存不友好访问下标跳跃实际跑起来常常比快排慢一截。另外堆结构本身比堆排序更有价值求 Top K 大元素用大小为 K 的小顶堆求中位数用一个大顶堆加一个小顶堆这些都是堆的应用比手写堆排序要常用得多。5.2 计数排序范围小的时候它是降维打击计数排序的思路是用值当下标。先扫一遍数组统计每个值出现的次数然后按值的顺序把元素填回去。它不做任何比较所以能突破 O(n log n) 的下限达到 O(n k)k 是值的范围。def counting_sort(a): if not a: return a lo, hi min(a), max(a) size hi - lo 1 count [0] * size for x in a: count[x - lo] 1 for i in range(1, size): # 前缀和, 变成最后一个位置 count[i] count[i - 1] res [0] * len(a) for x in reversed(a): # 倒序遍历, 保证稳定性 count[x - lo] - 1 res[count[x - lo]] x return res代码里有三个容易错的地方。第一偏移量的处理数组里可能有负数直接用值当下标会崩所以统一减去最小值lo做偏移。这个问题在面试里很常见很多人写完才发现负数处理不了。第二倒序遍历保证稳定性填回结果数组时从后往前扫这样相同值的元素中原数组里靠后的会放在后面相对顺序保持不变。如果正序遍历稳定性就没了。第三空间是 O(k) 不是 O(n)当值域 k 远大于 n 时比如数组里只有 10 个数但是最大值是 10 亿直接开 10 亿的数组显然不行。所以计数排序的适用条件很明确数据范围小且相对集中。比如统计考试成绩0 到 100、统计年龄0 到 150、统计某个区间内的整数这种场景用计数排序比快排快一个数量级。值域大就不合适了得换基数排序。5.3 基数排序与桶排序从低位到高位的分配收集基数排序解决的就是值域太大的问题。它不直接按整个值排序而是按每一位来排先按个位排再按十位排再按百位排直到最高位。因为每一轮用的都是稳定排序通常是计数排序所以低位排好的顺序会被高位保留最终结果是正确的。原始: [170, 45, 75, 90, 802, 24, 2, 66] 按个位分桶: 桶0: 170, 90 桶2: 802, 2 桶4: 24 桶5: 45, 75 桶6: 66 收集后: [170, 90, 802, 2, 24, 45, 75, 66] 按十位分桶: 桶0: 802, 2 桶4: 45 桶6: 66 桶7: 170, 75 桶9: 90 收集后: [802, 2, 24, 45, 66, 170, 75, 90] 按百位分桶: 桶0: 2, 24, 45, 66, 75, 90 桶1: 170 桶8: 802 收集后: [2, 24, 45, 66, 75, 90, 170, 802]def radix_sort(a): if not a: return a max_val max(a) exp 1 while max_val // exp 0: buckets [[] for _ in range(10)] for x in a: buckets[(x // exp) % 10].append(x) a [x for b in buckets for x in b] exp * 10 return a基数排序的稳定性要求是刚性的。因为低位排序的结果必须被保留如果某一位的排序不稳定前面几轮的工作就全白做了。它用的是 LSD从低位到高位方案适合整数和定长字符串。复杂度 O(d(nk))d 是最大值的位数。桶排序的思路介于归并和计数之间按值域把数据分成若干个区间桶每个桶内部再用其他排序算法排最后把桶按顺序拼起来。它的性能对数据分布极度敏感——数据均匀分布时每桶元素数量接近复杂度接近 O(n)数据全挤在一个桶里就退化成桶内排序的复杂度最坏 O(n²)。现实中桶排序用得不多主要是它需要事先知道数据的分布但基数排序可以看成桶排序的特例桶的数量固定为 10按位分配理解了这层关系两者的边界就清楚了。6. 工程选型把算法用对比会写更重要到这十个算法都讲完了但真正的难点在于什么场景用哪个。我在实际项目里见过的排序相关性能问题九成不是算法写错了而是选错了。6.1 主流语言内置排序用的都是混合算法不要自己手写排序去处理业务数据这是第一条经验。各大语言的标准库已经把混合算法的优势发挥到极致语言/方法底层算法稳定性说明JavaArrays.sort(int[])双轴快速排序不稳定基本类型不需要稳定, 追求速度JavaArrays.sort(Object[])TimSort稳定对象排序需要保留相对顺序JavaCollections.sortTimSort稳定委托给Arrays.sort(Object[])Pythonsorted/list.sortTimSort稳定归并插入, 专为真实数据优化Cstd::sortintrosort不稳定快排堆排插入, 三者混用Cstd::stable_sort归并排序稳定需要稳定时显式调用这里面的设计思路很值得琢磨。TimSort 的核心洞察是真实数据往往已经部分有序它会先在数组里找连续递增或严格递减的段叫 run把递减段直接反转然后用归并的方式把各个 run 合起来。对部分有序的真实数据它比纯快排快很多。而introsort 的核心是防退化先用快排当递归深度超过2 * log n时自动切换成堆排序避免最坏情况小区间再切换成插入排序。三个算法各管一段这才是工程级的答案。6.2 手写排序时的高频坑清单即便是为了面试或笔记手写也有几个坑必须提前知道。我把它们在下面列全这些都是我在实际调试中踩过的mid的计算要防溢出。(low high) / 2在 low 和 high 都很大时会溢出成负数正确写法是low (high - low) / 2。这个坑在归并排序和快排里都要注意。递归的终止条件写错。快排里写if (low high) return;而不是if (low high)因为 low 有可能大于 high空区间。用更安全。快排的左右先后顺序。挖坑法配最左基准时必须先动右指针这一点前面强调过是最高频的错误。归并排序的临时数组反复创建。递归里每次都new int[n]会造成大量 GC 压力正确做法是在递归外面创建一个和原数组等大的临时数组通过参数传进去复用。稳定性相关的比较符号。插入排序用a[j] key归并合并用left[i] right[j]这两处符号写反就会破坏稳定性而且排序结果看起来还是对的极难发现。要排序的是对象数组还是基本类型。如果排序的是自定义对象一定要明确是否需要稳定排序需要就用归并或者想办法把比较键扩展成多级 key别指望不稳定的快排。6.3 从排序延伸出去的几个高频考点排序是很多算法的地基往下延伸能牵出一串高频问题这也是我建议把排序学扎实的原因。求第 K 大元素用快排的分区思想不需要完整排序。每次分区后看基准的位置 p如果 p 正好是 K-1答案就是它如果 p 比 K-1 大就在左半找否则在右半找。平均复杂度 O(n)这叫快速选择算法。**求最大的 K 个元素Top K**用大小为 K 的小顶堆。遍历数组堆不满就插入堆满后比较堆顶比堆顶大就替换堆顶再下沉。总复杂度 O(n log K)比完整排序 O(n log n) 快尤其在 n 很大 K 很小的时候优势明显。这个模式在处理海量日志、排行榜时非常常用。统计逆序对数量用归并排序。在合并两个有序段时如果右半的元素先被取出说明它比左半剩下的所有元素都小此时左半剩余元素个数就是这批逆序对的数量。这个技巧只在归并的合并步骤里加两行代码非常巧妙。外部排序前面提过核心是多路归并是处理超大数据集的基础套路。我在实际使用中的体会是这十个算法的真正价值不在于能默写出来而在于它们提供了五套不同的思维工具交换的思维、插入的思维、选择的思维、分治的思维、按分布组织的思维。后面遇到的很多问题比如调度、聚合、去重本质上都能映射回某一个排序的思路上去。最后分享一个练习方法拿同一组十万条随机数据把这十个算法都跑一遍并打印耗时再换成已经基本有序和大量重复两种数据各跑一遍你会对每一栏参数产生实感这比看十遍表格都管用。