排序算法全解析：从八大经典到工程选型与面试实战

排序算法，这四个字只要学过编程基本都会碰到，但很多人背了又忘、写了又错，根源在于没把“算法与数据结构”当成一个整体去理解。排序算法不只是教科书里的知识点，它贯穿在数据库索引构建、搜索引擎排序、推荐系统打分、甚至外卖配送路径规划里。这篇博客我打算按自己实际学习和工作的理解，把排序算法从头到尾拆一遍——哪些排序是必须背下来的，哪些只是了解即可，怎么选型，怎么手写不出错，面试和工程里常见的坑又是什么。内容会比较长，适合正在学数据结构、准备考研408或算法工程师面试的人，也适合想系统梳理排序知识的学生。

1. 先想清楚：排序算法到底在排序什么

1.1 排序算法在真实世界中的应用场景

很多人觉得排序算法抽象，是因为学的时候只看数字排序。实际上，排序算法的本质是“让一组元素按照某种规则排列”，而这里的“元素”可以是数字、字符串、对象，甚至是自定义结构体。比如你在电商平台按价格排序商品，背后排序的是商品对象，比较标准是价格字段；数据库执行ORDER BY，底层可能是快速排序或归并排序的变体；搜索引擎把搜索结果按相关度排序，也是排序算法的应用。

我当年在项目里遇到过一个真实场景：一个广告投放系统需要把几百万条广告记录按出价和点击率组合排序，取前1000条展示。如果你只懂冒泡排序，那基本就是灾难；但如果掌握快排和堆排序的思想，就能在毫秒级完成筛选。这就是排序算法的价值——它不是孤立的知识点，而是解决“海量数据中找TopK”“按规则重排数据”等问题的基本功。

1.2 排序算法的前置认知与学习路径

我建议学习路径分四步走。第一步，理解“比较排序”和“非比较排序”的区别：冒泡、快排、归并等都属于比较排序，它们通过两两比较决定顺序；而计数排序、桶排序、基数排序则绕过比较，利用数据本身的分布特性，在特定场景下能达到线性时间复杂度。第二步，每个排序都要搞清楚四件事：思路、时间复杂度、空间复杂度、稳定性。第三步，手写代码，至少要能写出冒泡、插入、归并、快排、堆排序这五种。第四步，把排序和数据结构联系起来，比如堆排序依赖堆这个完全二叉树的结构，归并排序依赖递归和临时数组，快排依赖分治和指针移动。

很多人一上来就背代码，这是最没效率的路子。我自己的经验是，先在白纸上画出每一轮排序的结果，模拟一遍过程，再对照代码看每一步在做什么。这样当面试官问你“快排每一轮过后数组长什么样”的时候，你才能自然答上来。

2. 八大经典排序算法逐个拆解

2.1 冒泡排序：交换类排序的入门课

冒泡排序的原理说出来谁都能懂：从第一个元素开始，相邻两个元素两两比较，如果前一个大于后一个就交换位置，这样一轮下来，最大的元素就像气泡一样“冒”到了最后。重复 n-1 轮，整个数组就有序了。

void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int swapped = 0; 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 = 1; } } // 如果本轮没有发生交换，说明已经有序，提前退出 if (!swapped) break; } }

这个代码里有个关键细节：用一个swapped标记判断是否提前结束。如果你没加这个优化，那一个本来就有序的数组也会老老实实跑完 n-1 轮，浪费时间。加了之后，最好情况时间复杂度从 O(n²) 降到 O(n)。

冒泡排序的时间复杂度最好 O(n)、最坏 O(n²)、平均 O(n²)，空间复杂度 O(1)，并且是稳定排序。它的主要价值就是教学——让你理解暴力交换的思路。实际工程项目里，我几乎没见过有人用冒泡排序处理真数据。但你要是连冒泡都写不利索，后面的快排、归并也别指望能一次写对。

2.2 选择排序：最直观但是最不划算的排序

