企业官网建设流程全解析

我到现在还记得那个项目——后台导出一张两万行的报表，前端点一下表头排序，要卡两到三秒。一开始以为是后台接口慢，查了半天才发现，前任开发在浏览器端用冒泡排序处理数据，每条记录还带一串字符串比较。那个瞬间我就明白了，排序这个看起来"谁都会写"的东西，学不学得扎实，在真实系统里天差地别。

这篇排序算法学习实例，不是说"排序很重要"就完了，而是把我自己从零开始啃排序的完整过程摊开来讲：为什么冒泡、选择、插入要先学，归并和快排的核心思路差在哪，堆排序为什么既优雅又有点尴尬，以及最容易被忽略的复杂度记号问题——什么时候该写O，什么时候该写θ。如果你正在学算法、准备算法面试，或者工作中经常跟数据排序打交道，这篇内容应该能帮你把排序这块拼图完整装进脑子。

1. 一个两万行报表卡顿背后的真相：排序为什么值得系统学

先说那个卡顿项目。我最初也觉得两万行数据在浏览器里排序，就算算法一般也不至于卡成这样。打开代码才发现，问题的核心根本不是数据量，而是排序过程里嵌套了字符串比较，而且外层还有个多余的循环。把前端的冒泡排序换成内置的sort函数之后，整个排序从两秒多降到了几十毫秒。这次经历让我第一次意识到：排序算法不是一个"会用sort()就行"的知识点，而是理解代码性能的起点。

1.1 排序恰好覆盖了算法学习的全部关键概念

刚开始学算法的时候，最容易犯的错就是贪多。今天看动态规划，明天看KMP，后天又去刷图论，每样都只是"听说过"。排序不一样，它是一块信息密度极高的切片：

• 循环与嵌套循环：冒泡、选择、插入排序都是两层循环，循环变量的边界处理直接决定代码对不对。
• 递归与分治：归并排序和快速排序都用递归，递归树的概念能在这里第一次落地。
• 数据结构：堆排序直接用到完全二叉树；优先队列在TopK问题里的应用也以堆为基础。
• 复杂度分析：所有排序都能用来练习最好、最坏、平均情况下的时间复杂度推导。
• 稳定性与空间复杂度：这是工程上最容易被忽略的两个维度，但排序提供了一个极好的观察窗口。

所以我一直跟刚入门的朋友说：如果只有一个月准备算法，先把排序全部吃透，比囫囵吞枣刷一百道题更有用。排序几乎是唯一一个能把"复杂度分析、递归、数据结构、工程权衡"全部串起来的主题。

1.2 这篇实例的适用人群

这篇文章不是教科书式的知识罗列，而是按我自己的学习路径展开的：先用最暴力的三种排序建立直觉，再用归并和快排理解分治，接着用堆排序补上数据结构的视角，最后回到业务里看MySQL和JavaScript里实际运行的排序。每一段我都尽量说清楚两个事：这个算法到底怎么动的，以及为什么这样设计。

适合三类人看：

• 算法初学者：需要一个从上手到理解、再到反思的完整路径。
• 准备算法面试的工程师：排序衍生的TopK、逆序对、链表排序等变种题非常多，基础不牢会死得很惨。
• 日常开发中接触报表、排行榜、分页排序的人：搞清楚底层机制，你才知道什么时候该加索引，什么时候该改排序逻辑。

2. 三个"暴力求解"排序：为什么必须先写一遍冒泡、选择和插入

很多教程一上来就甩快速排序，美其名曰"面试只考快排"。但我的看法恰恰相反：把冒泡、选择、插入各写一遍，你对排序的理解会上一个台阶。这三个算法虽然慢，但它们是理解所有高级排序的"参照物"。

2.1 冒泡排序：最直观但工程上最没用

冒泡排序的思路一句话就能说清：每一轮从头到尾比较相邻元素，如果顺序不对就交换，让最大的元素像气泡一样浮到末尾。代码写起来是这样的：

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标记。这是冒泡排序最重要的优化：如果某一轮遍历完后一个元素都没交换，说明数组已经有序，直接结束。

复杂度方面，最坏情况下数组完全逆序，需要比较n×(n-1)/2次，是O(n²)；最好情况下数组本来就有序，加上提前退出，只需要一趟遍历，是O(n)。空间复杂度O(1)，稳定。

