企业官网建设流程全解析

开篇：排序算法是面试的照妖镜

在上篇里我们把插入排序、选择排序、冒泡排序、希尔排序这些“入门级选手”过了一遍。但说实话，现在一线公司面试，只靠那几板斧是撑不住场面的。真正让你在面试官面前站稳脚跟的，是快排、归并、堆排、计数、桶、基数这几位“重量级选手”。我常说一句话：排序算法是面试的照妖镜——你写代码的熟练度、对复杂度的敏感度、对边界条件的把控度，全在十分钟的手撕环节里暴露干净。

下篇这几种排序，几乎覆盖了面试中80%以上的算法题考察点。你刷LeetCode也好，做笔试题也好，经常发现考的不是排序本身，而是把排序当成了通向另一个问题的跳板。比如TopK问题表面上让你找最大的几个数，实则考察的是堆排序和快排的partition思想；合并K个有序链表，本质就是多路归并；字符串排序里如果有大量同前缀数据，基数排序可能才是面试官心里默认的最优解。

所以这篇不只是教你怎么写代码，更重要的是帮你在面试现场建立“看到问题→联想到某个排序→改造成适合当前场景”的条件反射。按我的经验，这种条件反射的训练，比背一百道题都有用。

1. 内容整体设计与思路拆解

1.1 为什么面试官死磕这几类排序

很多人不理解：现在业务开发里谁还会自己写排序？调库不就完了，Java里Arrays.sort，Python里sorted，一行代码搞定。这个观点没错，但面试官考察排序根本不是让你去解决实际业务问题，他们是在用排序作为载体，测试你几样底层能力。

第一是递归和分治思想。快排和归并是分治思想最典型、最简练的载体。你能不能在白板上把递归过程写清楚，能不能正确分析每一层递归的复杂度，能不能用循环改写递归避免栈溢出，这些能力在后面的二叉树、回溯、动态规划题目中一样需要。排序是训练这些能力成本最低的题目。

第二是数据结构的灵活使用。堆排序考的是“堆”这种抽象数据结构你是怎么理解并手搓实现的。TopK问题最经典的做法就是维护一个堆，这个堆可以是系统的PriorityQueue，但面试官常常会让你自己实现一个二叉堆，这时候你如果只会用库函数，当场就露馅。

第三是对数据特征的分析能力。计数排序、桶排序、基数排序不是比较排序，它们的复杂度可以做到O(n+k)，在特定场景下吊打所有比较排序。面试官给你一个“数组里成绩是0到100分”的场景，你能瞬间反应出该用计数排序，说明你对问题特征的敏感度到位了。

第四是工程权衡能力。归并排序稳定、O(nlogn)但需要额外空间，快排平均快但最坏退化到O(n^2)，堆排不占用额外空间但常数大且不稳定。面试官问你“如果内存极度受限但数据量巨大你选哪个”之类问题，实质就是逼你做工程取舍。

所以面试死磕排序，磕的是以上四种能力的综合表现。

1.2 这些排序之间的内在关系

先把“下篇”要讲的排序在脑子里串成一幅地图。快排和归并是靠“比较+递归”走向两个不同方向的典型：快排先划分再递归，归并先递归再合并。堆排干脆把乐观思想发挥到极致——每次都能取到全局最大或最小，靠堆这个结构把“找最大”的成本压到O(logn)。这三兄弟统称比较排序，理论下界是O(nlogn)。

计数、桶、基数则是另一个思路，它们不比较大小，而是利用数据的值域特征和位数结构，要么把数据当成桶里的石头一个个数，要么按位逐层处理，所以复杂度能突破O(nlogn)下界，稳定做到O(n+k)。但要享受这个复杂度，前提条件极苛刻：值域不能太大、分布要均匀、位数要有上限。

理解了这张图，你就知道为什么说出来某个排序之后，面试官下一个问题往往是“如果数据长成什么样，这个排序就不行了”——他们就是在考你对边界条件的把握。

2. 面试手撕必备：快速排序的三大变体

2.1 经典单边扫描法：最不容易写错的一版

面试现场手撕快排，我强烈建议你先写下这个版本。不是说它性能最好，但它最不容易写错，而且能很清晰地向面试官展示你对“分治”思想的理解。