选择排序的思路是：每一轮从未排序区间里找出最小值，放到已排序区间的末尾。它比冒泡更好理解，但有一个致命问题——无论数组是否有序，它都要执行 n-1 轮扫描，所以最好、最坏、平均时间复杂度都是 O(n²)，且不稳定。

void selectionSort(int arr[], int n) { 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; } } }

为什么说不稳定？举个例子：数组 [5a, 3, 5b]，第一轮找到最小值 3，和 5a 交换，变成 [3, 5b, 5a]，两个 5 的相对位置变了，所以不稳定。这个特性在一些需要保持原始顺序的场景里是不能接受的。比如按分数排序学生，分数相同时希望保留原来按照学号的先后顺序，用选择排序就会破坏这种顺序。

我选排序学习它的意义在于让你理解“扫描+交换”的基本套路，以及不稳定的概念。但实际应用里，它的效率差，而且交换次数偏多。如果你发现自己在工程里写了一个类似选择排序的循环，多半可以换成更高效的方案。

2.3 插入排序与希尔排序：从“摸牌”到“跳跃插牌”

插入排序的核心思想很像玩扑克牌摸牌：你手里的牌已经有序，每抓一张新牌就插入到合适的位置，让整副牌依然有序。

void insertionSort(int arr[], int n) { 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大的元素整体后移，而不是用两两交换。这样省了大量交换操作，而且对于“几乎有序”的数据，插入排序效率惊人——最好情况时间复杂度是 O(n)。在我实际处理“某个已经基本排好序但有几个元素错位”的数组时，插入排序有时候比快排还快，因为它省去了递归和分区开销。

希尔排序是插入排序的升级版，它的思路是先进行“大跨度插入排序”，让数据粗有序，再逐步缩小跨度，最后做一次普通插入排序。跨度叫增量（gap），常见的选择是不断折半。

void shellSort(int arr[], int n) { 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; } } }

希尔排序的时间复杂度与增量序列的选择有关，折半增量时大约是 O(n^1.3)。它是不稳定排序，但在中等规模数据上往往表现不错，而且不需要额外空间。我早年在一些嵌入式设备上用希尔排序处理传感器采集的数据，就是因为内存太紧张，不能用归并排序的辅助数组。

2.4 归并排序：分治思想最好的学习样本

归并排序是“分治法”的经典代表。它的思路一句话就能概括：把数组从中间拆成两半，分别排序，再把两个有序数组合并成一个。

void merge(int arr[], int left, int mid, int right) { int len = right - left + 1; int *tmp = (int *)malloc(sizeof(int) * len); int i = left, j = mid + 1, 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 (i = 0; i < len; i++) { arr[left + i] = tmp[i]; } free(tmp); } void mergeSort(int arr[], int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); }

归并排序的时间复杂度稳定为 O(n log n)，空间复杂度 O(n)。它最大的优点是稳定，而且在处理链表排序时特别好用——链表不支持随机访问，快排和堆排序在链表上实现很别扭，但归并排序天然适合链表。

我强调一下mid = left + (right - left) / 2这个写法。不要写成(left + right) / 2，因为当 left 和 right 都接近 int 上限时，两者相加会溢出。这个细节我在写算法题时踩过坑，后来养成了习惯，只要是二分相关都写left + (right - left) / 2。

另一个细节是原地归并。很多人听到“原地归并”就以为不需要辅助空间，其实纯原地归并要么牺牲稳定性，要么算法极复杂。工程实践中，直接用 O(n) 空间的归并排序往往就够了，不要为了省空间把自己绕进去。

2.5 快速排序：工程与面试的双料主角

快速排序算法是排序话题里绕不开的 C 位。它也是分治思想，但与归并排序的“先拆再合”不同，快排的思路是“边拆边定”：选一个基准值（pivot），把数组分成左边小于等于基准、右边大于等于基准的两部分，然后递归处理左右两侧。基准每次都在正确的位置上。

void quickSort(int arr[], int low, int high) { if (low >= high) return; 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]; while (i < j && arr[i] <= pivot) i++; if (i < j) arr[j--] = arr[i]; } arr[i] = pivot; quickSort(arr, low, i - 1); quickSort(arr, i + 1, high); }