工程上为什么没人用它？因为即使加了提前退出，它在平均情况下的交换次数也远多于插入排序，常数太大。它最大的价值是教学：让你直观感受"相邻交换"这个最基本的排序动作。我建议你至少手写一遍，然后把它放进抽屉，别再拿出来用了。

2.2 选择排序：用循环不变量证明它必然正确

选择排序的思路也很暴力：每次从剩余元素里找出最小的，放到已排序部分的末尾。代码：

def selection_sort(a): n = len(a) for i in range(n): min_idx = i for j in range(i + 1, n): if a[j] < a[min_idx]: min_idx = j a[i], a[min_idx] = a[min_idx], a[i] return a

为什么说"选择排序的循环不变量值得认真学"？因为这是算法正确性证明的最经典入门案例。

循环不变量是这样一个断言：外层循环每次迭代开始前，数组前i个位置已经是全局最小的i个元素，并且它们已经排好序。用归纳法来证明：

• 初始化：当i=0时，前0个元素天然有序，命题成立。
• 保持：假设迭代开始前前i个元素是有序的且是全局最小的i个。内层循环从i开始往后找最小元素的下标min_idx，找到后与a[i]交换。交换后，前i+1个元素就是全局最小的i+1个，且有序。因此下一次迭代开始时命题依然成立。
• 终止：当i=n时，前n个元素（也就是全部元素）有序，排序完成。

这个证明逻辑和解数学归纳法一模一样。我当时第一次看懂这个证明时，心里的震撼是：原来"程序是对的"这件事是可以被严谨论证的，而不是靠"我觉得应该没问题"。

选择排序有个容易被忽略的特点：无论输入什么样，它的比较次数都是固定的n×(n-1)/2。所以它最好、最坏、平均全是θ(n²)，这个"不敏感"性质在复杂度分析时特别有意思。缺点也很明显：交换操作虽然少，但它不稳定。举个例子，数组[2a, 2b, 1]，第一轮找到1，交换到位置0，此时2a被换到末尾，两个相同的2相对位置就变了——这正是后面面试里爱问的"为什么不稳定"。

2.3 插入排序：打扑克牌的手感应试大有用处

插入排序的思路很多人打扑克牌时就在用了：摸到一张新牌，插到手里已经排好序的牌堆中正确位置。代码：

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循环里：把所有比key大的元素依次往后挪一个位置，最后留出的空位就是key该待的地方。插入排序是稳定的，因为只有当a[j]严格大于key时才会挪动相等元素。

我最想强调的一点是：插入排序对"近乎有序"的数据非常快。如果数组已经有序，while循环一次都不执行，时间复杂度退化到θ(n)（这一点在第6节会细说）。这个特性让它成了很多高级排序的"最后一公里"：快速排序在递归到小规模区间时改用插入排序，Python内置的TimSort在合并短序列时也用插入排序。所以别小看它，它不是个淘汰的玩具，而是被嵌在工程级排序算法里的重要零件。

3. 归并排序：第一次真正理解"分治"的威力

如果说冒泡、选择、插入是暴力求解，那归并排序就是第一个"动脑子"的排序。我第一次写完归并排序，脑子里只有一个念头：原来可以把问题切成两半，分别解决后再合并起来。

3.1 分、治、合三步走的结构

归并排序遵循一个极其清晰的三段式：

1. 分（Divide）：把数组从中间切成两半。
2. 治（Conquer）：递归地对左半和右半各自排序。
3. 合（Combine）：把两个已经有序的子数组合并成一个有序数组。

Python实现：

def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(l, r): i = j = 0 result = [] while i < len(l) and j < len(r): if l[i] <= r[j]: result.append(l[i]) i += 1 else: result.append(r[j]) j += 1 result.extend(l[i:]) result.extend(r[j:]) return result

核心在merge函数：同时扫描两个有序数组，哪边当前元素小就取哪个。注意这里用的是 l[i] <= r[j]，这是归并排序稳定性的关键——当左右两个元素相等时，优先取左边数组里的元素，这样相同元素的原始相对顺序不会被破坏。

3.2 为什么复杂度稳定在O(n log n)

归并排序的复杂度分析是最经典的分治复杂度推导。设总时间复杂度为T(n)，则有递归式：

T(n) = 2T(n/2) + O(n)

其中2T(n/2)是两个子问题，O(n)是合并两个子数组的代价。把递归树画出来：第0层合并代价n，第1层有两个子问题每个代价n/2，合计n，第2层有四个子问题每个代价n/4，合计还是n……一直到log₂n层，每一层的总代价都是n，所以总复杂度是n×log₂n，即O(n log n)。