单边扫描法的思路是这样的：选一个pivot（通常选区间最后一个元素），用一个索引i维护“小于pivot的区域”的边界，用j遍历整个区间，发现比pivot小的就把它换到左边，遍历结束后pivot和i+1位置交换，这样pivot左边都小于它，右边都大于等于它。然后递归处理左右两半。

用Java实现长这样：

public void quickSort(int[] arr, int low, int high) { if (low >= high) return; int p = partition(arr, low, high); quickSort(arr, low, p - 1); quickSort(arr, p + 1, high); } private int partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(arr, i, j); } } swap(arr, i + 1, high); return i + 1; }

注意这里的边界条件：for循环j是从low到high-1，因为high位置是pivot本身，不参与遍历。i初始等于low-1，因为开始时“小于pivot区域”是空的。最后pivot换到i+1位置，返回的i+1就是pivot最终下标。

面试官经常会追问：为什么交换arr[i+1]和arr[high]？因为i+1位置恰好是第一个大于等于pivot的元素的位置，pivot放在这里能保证左边都小于它、右边都大于等于它。如果你换个写法，把相等元素分到左边，逻辑也通，但稳定性依然没法保证——快速排序天生不稳定，这点要心里有数。

2.2 双端扫描法：更均衡的性能选择

双端扫描法是很多教科书的标准写法，实际执行效率比单边法略好，因为它是从两边同时向中间逼近，在随机数据上可以减少一点赋值操作。

这个版本的partition思路是：取区间最左端为pivot，两个指针i和j分别从两端出发，j先动，从右往左找小于pivot的元素，i再从左往右找大于pivot的元素，两人都找到就交换。直到i和j碰头，把pivot换到交界处。

private int partition(int[] arr, int low, int high) { int pivot = arr[low]; int i = low, j = high; while (i < j) { while (i < j && arr[j] >= pivot) j--; if (i < j) { arr[i] = arr[j]; i++; } while (i < j && arr[i] <= pivot) i++; if (i < j) { arr[j] = arr[i]; j--; } } arr[i] = pivot; return i; }

我踩过的坑在这里讲给所有人：双端扫描里，必须保证j先动找到比pivot小的数，再让i找比pivot大的。如果顺序反了，会导致pivot换位后左边出现比pivot大的元素。这属于隐性bug，数据量大时排序结果错误，但小数组测试可能恰好不出来。面试现场写出这种bug，印象分会掉得很厉害。

2.3 三路切分：从O(nlogn)到O(n)的工程级优化

真实工程里，大量排序场景会碰到“数据里有大量重复元素”。比如排序一个班级几百人的成绩，满分100分的区间，可能三分之一的分数都是90分。这种情况经典快排会反复处理这些相等的元素，白白浪费递归深度。三路切分就是为了根治这个问题设计的。

三路切分的核心思想是把区间分成三段：小于pivot的、等于pivot的、大于pivot的。遍历一次后等于pivot的区域直接落定，不再参与递归。当重复元素很多时，等于区域较大，递归规模大幅缩小，甚至可以达到O(n)级别的复杂度。

public void quickSort3Ways(int[] arr, int low, int high) { if (low >= high) return; int lt = low, gt = high, i = low + 1; int pivot = arr[low]; while (i <= gt) { if (arr[i] < pivot) { swap(arr, lt++, i++); } else if (arr[i] > pivot) { swap(arr, i, gt--); } else { i++; } } quickSort3Ways(arr, low, lt - 1); quickSort3Ways(arr, gt + 1, high); }

这里lt保存“小于pivot区域”的后继位置，gt保存“大于pivot区域”的前驱位置，中间是等于区域。整个while循环结束后，[low, lt-1]全小于pivot，[lt, gt]全等于pivot，[gt+1, high]全大于pivot。

面试中写出三路切分，至少说明你真读过工程级代码，不是只背了课本题。另外提一句，Java自带的Arrays.sort对于引用类型对象排序，底层用的是归并排序（因为要保证稳定性），对基本类型排序用的是改良版双轴快排。你如果面试时说漏嘴说“Java排序就是快排”，可能被面试官抓小辫子。