这段代码是经典的“挖坑法”，需要注意几个边界：

第一，外层循环条件while (i < j)，内层两个while也必须带i < j，否则可能出现指针越过对方的情况。第二，内层比较时要用>=和<=，不能用>和<，否则相同的元素会被无限交换。第三，选择arr[low]作为基准值时，必须先从右边开始扫描。如果先从左边开始，最后填回基准时会出现错误。这些细节我在面试候选人时经常拿出来问，能一次写对的人真的不多。

快排的平均时间复杂度 O(n log n)，最坏 O(n²)，空间复杂度 O(log n)（递归栈）。最坏情况发生在每次分区都极度不平衡时，比如数组已经有序但每次都选第一个元素作为基准。针对这个问题，工程上常用两个优化：一个是“三数取中”选基准，即从第一个、中间、最后一个元素中选中间值；另一个是当递归分区长度小于某个阈值（比如16）时改用插入排序。像 C 标准库qsort和 Java 的Arrays.sort，底层都用了类似策略。

2.6 堆排序：用堆这种数据结构实现的高效排序

堆排序算法是“算法与数据结构”结合得最紧密的排序——它依赖二叉堆这种完全二叉树结构。堆排序的第一步是建堆，把数组整理成一个大顶堆（父节点大于等于子节点）；第二步是循环把堆顶的最大元素和末尾交换，缩小堆的范围，再下沉调整。

void heapify(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp; heapify(arr, n, largest); } } void heapSort(int arr[], int n) { for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } for (int i = n - 1; i > 0; i--) { int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; heapify(arr, i, 0); } }

这里有个关键点需要理解：数组下标从 0 开始，所以节点 i 的左右子节点分别是2*i+1和2*i+2；而从最后一个非叶子节点开始调整，它的下标是n/2 - 1。很多人建堆时从 0 到 n 逐个调整，这是错的——必须从下往上调整，才能保证每棵子树都已经是堆结构。

堆排序的时间复杂度是稳定的 O(n log n)，空间复杂度 O(1)，但它是不稳定排序。工程中它比快排用得少，但有个场景特别有用——维护动态数据的 TopK。比如实时统计系统日志中出现的 top 10 错误码，用一个大小为 10 的小顶堆，每个新数据进来时和堆顶比较，比堆顶大就替换并下沉，复杂度只有 O(log K)。如果你只会调用现成的排序函数，这种场景就很难优雅地处理。

2.7 计数排序、桶排序与基数排序：不比较也能排序

这三类排序属于非比较排序，它们不依赖两两比较，而是利用数据的分布特性。计数排序适用于数据范围较小但数据量很大的场景。比如公司员工年龄排序，年龄范围大约 18 到 65 岁，这时创建一个 48 大小的计数器数组，遍历一遍员工数据，统计每个年龄出现次数，最后按顺序输出即可。时间复杂度 O(n + k)，k 是数据范围。

void countingSort(int arr[], int n, int range) { int count[range]; memset(count, 0, sizeof(count)); for (int i = 0; i < n; i++) count[arr[i]]++; int idx = 0; for (int i = 0; i < range; i++) { while (count[i]-- > 0) arr[idx++] = i; } }

计数排序的局限性也非常明显：只能处理范围较小的整数。如果数据是浮点数，或者范围大到无法分配数组，就不适用了。

桶排序可以看作计数排序的泛化版。它把数据按范围分到若干个桶里，每个桶内部再用其他排序算法排序，最后把所有桶的数据依次拼接。桶排序在许多大数据处理框架里都有使用，典型场景是对均匀分布的数据排序。它的平均时间复杂度 O(n)，但数据分布极端不均匀时可能退化。我在处理地理位置坐标排序时试过用桶排序，把经纬度数据按网格分桶，效果比直接全量排序快了非常多。