这里有个值得注意的点：归并排序的最好情况、最坏情况和平均情况都是θ(n log n)。因为它无论输入怎么分布，都严格执行"对半分+线性合并"的流程，不存在"运气好就快"的情况。这个性质让它在所有排序算法里非常独特，也让它成为外部排序和数据库排序的基础。

空间复杂度是O(n)，因为合并时需要额外数组。这一点在后端场景下是个真实约束：数据量一大，内存占用就可能成为瓶颈。

3.3 从内存到磁盘：归并排序在大数据场景的延伸

归并排序真正的舞台其实不在内存里那几十万个元素。当数据量大到内存装不下时，比如排序几个GB的日志文件，你没法直接调用Arrays.sort，这时候就需要外部排序。外部排序的基本思路就是归并排序的工程放大版：

1. 把大文件切成多个内存放得下的小块。
2. 对每个小块用快速排序或插入排序排好，写回磁盘作为有序片段。
3. 然后用多路归并的方式，同时打开多个有序片段，不断取最小的元素写出到最终文件。

你看到的大数据框架里MapReduce的shuffle阶段排序、MySQL做超大结果集filesort时用的临时文件归并，本质都是这一套。学了归并排序再去看这些系统，你会觉得一切都很眼熟。

4. 快速排序：最常用、也最容易写崩的排序

快速排序大概是面试里出现频率最高的排序，但真让候选人当场手写一遍，能一次写对的并不多。我见过太多人在partition的边界条件上翻车。

4.1 partition是快排的灵魂

快速排序的核心不是递归本身，而是分区（partition）：选一个基准值pivot，让数组中所有小于pivot的元素移到左边，大于等于pivot的移到右边，然后返回pivot最终所在的位置。最直观的实现是Lomuto分区：

def quick_sort(arr, low, high): if low >= high: return p = partition(arr, low, high) quick_sort(arr, low, p - 1) quick_sort(arr, p + 1, high) def partition(arr, low, high): pivot = arr[high] i = low - 1 for j in range(low, high): if arr[j] < pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1

Lomuto分区的逻辑：i指向最后一个"小于pivot的区域"的末尾，j从头扫到尾，遇到比pivot小的元素就把它换到前面去。最后把pivot换到i+1位置。建议你强制自己把这个分区过程在纸上模拟几遍，因为这是快排最容易写错的地方。

另一个经典分区是Hoare分区，双向扫描，交换次数更少，但边界处理更复杂，新手容易死循环。我的建议是：面试写Lomuto，能讲清楚原理的是Hoare，日常工程用系统库，别自己造轮子。

4.2 为什么最坏是O(n²)，平均却是O(n log n)

快速排序的时间复杂度高度依赖pivot的选择。最优情况是每次pivot都能把数组分成两半，递归式和归并排序一样，T(n)=2T(n/2)+O(n)，复杂度O(n log n)。但如果你每次选的pivot恰好是当前区间的最小值或最大值，那分区结果就是一边0个、一边n-1个元素，递归式变成T(n)=T(n-1)+O(n)，退化成一个等差数列求和，复杂度O(n²)。

最经典的退化场景就是你对一个已经排好序的数组做快排，同时pivot固定取末尾元素。前两天我还跑了个测试，对一个10万元素有序数组用上面的Lomuto代码排序，肉眼可见地慢。解决办法有三个层次：

• 随机选pivot：partition之前随机交换一个元素到末尾，让"每次选中极值"的概率变得极低。
• 三数取中：取首、中、尾三个元素的中位数作pivot，对几乎有序的数组很有效。
• 小区间优化：递归到长度小于十几的子数组时改用插入排序，减少递归调用开销。

快速排序不稳定。比如数组[3a, 3b, 1]，partition过程中两个3的相对顺序可能被打乱。这在实际业务里是个大坑，尤其你按多个字段依次排序的时候。

5. 堆排序：用完全二叉树实现原地排序

堆排序是我学排序算法时感觉最吃力、但学完收获最大的一章。它第一次让我意识到：排序的本质不只是"相邻比较"或"分治切分"，还可以借助一个抽象数据结构来组织数据。

5.1 堆到底是什么

堆是一棵完全二叉树，用数组就能存。任意节点下标i，左孩子是2i+1，右孩子是2i+2，父节点是(i-1)//2。大顶堆满足一个性质：每个节点的值都大于等于它的两个孩子。所以堆顶永远是整个数组的最大值。