3. 归并排序：稳定排序里的扛把子

3.1 递归版实现与复杂度证明

归并排序之所以是面试高频考点，一方面它是稳定排序中复杂度最优的代表，另一方面它完美诠释了“先解决子问题，再合并结果”的分治流程。

它的逻辑可以一句话概括：把数组从中间切开，先把左右半边分别排有序，再合并成一个有序数组。递归地进行下去，直到区间只剩一个元素天然有序。

public void mergeSort(int[] arr, int low, int high) { if (low >= high) return; int mid = low + (high - low) / 2; mergeSort(arr, low, mid); mergeSort(arr, mid + 1, high); merge(arr, low, mid, high); } private void merge(int[] arr, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low, j = mid + 1, k = 0; while (i <= mid && j <= high) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while (i <= mid) temp[k++] = arr[i++]; while (j <= high) temp[k++] = arr[j++]; System.arraycopy(temp, 0, arr, low, temp.length); }

这里有两个细节值得你在面试中主动提出来，能加分。第一，int mid = low + (high - low) / 2，而不是(low + high) / 2，因为后者在low和high都很大时可能整数溢出。第二，合并时用<=保证稳定性，相等的元素永远先取左半边的，排序后相同值的相对顺序不会变。

复杂度分析要学会自己推一遍：每一层归并需要遍历全部n个元素做合并，递归深度是logn层，所以总时间是O(nlogn)。额外空间来自临时数组，最坏情况O(n)，如果你每次merge都新建数组、合并完再释放，在递归栈里同时存在多个临时数组，实际空间会更高，这也是递归版归并在超大数组上可能OOM的原因。

3.2 迭代版归并排序：根治递归栈溢出

递归虽然简洁，但有一个致命伤：递归深度等于logn，对10亿级别的数组来说深度大概30层，不算深，但每次递归都要压栈，栈空间不是无限大的。在Java默认线程栈配置下，某些极端环境下还是会出问题。更严谨的说法是，面试官问迭代版，是在考察你能不能把递归过程改写成自底向上的循环。

迭代版归并的思路：先把相邻的每两个元素排序，再每四个排序，再每八个排序……步长翻倍，直到整个数组有序。不需要不断切分数组，直接按步长合并。

public void mergeSortIterative(int[] arr) { int n = arr.length; int[] temp = new int[n]; for (int step = 1; step < n; step *= 2) { for (int low = 0; low < n; low += 2 * step) { int mid = Math.min(low + step - 1, n - 1); int high = Math.min(low + 2 * step - 1, n - 1); if (mid < high) { merge(arr, temp, low, mid, high); } } } }

注意这里的mid和high都要用Math.min缩到n-1以内，因为数组末尾可能不满一个step长度。还有一个工程细节：这里的merge版本要复用同一个temp数组，索引对应关系要处理好。每次合并后把结果写回arr，再下一轮继续用。

面试时如果时间紧张，写递归版就够了。但如果时间有余、你写迭代版，面试官会明显觉得你有过大规模数据处理方面的实际经验。

3.3 从归并到多路归并：外部排序的思想启蒙

面试官不会只满足于你写出归并排序，他往往会追加一个问题：如果内存只有1GB，但你要排序的是10GB的文件，怎么办？这问的不是归并排序本身，而是外部排序。而外部排序的基础思想就是多路归并。

多路归并的思路：把10GB数据切成10个1GB的块，每块在内存里排序后写回磁盘，形成10个有序小文件，然后对这10个有序文件做“多路归并”合成一个有序大文件。多路归并时用一个小根堆维护每个文件的当前最小值，每次从堆顶取出最小的写入输出文件，再从对应的输入文件读取下一个元素补入堆中。这个堆的插入和删除都是O(logk)，k是文件路数，所以总代价大约是nlogk，比两两合并的nlog2要高效得多。

这个点你在回答时要主动把它跟“归并排序的merge过程”串联起来：单路merge只是把两个有序数组合并，多路merge是把k个有序序列合并，思路一脉相承，逻辑差别只是把两个while换成基于堆的选择。面试时能这样抽丝剥茧地说出来，比背答案有说服力得多。

