正经分享 - 从「排序算法」看「学习的道术之论」

2025年9月25日 13时 记

刚好忙完了DDL，把积压已久的灵感有感而发一下。

前面写了很多不正经的东西，终于轮到点正经的了。

虽说正经，但风格一如既往，想到哪里写到哪里。

写到最后发现，发现跟我另一篇（还没写）里想写的「守正出奇」有点联系，不如就把这篇也当作「守正出奇」三部曲的开篇吧。

1. 从术入门：看排序有哪些

在计算机发展史中，排序一直是一个核心问题，小到数据检索，大到搜索聚合，高效处理数据都离不开排序作为前置环节。正因如此，把排序称为算法设计的试金石，一点也不为过。

回顾排序算法的历史，从最直观朴素的冒泡、插入、选择排序，到之后的归并、快速、堆排序，再到后来抛弃比较排序发明的计数类排序……

这些算法，无一例外都可以看作是「术」的一种，他们都是为了解决一个问题——排序。

2. 由术见道：从排序到数据结构与算法

每一次算法的进步，都是一次规模增长与理论探索的双重驱动：当朴素方法无法支撑需求时，思想必须升级。但是升级并不是也并不是简单的推翻重建，算法千变万化，其中存在着千丝万缕的联系，这就是由术见道后的由道返术。

这里我们以冒泡排序为例，顾名思义，冒泡排序每次交换相邻元素，逐步大的元素冒到头部，其核心是「交换」。那么，我们有没有办法交换的更高效呢？

有的。当我们把交换的对象放大，不仅仅局限于相邻的2个元素，以一个元素为锚，把比它大的放到左边，比它小的放到右边，你就会惊奇地发现，它刚好处在了序列中正确的位置。

此时你还会发现，你只需要把左边和右边两个区间分别排序，就可以得到一个正确的排序序列了。

恭喜你，发明了「分治」思想。而更进一步，当你分别对两个区间重复这个过程，恭喜你，又发明了「快速排序」。

类似的，你还可以发现「归并/希尔」与「插入排序」的联系，以及「堆排」与「选择排序」的联系。

你以为到这里就结束了吗？不！当你透过归并、快速和堆排序向更深的「道」挖掘时，你甚至可以看到「比较排序」的极限。

思考这样一个数学模型，一个包含N个元素的序列，它的排列方式有N!种。比较排序等价于一个决策树模型，每一次节点比较，分支结果是「左>右」/「右>左」。

最终你得到的这棵树上的叶子节点，便是排序好的序列。恭喜你，在探究信息论约束的时候，顺手发明了排序二叉树。

假设这棵决策树的高度为h，那么理论的决策空间便是2^h，两相比较，便可以得到这样一个不等式

2^h >= n!

h >= log2(n!)

利用斯特林公式进行近似，我们便可以得到基于「比较」排序的时间复杂度极限O(NlogN)。

Moreover，排序二叉树并不一定是均衡的，为了让排序二叉树的左右子树更均衡以其最优化高度h，恭喜你，发明了「平衡二叉树」。

看到了吗？这便是排序中的道，千变万化，都逃不出这里。

3. 不止于孤立的道：道的延伸

上面两个部分，我们从排序出发，聊到了算法与思想，即「术」与「道」，而对「道」的探索与思考不应该是孤立的。

这里，我们再举一个例子，「分治」的核心是将大问题拆解成小问题。进一步，如果这些子问题存在重叠，即「重叠子问题」，恭喜你，发明了「动态规划」。

好了，现在你又多了一把锤子，让我们一起看向图论里的诸多钉子，恭喜你，利用动态规划发明了「最小生成树」和「单源最短路」算法。

最后，让我们跳出单一的学科思维，看向更广阔的天空，带着这把锤子看向离散数学，哦天呐，你可以轻松理解「传递闭包」了。

让我们再带着这把锤子看向概率论中的随机过程，是不是觉得此时「马尔可夫过程」也能轻松拿捏了？

这样的例子不胜枚举。学习便是如此，当你理解了每个术的前因后果，你便明白了其背后的道。给孤立的术和道建立联系，这便是学习的内核。

由此回头，来聊一聊最近看到的一个有趣的问题：「当代教材的设计，是为了反自学吗？」。我的看法是，是也不是。

教材就好比是一份高度浓缩的知识索引，学科是孤立的，但知识从来不是孤立的。以点带面，才能撬动数理的大厦。

4. 写在最后

术起于用，源自所需。术多而繁，不离其本。

由术入道，窥探其性，由道返术，术亦常新。

术可穷尽，暂行一时。道则恒常，纲举目张。