建堆的过程叫堆化（heapify）：从最后一个非叶子节点开始，逐个向下调整，让每个子树都满足堆性质。所谓向下调整，就是比较当前节点和孩子的大小，如果不满足大顶堆规则就跟较大的孩子交换，然后继续向下检查。建堆代码：

def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)

这里n是当前堆的大小，i是待调整的节点下标。注意递归调用heapify的下标是largest，因为交换后原来的i元素跑到了孩子的位置，还要继续检查它是否满足堆性质。

5.2 建堆是O(n)，但这改变不了堆排序是O(n log n)

很多人以为建堆需要O(n log n)，这个直觉其实是错的。推导一下：高度为h的节点最多需要向下调整h次，而第h层的节点数是n/2^(h+1)个。总代价Σ h×n/2^(h+1)，求和结果是O(n)。我第一次看到这个推导时很惊讶——原来从下往上建堆，大部分节点几乎不需要调整。

堆排序的完整流程：

1. 建堆：把数组调整成一个大顶堆。
2. 交换：把堆顶（最大值）换到数组末尾，堆大小减1。
3. 堆化：对新堆顶重新向下调整，恢复大顶堆。
4. 重复步骤2和3，直到堆大小为1。

代码：

def heap_sort(arr): n = len(arr) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0)

第二步是个循环，从末尾往前面每次取出当前最大值，所以最终数组从小到大排列。每次删除堆顶需要O(log n)，共n次，所以总复杂度O(n log n)。堆排序是不稳定的——堆顶元素和末尾元素的交换可能让相同值的相对顺序发生变化。

5.3 TopK问题的堆排序思路

堆排序本身在实际排序场景里不算最优，因为它的常数大，而且对缓存不友好（数组随机跳访问）。但堆这种数据结构的真正价值在优先级队列和TopK问题：从10亿个数里找出最大的100个。如果用快排全量排序，复杂度O(N log N)，内存也扛不住。正确做法是维护一个容量为100的最小堆：

• 读到一个数，如果堆还没满，直接入堆。
• 堆满了，拿这个数和堆顶比较，如果比堆顶还大，就把堆顶弹出去，把这个数入堆。
• 全部数过完后，堆里那100个数就是最大的100个。

复杂度是O(N log 100)，N是数据总量。这就是为什么很多排行榜系统、分页统计系统里，堆结构这么常见的原因。

6. 复杂度那点糊涂账：什么时候该写O，什么时候该写θ

很多人在刷题和写博客的时候，复杂度符号用得乱七八糟。我自己也经历过一段"看到O就觉得是大约"的时期，直到系统的排序学习逼着我把记号彻底搞明白。这个知识点看似理论，实际上面试和工程里天天碰到。

6.1 大O描述的是上界，不是"大约"

严格定义是这样：如果存在正常数c和n₀，使得当n≥n₀时，f(n)≤c×g(n)，那么称f(n)=O(g(n))。它只约束"不会比这个更慢"，不约束"最少有多慢"。

所以你可以说“冒泡排序是O(n²)”，也可以说“冒泡排序是O(n³)”，虽然不精确，但定义上没错。也正因如此，大O常常被用来表达最坏情况下的性能上界。面试时你说"这个算法是O(n log n)"，面试官默认你是在给最坏情况一个保证性的承诺。

6.2 θ才是"紧的界"

f(n)=θ(g(n))定义是：存在正常数c₁、c₂和n₀，使得当n≥n₀时，c₁×g(n)≤f(n)≤c₂×g(n)。也就是说，f(n)的增长速率和g(n)是同一个量级，上下都被夹住了。当你看到θ，就能确定地说："它快慢就是这个程度，不存在隐藏的惊喜。"

什么时候该用θ？当某个算法的复杂度在所有输入分布下都一样的时候，比如选择排序最好最坏平均都是θ(n²)、归并排序所有情况都是θ(n log n)，这种情况下说θ就是最精确的。想表达"某个算法已经达到某种理论最优"时，也要用θ或Ω。比如"基于比较的排序下界是Ω(n log n)，归并排序是θ(n log n)"，这句话的意思是：归并排序在这个下界上已经做到了最优。

什么时候该用O？当算法复杂度随输入分布变化，而你需要描述一个保守保证时。快速排序平均θ(n log n)、最坏O(n²)，你不能直接说它"是θ(n log n)"，因为最坏输入会打脸。正确说法是"期望θ(n log n)，最坏O(n²)"。