4. 堆排序：TopK问题的最强辅助

4.1 堆的构建：从数组到堆的一行行堆化

堆排序在面试中出现频率极高，但大家的痛点也很集中：能说出“堆排序就是不断取堆顶然后重建堆”，但手写代码总是写不对。最直接的原因就是维护堆（heapify）的代码写不熟练。

堆是一个完全二叉树，可以用数组连续存储，父节点在i，左孩子在2i+1，右孩子在2i+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 i = n - 1; i > 0; i--) { swap(arr, 0, i); siftDown(arr, 0, i); } } private void siftDown(int[] arr, int i, int n) { while (true) { int max = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[max]) max = left; if (right < n && arr[right] > arr[max]) max = right; if (max == i) break; swap(arr, i, max); i = max; } }

为什么构建堆要从n/2-1开始？因为n/2-1是最后一个拥有子节点的非叶子节点。叶子节点没有孩子，谈不上下沉，所以从最后一个父节点开始，逐个调整，这样能保证所有子树都是堆。这一步的时间复杂度是O(n)，不是O(nlogn)，理解这事的关键在于堆化过程中大多数节点的下沉高度很小。面试时能提这点，说明你推导过复杂度。

4.2 堆排序特性：不稳定但空间零消耗

堆排序的时间复杂度稳定在O(nlogn)，空间复杂度O(1)，这算是它独特的优势。因为不需要额外临时数组，在内存受限场景中比归并排序更合适。但它有一个让很多初学者疑惑的特性：不稳定。

不稳定来自它的交换模式。堆排序在排序过程中，会把堆顶元素直接与数组尾部的元素交换，这种远距离跳跃式的交换很容易打破相等元素之间的相对顺序。比如有两个相同值的元素，一个在前一个在后，堆调整过程中可能把后面的翻到前面去。所以如果要求稳定排序且数据是引用类型，堆排序不能用，归并是更好的选择。

面试中常见的追问是：堆排序和快排都是O(nlogn)，什么时候优先选堆排序？我的回答经验是：当你有TopK需求（只要最大或最小的几个），而且数据量特别大、没必要全部排序时，堆是最优解；如果要全量排序且内存不限，快排常数小更快；如果内存很紧不能有额外空间，堆排更合适。

4.3 TopK问题的堆实现思路

TopK是堆最经典的实战场景：从海量数据中找到最大的K个。如果用排序做，先全部排序再取前K，时间至少O(nlogn)；用堆做，只需要维护一个大小为K的小根堆，遍历一遍数据，比堆顶大就换进去，最后堆里就是最大的K个，总时间O(nlogK)。

很多人会问为什么是“小根堆”而不是“大根堆”？因为你要保留最大的K个，堆里应该时刻保留“当前已见过最大的K个”。堆顶是这K个中最小的，新来的元素只要比堆顶大，说明它足够优秀，可以挤掉目前最小的那个。如果你用大根堆，堆顶是最大的，你无法判断新来的应该淘汰谁。