基数排序则适用于位数较多的整数或字符串，比如手机号排序、车牌号排序。它按位进行多次排序，每次排序必须使用稳定排序作为子过程，通常是计数排序。比如对所有三位数排序，就先按个位排，再按十位排，再按百位排，最终得到整体有序的结果。基数排序的时间复杂度 O(d * (n + k))，d 是位数。它的关键点是“必须稳定”，否则每一轮排序都会破坏上一轮的结果。

这三种非比较排序在实际工作中非常重要，而且常常是面试加分项。很多人只会背“八大排序”，却不知道什么时候用计数排序，什么时候用桶排序。我建议你记住一句话：只要数据的值域范围有限且已知，就可以考虑计数排序；只要数据分布均匀，就可以考虑桶排序；只要数据是多位数或定长字符串，就可以考虑基数排序。

3. 复杂度、稳定性与工程选型

3.1 一张表看懂八大排序的复杂度

我一直觉得，有经验的开发者看排序算法，第一件事是看复杂度表格，而不是看代码。下面这个表格建议直接记住：

注意“最好时间复杂度”那一列，很多人记错。冒泡和插入排序在数组本身有序时都能达到 O(n)，原因是它们可以提前终止或不需要移动元素；但选择排序即使数组已经有序，仍然要扫描全部未排序区间，所以最好也是 O(n²)。快排的“最好”和“平均”都是 O(n log n)，但“最好”的定义是每次分区都恰好平分数组时。

3.2 稳定性到底有什么用

稳定性是一个经常被轻视但实际非常重要的概念。稳定排序的意思是：如果两个元素相等，排序后它们的前后相对顺序保持不变。那为什么需要保持这个顺序？最典型的是“多关键字排序”场景。

举一个例子：有一组学生数据，先按班级排序，再按成绩排序。如果你用稳定排序按成绩排序，那么相同成绩的学生之间，还会保持上一次按班级排序的顺序；但如果你用非稳定排序，相同成绩的学生可能被打乱，班级顺序就失效了。所以多关键字排序的正确做法是：从最次要的关键字开始排序，逐级排序到最重要关键字，并且每一级都必须使用稳定排序。

我最早接触稳定性的概念是在做数据库索引时。数据库的二级索引在构建时，要求相同键值的记录按照主键顺序排列，这正是对稳定性的需求。如果你在项目中需要“先按时间、再按优先级”地排列任务列表，稳定性就要纳入选型考量。

3.3 工程中排序算法到底怎么选

在实际工程里，直接手写排序的场景并不常见，因为标准库已经提供高质量排序实现，比如 C 的qsort、C++ 的sort、Java 的Arrays.sort、Python 的sorted。但用库不等于不懂选型，尤其是在定制排序时，你要理解底层在做什么。

现代语言标准库的排序往往是混合算法，不是单一快排。例如 Java 的Arrays.sort对基本类型使用双轴快速排序，对对象类型使用 TimSort（一种稳定的归并排序变体）；Python 的排序底层也是 TimSort。为什么对象排序用 TimSort？因为对象比较可能开销较大，稳定排序能提供更好的可预测性，同时 TimSort 对“大致有序”的数据表现极佳。

如果你的数据量小于几百条，插入排序通常最快，因为它没有递归和复杂分区；如果你的数据量在几十万级，快排或归并是主力；如果内存紧张且数据量巨大，堆排序和外部排序更合适；如果数据值域有限而且在特定范围内，非比较排序可能碾压所有比较排序。我之前做过一个分析：10 万条 0 到 1000 之间的整数排序，计数排序只需要两次遍历，比快排快一个数量级。

4. 实战细节：手写排序前必须搞懂的关键点

4.1 快速排序的边界条件与三数取中

手写快速排序算法是算法工程师面试的高频环节，但也是最容易出错的环节。以我面试过的候选人为例，能一次写对快排的人，通常对边界条件非常敏感。

第一个边界条件是“递归终止”。很多初写者写if (low == high) return;，但快排递归时可能出现low > high的情况，所以正确写法是if (low >= high) return;。第二个边界条件是内层比较的等号。前面已经提过，挖坑法的内层循环必须用>=和<=，否则基准值周围的相等元素会形成死循环。第三个边界是分区后递归调用的范围：左半部分是[low, pivotIdx - 1]，右半部分是[pivotIdx + 1, high]，因为基准已经在正确位置。