我整理了一个常见排序算法的复杂度速查，方便对照：

注意这张表里我故意混用了O和θ，看懂这张表，你也就看懂了这两个符号的区别。

6.3 一个具体的推导例子

以插入排序为例。外层循环i从1到n-1，内层while在最坏情况下要把key一路挪到位置0，所以内层执行次数是1+2+...+(n-1)=n(n-1)/2，最坏是θ(n²)。但这个说法只能在最坏输入下成立，如果输入本身几乎有序，内层while几乎不执行，复杂度直接降到θ(n)。

所以当你被问到"插入排序复杂度是多少"时，最完整回答是：平均和最坏θ(n²)，但最好情况θ(n)，因此工程上它适合做近乎有序数据的小规模排序。这个回答同时展示了你对大O和θ的理解深度，比干巴巴说一句"O(n²)"好得多。

7. 真实系统里的排序：MySQL、JavaScript 和字符串的那些"意外"

学了这么多年排序，我最深的体会是：教科书上的排序是干净的理论，但现实系统中，排序往往以四两拨千斤的方式藏在各种功能背后。看看几个真实场景，你就能理解为什么"排序算法"这个基础会和业务强相关。

7.1 字符串排序：为什么item10会排在item2前面

有次我做一个文件列表功能，按文件名排序，期望的顺序是item1、item2、item10，结果却出现item1、item10、item2。原因很简单：字符串排序是按字符逐位比较的，'1'的Unicode码点小于'2'，所以"item10"在比较第7个字符时比"item2"更靠前。这就是字典序，不是你以为的数字序。

解决字母数字组合排序通常要用"自然排序"：把字符串拆成数字片段和非数字片段，数字片段转成整型参与比较。Python可以自己实现：

import re def natural_key(s): parts = re.split(r'(\d+)', s) return [int(part) if part.isdigit() else part.lower() for part in parts] files = ["item10", "item2", "Item1", "item1"] sorted_files = sorted(files, key=natural_key) print(sorted_files)

这里关键的技巧是re.split(r'(\d+)', s)中括号的使用——它会保留被切分的数字部分。拆分后，数字字符串转成int，非数字部分转成小写再比较。之所以用列表作为key，是因为Python比较两个key时，会逐个比较列表里的对应元素，前面的元素相等才继续往后比。跑出来的结果就是你要的item1、item2、item10，并且由于Python的sorted是稳定排序，Item1和item1会保持它们在原数组中的相对顺序。

这个"数字与字母混排"的坑，在版本号排序、日志文件排序、报表文件名排序里非常常见。如果处理的数据量大，建议直接用成熟的自然排序库（比如Python社区里的natsort），自己写正则容易漏边界，比如负数、小数点、前缀零这些情况。

7.2 一条SQL排序为什么慢：MySQL的ORDER BY执行逻辑

后端同学最熟悉的排序场景就是SQL里的ORDER BY。你真的搞清楚过它底层在干嘛吗？MySQL执行ORDER BY大体有两条路：

• 走索引排序：如果排序列正好命中索引，InnoDB按索引叶节点的顺序扫一遍就行，根本不需要额外的排序步骤，这也是最优情况。
• filesort排序：没命中索引时，MySQL会把查询结果放进sort_buffer里排序。如果数据量超过sort_buffer_size，它会把数据分成多块，每块排好序后写到临时文件，最后再对这些有序片段做归并排序——在上一节你应该已经认出这招了。

所以你能看到，归并排序真的活在数据库里。讲这个的用意是：为什么大表无索引的ORDER BY那么慢？不只是"没索引"一个笼统解释，而是sort_buffer装不下时，磁盘临时文件的写读和归并开销会被放大几倍。此前那个两万行报表卡顿的问题，本质上也是排序策略选错的缩影。

另一个容易踩的是排序规则。MySQL默认的utf8mb4_general_ci不区分大小写，对中文排序也有一套自己的collation规则。你按中文排序出来的结果，可能和你以为的拼音顺序不完全一样。需要精确控制时，可以显式指定collation，或者用ORDER BY BINARY(column)按字节序排序。这些细节平时没人讲，但一碰到数据对不上，排查起来非常痛苦。

7.3 JavaScript的sort方法到底用什么算法