public List<Integer> topK(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(k); for (int num : nums) { if (minHeap.size() < k) { minHeap.offer(num); } else if (num > minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } return new ArrayList<>(minHeap); }

这个题目看似简单，但有一个隐藏考点：数据是流式的、无限量的，你不可能全部存下来，只能用堆控制内存占用在O(k)。面试时你把这点挑明，说明你考虑的不是做题，而是真实系统设计。

5. 线性时间排序三件套：计数、桶、基数

5.1 计数排序：值域小才是王道

面试官在快排后面问你“有没有可能比O(nlogn)还快的排序”时，你不要第一时间答堆排或桶排，正确答案应该是：基于比较的排序下界是O(nlogn)，但如果我们打破比较的框架，可以做到线性时间。计数排序就是第一个要搬出来的案例。

计数排序的思路是：已知数据都在一个较小的值域范围内，比如0到100分的成绩，那我准备一个长度等于值域大小的计数数组，遍历一遍原始数组统计每个值出现多少次，然后按count数组把元素依次写回原数组。这整个过程没有一次比较，纯靠计数和回填。

public void countingSort(int[] arr, int k) { int[] count = new int[k + 1]; for (int num : arr) count[num]++; int idx = 0; for (int i = 0; i <= k; i++) { while (count[i] > 0) { arr[idx++] = i; count[i]--; } } }

这里k是数据最大值，count的长度是k+1。注意计数排序是稳定的——但上述“遍历count写回”的写法丢失了稳定性。要保留稳定性，需要先计算前缀和，得到每个元素应该落到的最后位置，然后从后往前填回原数组。我给你一个稳定版本的实现：

public void countingSortStable(int[] arr, int k) { int[] count = new int[k + 1]; int n = arr.length; for (int num : arr) count[num]++; for (int i = 1; i <= k; i++) count[i] += count[i - 1]; int[] output = new int[n]; for (int i = n - 1; i >= 0; i--) { int num = arr[i]; output[count[num] - 1] = num; count[num]--; } System.arraycopy(output, 0, arr, 0, n); }

前缀和的含义是：count[i]最终等于“小于等于i的元素总个数”，因此值i在输出数组中的位置范围是[count[i-1], count[i]-1]。从后往前遍历是为了稳定：相同值的元素，后面出现的先被放到右边，再往前一个放前面出现的，顺序就保住了。

5.2 桶排序：分布均匀时的奇效

桶排序本质上是把值域切成若干个区间，每个区间是一个桶，把数据分别放进对应的桶，桶内各自排序，再按桶顺序拼接。它跟计数排序的区别是：计数排序每个值独占一个计数位，桶排序是“一段区间”共用一个桶；桶内排序可以用任意排序算法，最常用插入排序或快排。

桶排序的复杂度分析比计数排序复杂一点，取决于桶内数据的分布。如果数据是均匀分布的，桶内数据规模大约是n/k，桶内排序总代价大约是O(n·log(n/k))，当k接近n时，桶内几乎都是一两个元素，总代价接近O(n)。但如果有大量数据挤进同一个桶，最坏退化成O(n²)。

面试时你最好举一个贴近“均匀分布”的实例。比如对0到1之间的10000个随机浮点数排序，把[0,1)均分成10个桶，每个桶管0.1的跨度，因为数据均匀，每个桶大概有1000个元素，桶内再递归用桶排序或插入排序。

public void bucketSort(float[] arr, int bucketCount) { List<List<Float>> buckets = new ArrayList<>(); for (int i = 0; i < bucketCount; i++) buckets.add(new ArrayList<>()); for (float num : arr) { int bucketIdx = (int) (num * bucketCount); buckets.get(bucketIdx).add(num); } int idx = 0; for (List<Float> bucket : buckets) { Collections.sort(bucket); for (float num : bucket) arr[idx++] = num; } }

这里要注意bucketIdx = (int)(num * bucketCount)，当num正好等于1时，会算出bucketCount，数组越界。所以浮点数范围如果包含1，要单独处理，或者用Math.min套一下。这种边界细节，你主动说出来，面试官会觉得你是一个真正写过工程代码的人。

5.3 基数排序：按位排，位数有限就无敌

基数排序的思路跟前面完全不一样：不是一次性比较大小，而是把整数看成多位数，从最低位到最高位一位一位地排，每一位都用稳定排序（通常用计数排序）来处理。因为低位的顺序在更高位确定顺序后依然保留，最终就能得到整体有序的结果。这就是稳定性在基数排序里的价值。

举个例子，排序三位数：先按个位排序，再按十位排序，最后按百位排序。十位排序时，十位相同的元素会保持个位排好的相对顺序，而个位顺序在十位相同时正好决定大小顺序。所以最终排出来的结果一定正确。

public void radixSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); for (int exp = 1; max / exp > 0; exp *= 10) { countingSortByDigit(arr, exp); } } private void countingSortByDigit(int[] arr, int exp) { int n = arr.length; int[] count = new int[10]; for (int num : arr) count[(num / exp) % 10]++; for (int i = 1; i < 10; i++) count[i] += count[i - 1]; int[] output = new int[n]; for (int i = n - 1; i >= 0; i--) { int digit = (arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; } System.arraycopy(output, 0, arr, 0, n); }

exp是“当前处理的位”对应的10的幂次：个位exp=1，十位exp=10，百位exp=100。每一轮计数排序只关注当前位的数字。时间复杂度等于O(d·(n+k))，d是最大数的位数，k是进制大小（十进制时是10）。当d是常数时，就是O(n)。

面试中谈到基数排序时，有个极好的加分点：它不是只能排整数，字符串也可以排，按字符的ASCII码逐位排序。比如大量短字符串排序，按长度分组后逐位用计数排序，整体非常高效。能想到这个扩展，说明你不是死记硬背。

6. 希尔排序与“几乎有序”数据的真香场景

6.1 增量序列驱动的间隔插入

上篇里我们聊过插入排序对“几乎有序”的数据非常高效，但大规模乱序数据上插入排序太慢。希尔排序就是在这个痛点上的改良：它不是一个个往后插入，而是先用大间隔把元素粗排一遍，让数据整体上从“乱序”变成“局部有序”，然后逐步缩小间隔，最终间隔为1时退化成插入排序。但因为前面几轮已经把数据整得差不多了，最后一轮插入排序的代价非常低。

简化的实现如下，用希尔增量n/2, n/4, ..., 1：

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 temp = arr[i]; int j = i; while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } }

