我到现在还记得那个项目——后台导出一张两万行的报表前端点一下表头排序要卡两到三秒。一开始以为是后台接口慢查了半天才发现前任开发在浏览器端用冒泡排序处理数据每条记录还带一串字符串比较。那个瞬间我就明白了排序这个看起来谁都会写的东西学不学得扎实在真实系统里天差地别。这篇排序算法学习实例不是说排序很重要就完了而是把我自己从零开始啃排序的完整过程摊开来讲为什么冒泡、选择、插入要先学归并和快排的核心思路差在哪堆排序为什么既优雅又有点尴尬以及最容易被忽略的复杂度记号问题——什么时候该写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个元素并且它们已经排好序。用归纳法来证明初始化当i0时前0个元素天然有序命题成立。保持假设迭代开始前前i个元素是有序的且是全局最小的i个。内层循环从i开始往后找最小元素的下标min_idx找到后与a[i]交换。交换后前i1个元素就是全局最小的i1个且有序。因此下一次迭代开始时命题依然成立。终止当in时前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 分、治、合三步走的结构归并排序遵循一个极其清晰的三段式分Divide把数组从中间切成两半。治Conquer递归地对左半和右半各自排序。合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这时候就需要外部排序。外部排序的基本思路就是归并排序的工程放大版把大文件切成多个内存放得下的小块。对每个小块用快速排序或插入排序排好写回磁盘作为有序片段。然后用多路归并的方式同时打开多个有序片段不断取最小的元素写出到最终文件。你看到的大数据框架里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 1Lomuto分区的逻辑i指向最后一个小于pivot的区域的末尾j从头扫到尾遇到比pivot小的元素就把它换到前面去。最后把pivot换到i1位置。建议你强制自己把这个分区过程在纸上模拟几遍因为这是快排最容易写错的地方。另一个经典分区是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代码排序肉眼可见地慢。解决办法有三个层次随机选pivotpartition之前随机交换一个元素到末尾让每次选中极值的概率变得极低。三数取中取首、中、尾三个元素的中位数作pivot对几乎有序的数组很有效。小区间优化递归到长度小于十几的子数组时改用插入排序减少递归调用开销。快速排序不稳定。比如数组[3a, 3b, 1]partition过程中两个3的相对顺序可能被打乱。这在实际业务里是个大坑尤其你按多个字段依次排序的时候。5. 堆排序用完全二叉树实现原地排序堆排序是我学排序算法时感觉最吃力、但学完收获最大的一章。它第一次让我意识到排序的本质不只是相邻比较或分治切分还可以借助一个抽象数据结构来组织数据。5.1 堆到底是什么堆是一棵完全二叉树用数组就能存。任意节点下标i左孩子是2i1右孩子是2i2父节点是(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^(h1)个。总代价Σ h×n/2^(h1)求和结果是O(n)。我第一次看到这个推导时很惊讶——原来从下往上建堆大部分节点几乎不需要调整。堆排序的完整流程建堆把数组调整成一个大顶堆。交换把堆顶最大值换到数组末尾堆大小减1。堆化对新堆顶重新向下调整恢复大顶堆。重复步骤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(n)O(n²)O(n²)O(1)稳定选择排序θ(n²)θ(n²)θ(n²)O(1)不稳定插入排序θ(n)θ(n²)θ(n²)O(1)稳定归并排序θ(n log n)θ(n log n)θ(n log n)O(n)稳定快速排序θ(n log n)θ(n log n)O(n²)O(log n)不稳定堆排序θ(n log n)θ(n log n)θ(n log n)O(1)不稳定注意这张表里我故意混用了O和θ看懂这张表你也就看懂了这两个符号的区别。6.3 一个具体的推导例子以插入排序为例。外层循环i从1到n-1内层while在最坏情况下要把key一路挪到位置0所以内层执行次数是12...(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, keynatural_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和复杂度退化堆排序把数据结构接进来。有余力再看计数排序、基数排序和桶排序它们对特定数据范围有奇效。每学完一个排序我只做三件事不看参考手写代码直到一次写对为止。一遍写不对就再写一遍重点观察自己在哪个边界条件上出错。用一个随机数组跑一遍再用断言校验有序。光看不跑永远不知道自己写的代码是不是恰好撞对了运气。在纸上画出前几次交换的过程特别是选择排序和快速排序的分区过程。很多人理解不了不稳定到底什么意思就是因为从没在纸上看过具体元素是怎么交换的。8.2 那些面试里高频出现的排序变种学完基础排序后有几道经典变种题能起到检验是否真懂的作用链表排序为什么通常用归并而不是快排因为链表不支持随机访问快排的partition需要频繁跳访问效率极差归并只需顺序遍历空间O(log n)的递归栈开销可接受。逆序对计数用归并排序在merge过程中统计右半元素比左半元素小的情况顺手就做完了复杂度O(n log n)。这个题目我第一次见时完全想不到能跟排序扯上关系。TopK问题使用堆前面已经详细讲过。要注意的是求最大K个用最小堆求最小K个用最大堆这个反直觉的设计最容易记反。荷兰国旗问题把数组按三种颜色分类其实是三分区partition的变形理解它对快速排序处理大量重复元素很有帮助。8.3 一点个人体会写这篇排序学习实例的过程中我重新把六种排序全部手写了一遍。每次重写都有新收获以前觉得冒泡排序和插入排序差不多现在能清楚说出一个交换频繁一个平移频繁以前觉得归并排序和快速排序都是分治现在能讲明一个靠合并时的有序性一个靠分区时的基准值以前觉得O和θ只是符号游戏现在写代码时会下意识判断我说的复杂度到底是上界还是紧界。如果你学排序时觉得背代码没用我特别理解。排序算法的正确打开方式是搞清楚数据在每一步是怎么流动的然后让代码去忠实描述这个流动过程。一旦你脑子里有了数据流动的画面堆排序的下沉操作、归并排序的合并操作、快排的partition操作全都变成了顺理成章的事。最后说个小技巧每次写完一个排序算法在数组变化的关键节点打日志把每一轮结束后的数组打印出来。纸上模拟虽然笨但它比任何讲解都来得直接。这个方法帮我搞清楚了选择排序为什么不稳定帮我发现了快排最坏退化的数组形态也帮我建立了对稳定性的直觉。排序算法是算法世界的门把手推开门以后还有更多有意思的东西在等着。
从冒泡到快排：排序算法与时间复杂度实战学习指南
我到现在还记得那个项目——后台导出一张两万行的报表前端点一下表头排序要卡两到三秒。一开始以为是后台接口慢查了半天才发现前任开发在浏览器端用冒泡排序处理数据每条记录还带一串字符串比较。那个瞬间我就明白了排序这个看起来谁都会写的东西学不学得扎实在真实系统里天差地别。这篇排序算法学习实例不是说排序很重要就完了而是把我自己从零开始啃排序的完整过程摊开来讲为什么冒泡、选择、插入要先学归并和快排的核心思路差在哪堆排序为什么既优雅又有点尴尬以及最容易被忽略的复杂度记号问题——什么时候该写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个元素并且它们已经排好序。用归纳法来证明初始化当i0时前0个元素天然有序命题成立。保持假设迭代开始前前i个元素是有序的且是全局最小的i个。内层循环从i开始往后找最小元素的下标min_idx找到后与a[i]交换。交换后前i1个元素就是全局最小的i1个且有序。因此下一次迭代开始时命题依然成立。终止当in时前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 分、治、合三步走的结构归并排序遵循一个极其清晰的三段式分Divide把数组从中间切成两半。治Conquer递归地对左半和右半各自排序。合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这时候就需要外部排序。外部排序的基本思路就是归并排序的工程放大版把大文件切成多个内存放得下的小块。对每个小块用快速排序或插入排序排好写回磁盘作为有序片段。然后用多路归并的方式同时打开多个有序片段不断取最小的元素写出到最终文件。你看到的大数据框架里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 1Lomuto分区的逻辑i指向最后一个小于pivot的区域的末尾j从头扫到尾遇到比pivot小的元素就把它换到前面去。最后把pivot换到i1位置。建议你强制自己把这个分区过程在纸上模拟几遍因为这是快排最容易写错的地方。另一个经典分区是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代码排序肉眼可见地慢。解决办法有三个层次随机选pivotpartition之前随机交换一个元素到末尾让每次选中极值的概率变得极低。三数取中取首、中、尾三个元素的中位数作pivot对几乎有序的数组很有效。小区间优化递归到长度小于十几的子数组时改用插入排序减少递归调用开销。快速排序不稳定。比如数组[3a, 3b, 1]partition过程中两个3的相对顺序可能被打乱。这在实际业务里是个大坑尤其你按多个字段依次排序的时候。5. 堆排序用完全二叉树实现原地排序堆排序是我学排序算法时感觉最吃力、但学完收获最大的一章。它第一次让我意识到排序的本质不只是相邻比较或分治切分还可以借助一个抽象数据结构来组织数据。5.1 堆到底是什么堆是一棵完全二叉树用数组就能存。任意节点下标i左孩子是2i1右孩子是2i2父节点是(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^(h1)个。总代价Σ h×n/2^(h1)求和结果是O(n)。我第一次看到这个推导时很惊讶——原来从下往上建堆大部分节点几乎不需要调整。堆排序的完整流程建堆把数组调整成一个大顶堆。交换把堆顶最大值换到数组末尾堆大小减1。堆化对新堆顶重新向下调整恢复大顶堆。重复步骤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(n)O(n²)O(n²)O(1)稳定选择排序θ(n²)θ(n²)θ(n²)O(1)不稳定插入排序θ(n)θ(n²)θ(n²)O(1)稳定归并排序θ(n log n)θ(n log n)θ(n log n)O(n)稳定快速排序θ(n log n)θ(n log n)O(n²)O(log n)不稳定堆排序θ(n log n)θ(n log n)θ(n log n)O(1)不稳定注意这张表里我故意混用了O和θ看懂这张表你也就看懂了这两个符号的区别。6.3 一个具体的推导例子以插入排序为例。外层循环i从1到n-1内层while在最坏情况下要把key一路挪到位置0所以内层执行次数是12...(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, keynatural_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和复杂度退化堆排序把数据结构接进来。有余力再看计数排序、基数排序和桶排序它们对特定数据范围有奇效。每学完一个排序我只做三件事不看参考手写代码直到一次写对为止。一遍写不对就再写一遍重点观察自己在哪个边界条件上出错。用一个随机数组跑一遍再用断言校验有序。光看不跑永远不知道自己写的代码是不是恰好撞对了运气。在纸上画出前几次交换的过程特别是选择排序和快速排序的分区过程。很多人理解不了不稳定到底什么意思就是因为从没在纸上看过具体元素是怎么交换的。8.2 那些面试里高频出现的排序变种学完基础排序后有几道经典变种题能起到检验是否真懂的作用链表排序为什么通常用归并而不是快排因为链表不支持随机访问快排的partition需要频繁跳访问效率极差归并只需顺序遍历空间O(log n)的递归栈开销可接受。逆序对计数用归并排序在merge过程中统计右半元素比左半元素小的情况顺手就做完了复杂度O(n log n)。这个题目我第一次见时完全想不到能跟排序扯上关系。TopK问题使用堆前面已经详细讲过。要注意的是求最大K个用最小堆求最小K个用最大堆这个反直觉的设计最容易记反。荷兰国旗问题把数组按三种颜色分类其实是三分区partition的变形理解它对快速排序处理大量重复元素很有帮助。8.3 一点个人体会写这篇排序学习实例的过程中我重新把六种排序全部手写了一遍。每次重写都有新收获以前觉得冒泡排序和插入排序差不多现在能清楚说出一个交换频繁一个平移频繁以前觉得归并排序和快速排序都是分治现在能讲明一个靠合并时的有序性一个靠分区时的基准值以前觉得O和θ只是符号游戏现在写代码时会下意识判断我说的复杂度到底是上界还是紧界。如果你学排序时觉得背代码没用我特别理解。排序算法的正确打开方式是搞清楚数据在每一步是怎么流动的然后让代码去忠实描述这个流动过程。一旦你脑子里有了数据流动的画面堆排序的下沉操作、归并排序的合并操作、快排的partition操作全都变成了顺理成章的事。最后说个小技巧每次写完一个排序算法在数组变化的关键节点打日志把每一轮结束后的数组打印出来。纸上模拟虽然笨但它比任何讲解都来得直接。这个方法帮我搞清楚了选择排序为什么不稳定帮我发现了快排最坏退化的数组形态也帮我建立了对稳定性的直觉。排序算法是算法世界的门把手推开门以后还有更多有意思的东西在等着。