为了规避最坏情况 O(n²)，工程实现里会做“三数取中”优化：取区间第一个元素、中间元素、最后一个元素，选出它们的中位数作为基准值。这个操作代码很短，但实际效果非常好——它可以避免数组有序时（即每次选到最小或最大值做基准）的退化情况。如果面试官让你优化快排，提到三数取中、插排阈值、尾递归优化，基本就能过关了。

我在工程里还见过一个有趣的现象：很多人会用swap(arr[low], arr[mid])把选好的基准换到最前面，这没问题，但要注意如果基准值是用挖坑法处理的，挖坑法的初始坑位必须和基准真正所在位置一致。一个小心得：写快排之前先想清楚“基准位置的赋值路径”，也就是每次i和j移动后，arr[i]或arr[j]的旧值去了哪里。想清楚这个过程，代码基本不会乱。

4.2 归并排序的额外空间与外排序扩展

归并排序的场景远不止内存排序。当数据量超过内存容量时，最少用到的一个算法就是“外部归并排序”。它的基本流程是：把海量数据分块读入内存，每一块分别用快排整理成有序的小文件；然后把这些有序小文件像多路归并一样逐个合并，最终生成一个完整的有序大文件。

这就是为什么很多大数据系统的 Shuffle 阶段（即 MapReduce 框架里 mapper 输出排序后交给 reducer 的过程）会用到归并排序的思想——它的机制天然适合流式处理。你不需要把几 GB 数据全部加载进内存，只要维护 K 个文件的游标，每次比较 K 个头部数据，取最小写入结果文件。

实现多路归并时有一个经典优化：用一个大小为 K 的最小堆来维护 K 个文件当前的最小值，这样每次从堆顶取出最小元素后，再从对应文件补充下一个元素，时间复杂度从 O(K) 降到 O(log K)。这个点经常出现在算法工程师面试里，表面考归并排序，实际考堆数据结构的应用。

如果你要在内存里手写归并，也要注意辅助数组的生命周期。不要在递归过程中频繁地分配和释放内存，这是性能杀手。正确做法是在递归前一次性分配好临时数组，然后传给每一层归并函数使用。这一点很多教程不会专门讲，但实际排查性能瓶颈时经常会碰到。

4.3 从排序算法的“价值观”讲到面试答题套路

这里我想分享一个面试答题的心得。算法面试里经常出现“请给一个数组排序，但要求 xxx”的变形题，比如“有大量重复元素时如何排序”“只排其中的一段区间”“需要稳定但原地”。

面对这些变形，不能只靠背模板，要理解每种排序算法的适用条件和短板。比如大量重复元素，快排会表现得比较差，因为分区会极不平衡；此时可以引入三路快排（把区间分为小于、等于、大于基准三部分），或者直接用计数排序。又比如要求稳定且需要原地，这是比较棘手的要求，因为稳定排序大多需要额外空间，原地归并排序代码复杂且常数因子大，工程上通常会用插入排序这类空间 O(1) 且稳定的算法去折中，但时间复杂度会退化到 O(n²)。

再比如“需要找到第 K 大的数，不要求整体排序”，这时候没有任何必要做完整排序，最佳方案是基于快排思想的“快速选择”，平均 O(n)。我在真实的数据分析任务里，用快速选择找出千万级数据的中位数，速度比全量排序快太多。这个知识点在热词搜索里也经常和“八大排序算法总结”一起出现，说明大家对排序变形问题确实很关注。

5. 常见问题与调试记录

5.1 递归一深就栈溢出

无论是快排还是归并排序，都用到了递归，而递归深度在数据量大的时候可能很深，尤其是快排在极端情况下递归深度达到 O(n)，很容易爆栈。