这个写法本质上就是“间隔为gap的插入排序”。外层循环控制gap从大到小，内层对每个位置做一次间隔为gap的插入。很多人在这一步会写错，特别是内层循环的边界：j >= gap保证arr[j-gap]下标不越界，temp保存的元素必须在外层循环里定义而不是在内层。

6.2 为什么面试官最后问它

希尔排序在纯理论面试中不算重点，因为它的时间复杂度分析非常复杂，依赖增量序列的选取。别的不说，不同增量序列下的最坏复杂度从O(n^3/2)到O(nlog²n)都有报告，面试官很难期待你能现场证明具体数值。

但它在实际面试中常作为“附加题”出现，原因有两个。一是它非常方便面试官考察你对插入排序本质的理解程度：你能不能把两两相邻的插入排序推广到任意间隔，能不能理解“局部有序帮助最终的插入排序减少移动次数”。二是现实里大量数据接近有序，比如日志按时间追加、数据库按主键递增写入，这种场景下希尔排序往往比快排更实用。你能主动提到这一点，说明你不仅会写，还关注排序在真实数据上的表现。

7. 稳定性与复杂度全景对照表

这张表是面试的高频弹药库，建议你反复咀嚼，尤其注意三组容易被问倒的对比。

第一组：快速排序和归并排序。快排最坏O(n²)但常数小，归并稳定O(nlogn)但需要额外内存。Java的Arrays.sort对基本类型用快排变体，对对象类型用归并或TimSort，原因就在于“基本类型不需要稳定性，对象类型排序后可能还依赖相对顺序”。第二组：堆排序和快排。堆排最坏也是O(nlogn)，且空间O(1)，为什么很多场景还是首选快排？因为快排的局部性更好，缓存命中率高，常数小，堆排虽然复杂度一样但频繁跳变访问数组不同位置，缓存很不友好。第三组：三个线性排序的适用边界。计数排序要求值域小且已知，桶排序要求数据分布均匀，基数排序要求数据有位数结构且位数有限。三者都不能应对“任意场景”，面试官很容易在这个点上埋连环问。

8. 面试实战：从排序到场景题的通关套路

8.1 高频面试题抽丝剥茧

面试里很多题看似跟排序不相关，内核就是排序思维的变体。我按出现频率给几个经典案例。

“求一个无序数组的第K大元素”。这道题的经典解法有两个：快排partition法把元素定位到它的最终位置，如果最终位置恰好是n-K，直接返回；如果偏左，只递归右边，否则只递归左边，平均O(n)。另一个解法是小根堆维护K个元素，堆顶就是答案，O(nlogK)。面试官通常会让你两种都讲，然后问你它们分别适合什么数据规模——答案是在内存充足、数据全部载入内存时快选更快，流式数据或内存限制时堆更合适。

