面试官让候选人讲讲八大排序算法很多人的第一反应是背快排模板。有一次我在技术面里问一个三年经验的候选人“快排最坏情况是什么”他答上来了接着问“为什么基本类型用快速排序、引用类型用归并排序”他愣住了。排序算法背后的本质理解远比默写模板重要。八大排序算法通常指冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序。这八个算法几乎覆盖了排序领域最重要的思想暴力枚举、插入优化、分治递归、堆结构、线性非比较。无论你是准备校招面试、社招跳槽还是在日常开发里优化一段数据流水线弄清楚它们都不是浪费时间。这篇内容我打算用文字版图解的方式把每个算法的“为什么”讲透为什么插入排序适合小数据、为什么快排平均最快、为什么堆排序明明O(n log n)却斗不过快排、为什么非比较排序能突破理论下限。每段都配核心代码和避坑提醒读完可以直接照着写、照着用。1. 排序算法不是背模板先看它解决的真实问题1.1 一次面试追问暴露的盲区那次面试结束后我和候选人又聊了十分钟。他说快排他能背但“为什么基本类型不直接用归并”这个问题从没想过。后来我给他拆了一下基本类型排序不在乎稳定性因为两个相同的int本身没有区别但对象排序如果先按A字段排、再按B字段排稳定性就成了刚性需求。JDK里的Arrays.sort对基本类型用Dual-Pivot QuickSort对对象用TimSort正是考虑这一点。这个例子说明排序算法不是一个“会写就行”的八股文而是一个需要结合数据规模、内存限制、稳定性要求、键值范围综合决策的工程问题。很多人花大量时间背代码却忽略了最核心的问题每个算法到底在优化什么牺牲了什么适用的边界在哪里1.2 八个算法分别解决了什么冒泡排序解决的是“最容易理解”的问题适合入门教学。选择排序解决了“减少交换次数”的问题。插入排序则抓住了“数据接近有序时效率极高”这个特性。希尔排序是插入排序对“远距离元素”的加速让元素可以大步跳跃。归并排序的核心是稳定且可预测的O(n log n)适合需要稳定性或链表结构。快速排序用原地分区把常数压到最低成为通用排序的默认选择。堆排序利用堆结构在O(1)空间下完成排序适合内存极紧张但需要可预测性能的场景。基数排序走的是另一条路——不比较大小而是按位分配把时间复杂度压到线性。把这八个算法放在一起看你会发现它们不是孤立的。冒泡是无效比较的典型选择是“每次挑最值”的朴素的极致插入是“局部有序”的利用希尔是“分治思想”的雏形归并和快排把分治用到极致堆排序用堆这种数据结构替代线性扫描基数排序彻底跳出比较排序框架。理解了这条演进线排序算法在你眼里就不再是一堆要背的模板而是一套解题思路。2. 复杂度全景先把八个算法的性能边界刻进直觉2.1 一张表看懂时间、空间与稳定性在写任何代码之前先把每个算法的复杂度边界刻进脑子里。下面的表是我自己整理时一直用的基准。排序算法平均时间最好时间最坏时间空间稳定性冒泡排序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~1.5)O(n log 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 log n)O(n²)O(log n)~O(n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定基数排序O(d(nk))O(d(nk))O(d(nk))O(nk)稳定我特意把最好、最坏、平均都列出来因为只看平均会漏掉很多关键信息。比如插入排序在最好情况下是O(n)这让它在处理“近乎有序”的数据时能吊打快排而快排最坏退化到O(n²)这是所有快排优化都要解决的问题。2.2 为什么稳定性和复杂度同样重要稳定性指的是如果两个元素的排序关键字相同排序后它们的相对顺序能否保持不变。能就说明这个排序稳定不能就不稳定。它之所以重要是因为现实里的数据往往带有多字段语义。举个例子先按订单金额排序再按下单时间排序。如果第二次排序用的是稳定排序那么金额相同的订单仍然会保持时间上的先后顺序但如果用不稳定排序之前按时间排好的关系就可能被打乱。这就是为什么Java对象排序要选稳定的归并思路而基本类型排序无所谓。再看空间复杂度。冒泡、选择、插入、希尔、堆都属于原地排序空间O(1)这在内存受限的嵌入式或移动端很关键。归并和基数都要额外开数组空间代价高。快排的空间复杂度虽然记作O(log n)但那是因为递归栈最坏情况下递归深度变成n空间就退化成O(n)。这些差异在真正处理大数据时往往比时间复杂度的常数更致命。3. 暴力美学三兄弟冒泡、选择、插入排序的细节与升级3.1 冒泡排序相邻交换与提前终止优化冒泡排序的思路很简单每一轮从左到右比较相邻元素如果左边比右边大就交换这样每轮结束最大的元素会“冒泡”到末尾。重复n-1轮数组就有序了。我用一组数据演示一下数组[5, 1, 4, 2, 8]第一轮比较5和1交换[1, 5, 4, 2, 8]比较5和4交换[1, 4, 5, 2, 8]比较5和2交换[1, 4, 2, 5, 8]比较5和8不交换[1, 4, 2, 5, 8]第一轮结束最大值8已经到末尾。第二轮从[1, 4, 2]里继续冒泡最终得到[1, 2, 4, 5, 8]。核心代码public void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped true; } } if (!swapped) { break; } } }这个swapped标志是最常用的优化。如果某一轮一次交换都没发生说明数组已经有序直接跳出循环。于是最好情况下一轮扫描就能结束复杂度降到O(n)。我见过很多人背模板时漏掉这个标志一旦遇到基本有序的输入性能会差很多。冒泡排序的缺点是元素交换太频繁。每一轮可能产生大量相邻交换而这些交换在数据基本有序时显得极其浪费。它真正适合的场景是数据量小、而且只是教学演示工程上很少直接用。3.2 选择排序每轮选最小的“胆小鬼”选择排序的思路更直接第一轮遍历整个数组找到最小值放到下标0第二轮遍历剩余元素找到最小值放到下标1以此类推。它的优势是交换次数少每轮只交换一次总共最多n-1次交换。但缺点是无论数组是否有序都要做完整的遍历所以最好情况和最坏情况都是O(n²)。用数组[5, 8, 5, 2]演示一轮先遍历全数组找到最小值2和下标0的元素5交换。数组变成[2, 8, 5, 5]。 注意这里有两个5原来的第一个5跑到了第二个5后面相对顺序被改变了。所以选择排序不稳定。写一个带“同时找最大和最小”的优化版本可以把轮次减半。每轮同时找最小值和最大值分别放到未排序区间的最前面和最后面。这个优化思路在面试里能加分但代码边界要小心容易越界。public void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } if (minIdx ! i) { int tmp arr[i]; arr[i] arr[minIdx]; arr[minIdx] tmp; } } }选择排序虽然时间复杂度不理想但它的思想很重要从无序区间里反复取最值这个思路是堆排序的雏形。如果你理解了选择排序再看堆排序会顺畅很多——堆排序不过是用堆这种数据结构把“找最小值”的O(n)扫描优化成了O(log n)。3.3 插入排序玩扑克牌式的高效短排序插入排序很像整理扑克牌。你左手拿着的牌已经有序右手摸到一张新牌就把它插入到左手中正确的位置。数组排序时我们维护一个“已排序区间”每次把当前元素往左移动直到找到合适的位置。它在工程里非常重要原因有两点第一对于小规模数据比如十几个元素插入排序的实现极简没有递归也没有额外数组常数非常小第二当数据接近有序时内层循环几乎不用移动复杂度逼近O(n)。这也是为什么快排和归并在递归到小数组时会切回插入排序而不是继续递归。代码实现public void insertionSort(int[] arr) { int n arr.length; for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }写插入排序最常犯的错误是忘记把key保存下来。如果你直接拿arr[j1] arr[j]去覆盖arr[i]的原始值就丢了。另一个容易忽略的细节是while条件里要带上j 0否则左边界检查会数组越界。3.4 三兄弟对比谁更适合当排序的“地基”这三个O(n²)排序在工程上不会单独用于大数据但它们是小规模数据、以及更复杂排序算法内部的基石。算法比较次数交换次数适合场景冒泡多多入门教学选择多少交换代价极高时插入数据有序时很少数据有序时很少小规模、近有序数据我最常用的是插入排序。它稳定、代码简单、对小数组和近有序数据表现极佳。在Timsort和快排的优化实现里小数组阈值通常是16或48低于这个值就直接用插入排序而不是继续递归或归并。4. 希尔排序插入排序的“跳步”逆袭4.1 从插入排序的软肋入手插入排序的问题在于每次只能把元素移动一个位置。如果数组是[8, 7, 6, 5, 4, 3, 2, 1]要把最后的1挪到最前面得经过7次移动。如果数据量到一万最坏情况需要约2500万次移动效率很低。希尔排序的思路是先让元素跳跃式移动而不是一步一步挪。它把数组按某个增量gap分成多个子序列对每个子序列做插入排序。这样做一轮之后整个数组会变得“大体有序”但距离最终有序还差一些然后缩小gap再分组排序最后gap变成1做一次标准插入排序收尾。这里的直觉是经过前面几轮跳跃排序数组已经接近有序而插入排序对接近有序的数组效率非常高所以最后一轮几乎不会浪费时间。4.2 增量分组排序的直观过程看一个有11个元素的数组假设gap5[49, 38, 65, 97, 76, 13, 27, 49, 55, 04, 87]间隔5分成组下标0和549和13下标1和638和27下标2和765和49下标3和897和55下标4和976和04对每组内部做插入排序后数组变成[13, 27, 49, 55, 04, 49, 38, 65, 97, 76, 87]可以看到13、27这些较小的元素一下子跳到了前面。接着gap缩小到2、1继续排序最终完成。这个过程用文字描述是“跳跃式插入”用代码写出来其实就是插入排序的外层嵌套一层gap循环。4.3 代码实现与增量序列选择public void shellSort(int[] arr) { int n arr.length; for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key arr[i]; int j i - gap; while (j 0 arr[j] key) { arr[j gap] arr[j]; j - gap; } arr[j gap] key; } } }这段代码和插入排序几乎一样只是把所有1换成了gap。外层控制gap从n/2开始不断减半直到1。内层对每个元素按照gap做一次局部插入。gap序列的选择对希尔排序的性能影响很大。用n/2每次减半最坏复杂度是O(n²)如果使用Hibbard序列1, 3, 7, 15...最坏可以到O(n^(3/2))更复杂的Sedgewick序列平均可以到O(n^(7/6))。工程上很少纠结gap序列因为通用排序有更好的选择。但在算法演进史上希尔排序是第一个突破O(n²)的排序算法它能让你明白“优化不是推翻重来而是找到瓶颈并放大优势”。希尔排序是不稳定的。因为在分组排序时相同元素可能处于不同组或者在同组内被跨越式移动导致相对顺序无法保证。这一点在需要稳定性的场景里是硬伤。5. 分治双雄归并排序与快速排序的完整拆解5.1 归并排序稳定且预判性极强的分治典范归并排序的思想是分治三步走分解把数组从中间劈成两半递归排序对左右两半分别排序合并把两个有序数组合并成一个有序数组。它的好处有三个第一时间复杂度稳定在O(n log n)不管输入是什么样都不会退化第二稳定性好合并时只要遇到左边元素小于等于右边元素就优先取左边相同元素相对顺序就能保住第三非常适合链表排序因为对链表做二分归并不会像数组那样需要大块连续空间。代价是需要额外O(n)的辅助空间。每次合并要创建一个临时数组如果递归里频繁创建性能会很难看。实际工程中会复用同一个临时数组用下标控制区间避免反复分配和GC压力。public void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid left ((right - left) 1); mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } private void merge(int[] arr, int left, int mid, int right) { int[] tmp new int[right - left 1]; int i left; int j mid 1; int k 0; while (i mid j right) { if (arr[i] arr[j]) { tmp[k] arr[i]; } else { tmp[k] arr[j]; } } while (i mid) { tmp[k] arr[i]; } while (j right) { tmp[k] arr[j]; } for (int p 0; p tmp.length; p) { arr[left p] tmp[p]; } }合并时最容易出两个bug一个是漏掉两个while里残留元素的处理数组会丢数据另一个是递归边界写成left right导致单元素数组无限递归。我建议你在写完后用长度为0、1、2的边界数组快速自测一下很多问题一眼就能看出来。归并排序还有一个常见变种自底向上的迭代归并从长度为1的子数组开始两两归并再四四归并最后合成完整数组。这种写法避免了递归栈开销也是外部排序中常用的分块思想。5.2 快速排序原地分区的实战之王快速排序也是分治但它和归并的路线不同。快排的核心是“分区”选一个pivot基准值把小于pivot的元素放到左边大于pivot的放到右边然后递归处理左右两部分。分区完成后pivot已经处于最终位置。这个过程不需要额外的大块数组所有交换都在原数组内部完成。正因为操作少、缓存友好快排的平均常数远小于归并排序。最常见的分区方式是Lomuto分区选最后一个元素作为pivot用两个指针扫描。实现简单适合教学。public void quickSort(int[] arr, int left, int right) { if (left right) { return; } int pivotIdx partition(arr, left, right); quickSort(arr, left, pivotIdx - 1); quickSort(arr, pivotIdx 1, right); } private int partition(int[] arr, int left, int right) { int pivot arr[right]; int i left; for (int j left; j right; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, right); return i; }这个写法在面试里最容易被追问为什么最后要把pivot换到i因为i左边的元素都小于pivot右边都大于等于pivot把pivot和arr[i]交换后pivot就正好落在“最终位置”上。快排最大的坑是退化。如果每次选的pivot恰好是当前区间的最小值或最大值分区极不平衡递归树会退化成长链时间复杂度变成O(n²)递归深度变成n空间也变成O(n)。比如对一个已经有序的数组如果用最后一个元素当pivot且没有做任何处理就会发生这种灾难。解决办法有几种随机选pivot打破最坏输入的可构造性三数取中取left、mid、right三个位置的中间值当pivot能有效应对接近有序的数组当递归区间小于阈值时切到插入排序双路快排、三路快排能改善大量重复元素时的性能。Java的Arrays.sort对基本类型用的是双轴快排实际上就是把区间分成三段比两路分区更能应对重复元素。5.3 分治双雄的适用边界与JDK选择归并和快排没有绝对的优劣只有是否匹配场景。归并在需要稳定性、链表结构、数据无法全部载入内存时更适合。外部排序几乎都基于归并把大文件切块每块排序后写入磁盘再用多路归并合成结果。而快排在原地排序、缓存利用率、平均性能上更强所以绝大多数通用排序库的默认选择都是快排。JDK的取舍非常典型Arrays.sort(int[])用Dual-Pivot QuickSortArrays.sort(Object[])用TimSort。前者不考虑稳定性后者必须稳定。这正好回答了我开头说的那个面试题。6. 堆排序用二叉树思想优化选择排序6.1 从选择排序到堆排序的进化选择排序每轮要扫描整个数组找最小值这是O(n)的操作整体复杂度因此变成O(n²)。堆排序的思路是用一个大顶堆来维护数组中最大的元素堆顶就是最大值把它和末尾交换然后缩小堆范围、向下调整堆。这样“找最大值”就从O(n)降到了O(log n)。堆在数组里的表示很巧妙对于下标i它的左孩子是2*i1右孩子是2*i2父节点是(i-1)/2。这个特性让堆排序做到完全原地空间O(1)。建堆的过程是从最后一个非叶子节点开始逐个向下调整。最后一个非叶子节点的下标是n/2-1。为什么不是从0开始因为叶子节点本身已经满足“单个节点成堆”根本没有必要调整从叶子往上调整纯属浪费。6.2 建堆与堆排序的完整代码public void heapSort(int[] arr) { int n arr.length; for (int i n / 2 - 1; i 0; i--) { siftDown(arr, i, n); } for (int end n - 1; end 0; end--) { swap(arr, 0, end); siftDown(arr, 0, end); } } private void siftDown(int[] arr, int i, int size) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left size arr[left] arr[largest]) { largest left; } if (right size arr[right] arr[largest]) { largest right; } if (largest ! i) { swap(arr, i, largest); siftDown(arr, largest, size); } }这里最关键的细节是siftDown里的size会越来越小。排序阶段每次把堆顶最大值放到数组末尾的end位置然后调整堆时只能碰到end之前的元素否则已经排好的元素会被重新破坏。很多人以为建堆的复杂度是O(n log n)其实不是。建堆阶段从下往上做筛选大部分节点深度小总复杂度是O(n)。排序阶段才需要n次O(log n)的下滤所以堆排序整体是O(n log n)。6.3 为什么堆排序工程上不是最优堆排序听着很完美原地、O(n log n)、没有最坏退化。但实际工程里它很难打赢快排。原因主要有三个。第一堆排序访问数组的方式是跳跃式的不是顺序扫描。现代CPU对顺序访问有缓存预取优化快排能连续读写堆排序却动不动跳去访问2*i1的位置cache miss率明显更高。第二堆排序的交换次数比快排多。数据本身有序性越好快排的切换和比较次数越少但堆排序不管输入是否有序排序阶段每次都是堆顶交换 下滤操作量几乎恒定。第三快排经过优化后pivot的位置一旦确定左边右边可以并行处理更有利于现代处理器和多线程环境。但堆排序依然有独门绝技TopK问题。只要维护一个大小为K的小顶堆遍历一遍数据遇到比堆顶大的就替换并调整即可在O(n log K)内找到最大的K个元素。这在处理海量数据时非常实用也是堆排序最值得记住的应用场景。7. 非比较排序基数排序、计数排序与桶排序的线性时间魔法7.1 计数排序用空间换时间的第一课计数排序适用于数据范围有限且相对集中的整数。它的想法非常朴素统计每个值出现了多少次然后根据统计结果把元素放回原数组。比如要对[4, 2, 2, 8, 3, 3, 1]排序先扫描一遍知道值范围是1到8建一个大小为9的计数数组。统计完后计数数组变成[0,1,2,2,0,0,0,0,1]表示1出现1次、2出现2次、3出现2次、4出现1次、8出现1次。然后按顺序回填即可得到有序数组。如果只需要回填用累计频率可以保证稳定性。做法是把计数数组改成前缀和它表示“每个值最后一次出现时应该放在哪个位置”。然后从原数组末尾往前倒着放每放一个就把对应计数减一。public void countingSort(int[] arr, int maxVal) { int[] count new int[maxVal 1]; for (int x : arr) { count[x]; } for (int i 1; i maxVal; i) { count[i] count[i - 1]; } int[] out new int[arr.length]; for (int i arr.length - 1; i 0; i--) { int x arr[i]; out[--count[x]] x; } System.arraycopy(out, 0, arr, 0, arr.length); }这里的坑是计数数组大小。如果数据范围很大比如0到2^31-1计数排序的空间会爆炸。所以它的适用前提是整数、范围不能太大、最好数据分布密集。7.2 基数排序按位排序的稳定组合拳基数排序把比较大小变成了“按位分类”。它通常用LSDLeast Significant Digit最低位优先先按个位对所有元素做稳定排序再按十位排再按百位排排完最高位后整个数组就有序了。为什么按低位排完再按高位排能得到正确结果核心就是稳定排序。按十位排序时如果两个数十位相同稳定排序会保留上一次按个位排好的顺序也就是说十位相同的情况下个位小的会排在前面。每一位都在利用上一位的结果最终整体有序。实现上每一位都可以用一个计数排序来完成。假设数据都是三位数那么d3每轮计数排序的范围k是0到9复杂度就是O(3 * (n 10))约等于O(n)。写成代码就是在外层循环位数内层调用计数排序。基数排序的空间主要消耗在输出数组和计数数组上。它虽然稳定但不适用于负数、小数、字符串排序时也有限制。如果要处理负数需要先做偏移映射把所有数变成非负数再进行基数排序。7.3 桶排序均匀分布数据的利器桶排序是计数排序和基数排序的“中间形态”。它把数据按区间映射到多个桶里桶间有序桶内单独排序最后把桶按顺序连接起来。比如对[0.1, 0.3, 0.8, 0.2, 0.9, 0.5]这些在[0,1)之间的浮点数可以开10个桶分别对应[0,0.1)、[0.1,0.2)等区间元素落入各自桶后桶内用插入排序或快排最后从第0个桶到第9个桶依次输出。只要数据分布均匀桶排序接近线性但如果分布极端比如所有数都挤在一个桶里就退化成桶内排序的复杂度最坏又是O(n²)。桶排序在实际工程里的一个典型场景是外部排序的“分桶”预处理。把大数据按哈希或范围分到多个小文件中每个文件能装进内存时就单独排序最后按桶顺序合并。它不见得是单机排序的最优解但非常适合分布式和并行框架。7.4 突破O(n log n)下界的底层逻辑很多人困惑折半插入、快排、归并的最优都是O(n log n)为什么基数排序能到O(n)因为O(n log n)是“基于比较的排序”的理论下界而这个下界的推导假设是任何两个元素之间只能通过比较大小来获取信息。比较排序可以抽象成一棵决策树。n个元素的排列有n!种每次比较相当于走两个分支k次比较最多区分2^k种结果所以必须有2^k ≥ n!对n!取对数后得到k ≥ O(n log n)。计数排序、基数排序、桶排序都没有做“比较大小”而是借助值域、位数、区间映射直接从元素本身的特征确定位置。它们的信息获取方式绕过了比较决策树因此能突破下界。这给我们的启示是如果能利用数据的先验信息复杂度往往可以做得比通用方案更好。8. 八大排序横向对比与工程选型指南8.1 八大排序终极对比表把前面所有信息浓缩成一张总表方便你贴在屏幕前或者复习用。排序算法时间复杂度平均/最坏空间稳定性核心优势最大限制冒泡O(n²)/O(n²)O(1)稳定实现最简单太慢选择O(n²)/O(n²)O(1)不稳定交换次数最少比较次数恒定插入O(n²)/O(n²)O(1)稳定近有序极快大数组慢希尔O(n^1.3~1.5)/O(n²)O(1)不稳定跳跃插入增量序列难定归并O(n log n)/O(n log n)O(n)稳定稳定且可预测额外空间快速O(n log n)/O(n²)O(log n)~O(n)不稳定原地且平均最快最坏退化堆O(n log n)/O(n log n)O(1)不稳定原地稳定复杂度缓存不友好基数O(d(nk))/O(d(nk))O(nk)稳定线性时间值域/位数受限这里要特别提醒堆排序的“原地稳定复杂度”指的是时间和空间都可预测但它并不稳定。我见过不少文章把这句写成“堆排序稳定”这是错的。在任何面试场合回答稳定性都要非常小心。8.2 真实工程中的选型套路真实开发中我们绝大多数时候不会自己造排序轮子直接用现成库。但选型思路还是要懂。如果你在写Java对象排序直接信任Collections.sort或Arrays.sort的稳定排序如果你需要自定义排序规则注意Comparator的返回值必须和equals保持一致否则可能出现“排序结果不一致”的诡异问题。如果处理的是上GB的数据内存装不下就不要用快排而是用外部多路归并分块排序落盘再用优先队列做多路合并。这和堆排序里的TopK思想一脉相承。如果数据量很小比如排序几十个元素简单的插入排序往往比快排更快因为常数小、没有递归开销。这也是很多排序库在小数组阈值内切回插入排序的原因。如果数据范围是有限整数且分布密集计数排序和基数排序非常划算。典型例子是成绩统计、年龄分布、ID去重后的排序。我在一个日志分析项目里就遇到过这种情况几十万条记录要按照“时间戳排序”但时间戳都是同一个小时内的秒级整数范围不超过3600。直接用基数排序按低位到高位跑一遍比系统排序快了好几倍内存消耗也完全可控。8.3 面试考点与自查清单如果你是准备面试建议按下面的清单自查一遍能不能手写快排并解释partition为什么返回i能不能说清快排的最坏情况以及三种避免方式归并排序为什么稳定空间复杂度为什么是O(n)?堆排序如何用数组表示堆建堆复杂度为什么是O(n)?计数排序为什么用前缀和从后往前回填的目的什么基数排序为什么要求每一轮排序稳定哪些排序是稳定的哪些不是为什么如果要对链表排序选哪个如果要对字符串数组排序选哪个这些问题基本覆盖了面试官最爱追问的高频点。能答上来这些问题比背十遍模板都有用。最后分享一个我自己写排序算法时的习惯每次写完一个算法先用一个5个元素的随机数组跑一遍再打印每轮排序后的中间状态。比如快排就打印每次分区结束后的数组归并就打印每次合并后的数组。这个习惯帮我抓到了很多肉眼看不出来的边界bug。排序算法这八个本质上是八种解决问题的思路。冒泡教你从交换角度理解有序性选择教你用最值定位插入教你利用局部有序希尔教你跳跃式优化归并教你稳定的分治快排教你原地分区堆教你维护树形结构基数教你绕过比较限制。真正的收获不是背会代码而是下次遇到一个新问题你能从这八种思路里找到可迁移的那一个。