我遇到过一个真实的线上问题：一个 Java 服务对大 List 调用Collections.sort()时莫名抛出StackOverflowError，排查后才发现是因为 JDK 的sort里 TimSort 实现本身也有递归逻辑，当输入数据包含大量逆序数据时，合并栈深度异常高。这里给一个通用建议：如果你在写快排，可以用“尾递归优化”减少栈深度，办法是每次递归只处理较短的一半，较长的一半用迭代处理。

void quickSortOptimized(int arr[], int low, int high) { while (low < high) { int pivotIdx = partition(arr, low, high); if (pivotIdx - low < high - pivotIdx) { quickSortOptimized(arr, low, pivotIdx - 1); low = pivotIdx + 1; } else { quickSortOptimized(arr, pivotIdx + 1, high); high = pivotIdx - 1; } } }

如果你使用的是 C 语言，还可以在编译期调大栈空间，但这是治标不治本。更通用的方法是在递归函数内部限制最大递归深度，超过阈值就切换到堆排序。

5.2 数据量一大内存就爆

归并排序需要一个大小为 n 的临时数组，当 n 是几千万甚至上亿时，这本身就很危险。一次我在处理上亿行 CSV 文件排序时，直接用归并排序，结果内存直接被打满，进程被杀。后来我改用外部排序——把文件拆成几百个小块，每块内部排序后写回磁盘，再用多路归并合并。只用了几百 MB 内存，就能处理几十 GB 的数据。

另外要提醒一点：如果用 C 语言写归并排序，malloc临时数组后记得free，而且要在函数出口执行。很多人调试时发现内存泄漏，就是因为在merge里开了数组但提前 return 导致free没执行。这个属于低级错误，但在初期特别容易发生。

5.3 比较器写错导致的结果随机

排序不只是“大小比较”的问题。对整数数组排序，直接用>和<；对自定义对象排序，就要写比较器。比较器写错是排序类 bug 里最常见的根源。比如在 Java 里写：

Collections.sort(list, (a, b) -> a.score - b.score);

如果a.score - b.score超过 int 范围，就会溢出，导致比较结果错误。更隐蔽的问题是“比较器不满足传递性”，即compare(a, b) < 0且compare(b, c) < 0但compare(a, c) >= 0，这样排序算法可能陷入不可预期的行为，甚至抛出异常。所以工程里我的习惯是使用Integer.compare(a.score, b.score)而不是直接做减法，避免溢出和传递性风险。

还有一个与稳定性相关的坑：很多库的排序底层是稳定排序，但如果你在比较时恰好比较了对象内部的某个字段，而其他字段顺序被打乱，结果看起来像是排序不稳定。我之前排查过一次“List 排序后相同 score 的记录顺序变了”的问题，最后发现是自己比较器返回时把 score 相等的情况也返回了非零值。写比较器时，一定要在条件里明确处理相等情况，返回 0。

6. 一些真实的工程体会

我个人在实际项目里用得最多的是系统自带的排序函数，但真正让我在性能问题面前不至于抓瞎的，恰恰是这些排序算法的底层原理。比如有一次处理用户行为日志，需要按时间字段排序千万条记录，直接调用qsort就能算完，但内存占用一直居高不下，后来我判断是排序过程中发生了大量缓存不命中，改成基于桶的思路按小时分组排序后，性能立刻提升了几倍。这种场景下，如果只看排序复杂度已经不够，还要考虑数据分布和内存访问模式。

还有一个很实际的建议：在面试前手写这几类排序时，不要抄代码，而是边写边说出每一步在做什么。我后来带新人时也一直这么要求。比如写快排时说“我现在把基准填到正确位置，左边全部小于它，右边全部大于它”，写归并时说“我把两个有序子数组合并到临时数组，再拷贝回原数组”。能说出来，说明你才是真的理解，面试官也会觉得你是真在写算法，而不是背模板。

排序算法的话题到这里远远没有结束，像外部排序、TimSort、并行排序这些从高频排序衍生出的主题，每一个都值得专门研究。这篇文章相当于一个系统性的总览和实战手册，剩下的路，就在你实际写代码和调性能的过程中慢慢展开了。