企业官网建设流程全解析

面试官让候选人讲讲八大排序算法，很多人的第一反应是背快排模板。有一次我在技术面里问一个三年经验的候选人：“快排最坏情况是什么？”他答上来了；接着问“为什么基本类型用快速排序、引用类型用归并排序？”他愣住了。排序算法背后的本质理解，远比默写模板重要。

八大排序算法，通常指冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序。这八个算法几乎覆盖了排序领域最重要的思想：暴力枚举、插入优化、分治递归、堆结构、线性非比较。无论你是准备校招面试、社招跳槽，还是在日常开发里优化一段数据流水线，弄清楚它们都不是浪费时间。

这篇内容我打算用文字版图解的方式，把每个算法的“为什么”讲透：为什么插入排序适合小数据、为什么快排平均最快、为什么堆排序明明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²)，这是所有快排优化都要解决的问题。

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[j+1] = 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个元素的数组，假设gap=5：

[49, 38, 65, 97, 76, 13, 27, 49, 55, 04, 87]

间隔5分成组：

• 下标0和5：49和13
• 下标1和6：38和27
• 下标2和7：65和49
• 下标3和8：97和55
• 下标4和9：76和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 QuickSort，Arrays.sort(Object[])用TimSort。前者不考虑稳定性，后者必须稳定。这正好回答了我开头说的那个面试题。

6. 堆排序：用二叉树思想优化选择排序

6.1 从选择排序到堆排序的进化

选择排序每轮要扫描整个数组找最小值，这是O(n)的操作，整体复杂度因此变成O(n²)。堆排序的思路是：用一个大顶堆来维护数组中最大的元素，堆顶就是最大值，把它和末尾交换，然后缩小堆范围、向下调整堆。这样“找最大值”就从O(n)降到了O(log n)。

堆在数组里的表示很巧妙：对于下标i，它的左孩子是2*i+1，右孩子是2*i+2，父节点是(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*i+1的位置，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 基数排序：按位排序的稳定组合拳

基数排序把比较大小变成了“按位分类”。它通常用LSD（Least Significant Digit，最低位优先）：先按个位对所有元素做稳定排序，再按十位排，再按百位排，排完最高位后，整个数组就有序了。

为什么按低位排完再按高位排能得到正确结果？核心就是稳定排序。按十位排序时，如果两个数十位相同，稳定排序会保留上一次按个位排好的顺序，也就是说十位相同的情况下，个位小的会排在前面。每一位都在利用上一位的结果，最终整体有序。

实现上，每一位都可以用一个计数排序来完成。假设数据都是三位数，那么d=3，每轮计数排序的范围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 八大排序终极对比表

把前面所有信息浓缩成一张总表，方便你贴在屏幕前或者复习用。

这里要特别提醒：堆排序的“原地稳定复杂度”指的是时间和空间都可预测，但它并不稳定。我见过不少文章把这句写成“堆排序稳定”，这是错的。在任何面试场合，回答稳定性都要非常小心。

8.2 真实工程中的选型套路

真实开发中，我们绝大多数时候不会自己造排序轮子，直接用现成库。但选型思路还是要懂。

• 如果你在写Java对象排序，直接信任Collections.sort或Arrays.sort的稳定排序；如果你需要自定义排序规则，注意Comparator的返回值必须和equals保持一致，否则可能出现“排序结果不一致”的诡异问题。
• 如果处理的是上GB的数据，内存装不下，就不要用快排，而是用外部多路归并：分块排序落盘，再用优先队列做多路合并。这和堆排序里的TopK思想一脉相承。
• 如果数据量很小，比如排序几十个元素，简单的插入排序往往比快排更快，因为常数小、没有递归开销。这也是很多排序库在小数组阈值内切回插入排序的原因。
• 如果数据范围是有限整数且分布密集，计数排序和基数排序非常划算。典型例子是成绩统计、年龄分布、ID去重后的排序。

我在一个日志分析项目里就遇到过这种情况：几十万条记录要按照“时间戳排序”，但时间戳都是同一个小时内的秒级整数，范围不超过3600。直接用基数排序按低位到高位跑一遍，比系统排序快了好几倍，内存消耗也完全可控。

8.3 面试考点与自查清单

如果你是准备面试，建议按下面的清单自查一遍：

1. 能不能手写快排并解释partition为什么返回i？
2. 能不能说清快排的最坏情况以及三种避免方式？
3. 归并排序为什么稳定？空间复杂度为什么是O(n)?
4. 堆排序如何用数组表示堆？建堆复杂度为什么是O(n)?
5. 计数排序为什么用前缀和？从后往前回填的目的什么？
6. 基数排序为什么要求每一轮排序稳定？
7. 哪些排序是稳定的？哪些不是？为什么？
8. 如果要对链表排序，选哪个？如果要对字符串数组排序，选哪个？

这些问题基本覆盖了面试官最爱追问的高频点。能答上来这些问题，比背十遍模板都有用。

最后分享一个我自己写排序算法时的习惯：每次写完一个算法，先用一个5个元素的随机数组跑一遍，再打印每轮排序后的中间状态。比如快排就打印每次分区结束后的数组，归并就打印每次合并后的数组。这个习惯帮我抓到了很多肉眼看不出来的边界bug。

排序算法这八个，本质上是八种解决问题的思路。冒泡教你从交换角度理解有序性，选择教你用最值定位，插入教你利用局部有序，希尔教你跳跃式优化，归并教你稳定的分治，快排教你原地分区，堆教你维护树形结构，基数教你绕过比较限制。真正的收获不是背会代码，而是下次遇到一个新问题，你能从这八种思路里找到可迁移的那一个。