“合并K个有序链表”。这道题答案本质就是多路归并：维护一个小根堆，存K个链表的当前头节点，每次弹出最小节点，并将它的后继入堆，直到堆空。复杂度O(nlogK)，空间O(K)。面试官会问你为什么不能每次比较K个头直接取最小——那样是O(nK)，当K很大时性能完全不行。

“一个文件里有海量URL，统计出现次数最多的前K个”。标准答案是小根堆+哈希表，精确做法，内存够用的情况下。如果内存不够，基于哈希分片拆分成多个小文件，逐文件统计后合并。这一问考察的是外部排序思想的延伸应用。

这三个案例的共同点是：答案从来不是让你“写一次完整排序”，而是让你用某个排序的局部结构（partition、堆化、勾并）快速解决更大问题。你在回答时先定位“这是某种排序的变体”，再展开，面试官会更容易跟你的思路走。

8.2 快速有序的选择指南

在面试里给你一个数组，你该选哪个排序？我平时建议按三个维度过一遍：数据量大小、数据是否接近有序、是否允许额外空间。

数据量很小（几十个以内），插入排序就完事，别把简单问题复杂化。数据量大但不要求稳定性，优先快排。数据量大且值域非常小（比如成绩0到100），计数排序秒杀一切比较排序。数据量大且要稳定排序，归并排序或TimSort。内存非常紧，不允许额外空间，堆排序或快排原地版。数据分布均匀且已知范围，桶排序往往有惊人效果。数据位数有限（身份证号、手机号字符串），基数排序很顶。

面试官问完“你会哪些排序”之后，紧接着来一句“如果要你在生产环境选一个排序，你会怎么选”，千万不要回答“我全都要”。给出明确的取舍逻辑，说明你理解得足够深。

8.3 常见错误与边界条件

面试现场手写排序，有几个高频翻车点，我必须单独拎出来。

数组越界是最常见的。所有涉及i+1、j-1、2i+1的地方，必须检查循环边界。快排里i从low-1开始，归并里mid+1可能超过high（但递归保证不会），堆排里siftDown的左孩子2i+1必须小于堆大小n。

递归边界写错也很常见。快排里只要low >= high就return，归并同理。有人会把if (low == high) return当作正确写法，其实low > high也会出现，尤其在partition返回p等于low后，左右分区会有一个为空的情况，这时候必须用>=兜底。

稳定与不稳态混淆。面试官问归并排序为什么稳定，你要答出关键在merge时相等元素优先取左半部分。问快排为什么不稳定，你要答出partition的交换可能把相等的元素前后顺序打乱。这些细节说对了，加分极大。

还有一个细节：写快排pivot选最后一个元素时，如果数组本身接近有序，快排会退化到O(n²)。你可以提前用“随机选pivot”或“三数取中”策略规避，面试时简单提一句“为了对抗有序输入，我会随机化pivot”，预算上就已经赢了。

结尾：手撕排序，撕的是对自己代码的掌控感

跟我带过的很多同学交流，大家普遍反馈一个现象：排序算法看别人写都懂，轮到自己手写就卡壳。这不是智力问题，而是练习方式问题。你光看代码不动手，永远不知道while循环里哪个条件是多余的，也不会发现j>=gap这个判断漏掉后程序会出什么错。我建议把下篇这七种排序，每一行都亲手敲三遍：第一遍照着写，第二遍默写，第三遍在纸上画流程然后直接写。三遍下来，你会发现自己不仅在排序题上有了底气，连递归分治、堆操作、边界处理这些底层技能也一起刷新了。

还有一个技巧我一直跟人说：把每种排序当成“模板”背下来，但背的时候在脑内附一个“最不容易记牢的小细节”。比如快排是i从low-1开始，归并是mid = low + (high-low)/2，堆排是for i从n/2-1开始构建，计数排序是求前缀和并反向填回。这些小细节就是面试现场的救命稻草。

另外最后再多说一句，别光练下篇，上篇那些基础排序也不是没用——插入排序在Timsort里就是作为小规模排序的基本单元，归并排序的核心思想就是上篇merge的扩展。整个排序体系是一条完整的技术链，从简单到复杂，从比较到非比较，每一步都是在为后面更复杂的算法打地基。你把这张网织好了，面试这一关就稳了，往后看任何算法题都会觉得底盘扎实很多。