前端这边同样有坑。JavaScript的Array.prototype.sort在不同引擎里的实现不一样，其中最常被提到的V8引擎经历了一次明显演进：老版本对小数组用插入排序，对大数组用快速排序，所以那时候sort是不稳定的；后来的V8改用了TimSort——一种结合了归并排序和插入排序的稳定排序算法。

TimSort的思路很务实：先扫描出数组中天然有序的片段（称run），每个run用插入排序整理好，然后把这些run两两归并。它对真实世界中大量"部分有序"的数据非常友好。这也是为什么现在你在浏览器里用sort()，不再需要担心稳定性问题。

但还有一个永久不变的坑：不传比较函数时，sort()会把元素转成字符串，按UTF-16码元比较。所以数字数组[10, 2, 1]排序结果会是[1, 10, 2]。正确写法是 arr.sort((a, b) => a - b)。这个坑几乎每个月都能在代码评审里看到一次。

给前端同学一个实用建议：如果你要对一个对象数组按多个字段排序，比如先按部门再按年龄，记得利用稳定排序——先按次要字段排一次，再按主要字段排一次，那么主要字段相同的项会保持原来的次要字段顺序。如果你用不稳定的排序算法做多关键字排序，这个过程就会出错。

8. 从入门到能面试：一份排序学习的复盘路线和一些私人经验

文章最后这部分，不打算再列知识点，而是聊聊怎么把这些内容真正变成自己的东西。

8.1 学习顺序和我的复盘方法

最优学习顺序我觉得是这样的：冒泡排序建立"交换"的直觉，选择排序理解"选择最小值"并接触循环不变量，插入排序感受"近乎有序输入的巨大优势"，归并排序吃透分治和稳定性，快速排序深入partition和复杂度退化，堆排序把数据结构接进来。有余力再看计数排序、基数排序和桶排序，它们对特定数据范围有奇效。

每学完一个排序，我只做三件事：

1. 不看参考，手写代码，直到一次写对为止。一遍写不对就再写一遍，重点观察自己在哪个边界条件上出错。
2. 用一个随机数组跑一遍，再用断言校验有序。光看不跑，永远不知道自己写的代码是不是恰好撞对了运气。
3. 在纸上画出前几次交换的过程，特别是选择排序和快速排序的分区过程。很多人理解不了"不稳定"到底什么意思，就是因为从没在纸上看过具体元素是怎么交换的。

8.2 那些面试里高频出现的排序变种

学完基础排序后，有几道经典变种题能起到"检验是否真懂"的作用：

• 链表排序：为什么通常用归并而不是快排？因为链表不支持随机访问，快排的partition需要频繁跳访问，效率极差；归并只需顺序遍历，空间O(log n)的递归栈开销可接受。
• 逆序对计数：用归并排序，在merge过程中统计右半元素比左半元素小的情况，顺手就做完了，复杂度O(n log n)。这个题目我第一次见时完全想不到能跟排序扯上关系。
• TopK问题：使用堆，前面已经详细讲过。要注意的是求最大K个用最小堆，求最小K个用最大堆，这个反直觉的设计最容易记反。
• 荷兰国旗问题：把数组按三种颜色分类，其实是三分区partition的变形，理解它对快速排序处理大量重复元素很有帮助。

8.3 一点个人体会

写这篇排序学习实例的过程中，我重新把六种排序全部手写了一遍。每次重写都有新收获：以前觉得冒泡排序和插入排序差不多，现在能清楚说出一个交换频繁一个平移频繁；以前觉得归并排序和快速排序都是分治，现在能讲明一个靠"合并时的有序性"一个靠"分区时的基准值"；以前觉得O和θ只是符号游戏，现在写代码时会下意识判断我说的复杂度到底是上界还是紧界。

如果你学排序时觉得"背代码没用"，我特别理解。排序算法的正确打开方式，是搞清楚数据在每一步是怎么流动的，然后让代码去忠实描述这个流动过程。一旦你脑子里有了"数据流动"的画面，堆排序的下沉操作、归并排序的合并操作、快排的partition操作，全都变成了顺理成章的事。

最后说个小技巧：每次写完一个排序算法，在数组变化的关键节点打日志，把每一轮结束后的数组打印出来。纸上模拟虽然笨，但它比任何讲解都来得直接。这个方法帮我搞清楚了选择排序为什么不稳定，帮我发现了快排最坏退化的数组形态，也帮我建立了对稳定性的直觉。排序算法是算法世界的门把手，推开门以后还有更多有意思的东西在等着。