LeetCode排序章：算法与生活的共鸣

（这份随想记录于2026.02.23，最近在整理学习笔记时再次感觉枯燥的数据结构与算法竟然也能讲解这么有意义，于是二次整理准备发出来）

新年假期将数据结构与算法的主体内容复习完毕，之后每天做几题保持手感，便不再投入过多精力于LeetCode——终于，真正开始AI与机器人领域的学习了。最后几天读到《排序算法》章末，颇受触动。这段文字将数学原理讲得通透，又不失幽默，且意涵早已超越算法本身，引人反观生活。二分思想部分，”一尺之捶，日取其半，logn世竭”的化用让我想到：许多被奉为人生哲理的大道理，在数学家眼中不过是可推导的逻辑，并无神秘可言。这让那些听起来格外抚慰人心的华语骤然褪色——一切皆有章法。我想，数学家的孤独或许正源于此：身心灵的慰藉在此处失效，唯有逻辑冰冷而诚实地运转。 “治”的过程被比作《活着》里的那句话：”小鸡长大了就变成了鹅，鹅长大了，就变成了羊，羊再长大了，就变成了牛……”初读只觉无厘头，下一秒却像被什么戳中了——这不就是文学版的量变引起质变吗？所有的成长都不会浪费，只要持续积累，终会有一个奇点让过往悉数兑现。后文的猴子排序听着荒诞，却真有严谨的数学家亲自实践。一本正经地做无厘头的事，严肃得好玩。至于睡眠排序，读完后我想：若我是老板，手下员工交出这等算法，我必深吸一口气告诉自己莫激动——问题终究是能解决的，无非慢些。员工既是我招的，他们能想出如此”优秀”的算法，也有我的一份”功劳”。最后的奇迹排序像是全章的升华。时间复杂度为正无穷的算法，竟能被写进教材，其价值已上升到人生哲理的高度。作者总结：若只是等待、什么也不做，终将一事无成。但我觉得这解读稍嫌狭隘。正如猴子排序——等待够久，说不定宇宙射线就让内存bit位翻转、数据自愈了呢？真正上过班的人或许有类似体验：一个棘手的难题搁在那儿，过段时间竟自然而然消解了，或问题本身就不复存在了。这难道不是奇迹算法的某种应用？甚至，难题放久了，工作没了，或公司没了，算不算某种维度的”解决”？当然，最后这部分纯属开脑洞，当不得真。遇到问题，最优解仍是正面应对——就像我现在想换工作，虽然有了AI，虽然之后大部分是Vibe Coding，但是作为基本功测试必过在线测评，既然绕不开刷题，便坦然拥抱，将能做的事做到最好。与君共勉。

（排序算法章节内容节选，原文链接见文末）

归并排序：

总结起来，归并排序分成两步，一是拆分数组，二是合并数组，它是分治思想的典型应用。分治的意思是“分而治之”，分的时候体现了二分的思想，“一尺之棰，日取其半，logn 世竭”，治是一个滚雪球的过程，将 1 个数字组成的有序数组合并成一个包含 2 个数字的有序数组，再将 2 个数字组成的有序数组合并成包含 4 个数字的有序数组…如《活着》一书中的经典名句：“小鸡长大了就变成了鹅；鹅长大了，就变成了羊；羊再长大了，就变成了牛…”

猴子排序：

$1913$ 年，法国数学家埃米尔·博雷尔出版了一本谈概率的书籍，其中介绍了「打字的猴子」概念，引发了「无限猴子定理」这个有趣的实验构想。

无限猴子定理：让一只猴子在打字机上随机地按键，当按键时间达到无穷时，几乎必然能够打出任何给定的文字，比如莎士比亚的全套著作。

这个理论说明「把一个很大但有限的数看成无限」的推论是错误的。猴子精确地通过键盘敲打出一部完整的作品发生的概率是极其低的，但并不是零。

2003 年，普利茅斯大学艺术媒体实验室课程的教师和学生使用 2,000 英镑津贴做了这个实验，结果打出了 5 张几乎全是S的纸，没有一个完整的句子。

无限猴子定理启发出了一个排序算法：把待排序的数组交给猴子，只要猴子不断地打乱数组，总会有一次排序成功！这个算法被称为猴子排序，英文名是 bogo-sort（英文名源于 Quantum bogodynamics）。其中，可以使用「快速排序」章节中介绍的洗牌算法来打乱数组。

Random random = new Random();

private void bogoSort(int[] arr) {
while (true) {
if (isAscendingSorted(arr)) break;
shuffle(arr);
}
}

public void shuffle(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int swapPosition = random.nextInt(i + 1);
int temp = arr[i];
arr[i] = arr[swapPosition];
arr[swapPosition] = temp;
}
}

private boolean isAscendingSorted(int[] arr) {
if (arr == null || arr.length < 2) return true;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) return false;
}
return true;
}

意大利面排序：

1984 年，加拿大数学家亚历山大·杜德尼（Alexander Dewdney）在「Scientific American」杂志上发表了意大利面排序算法（Spaghetti sort）。

意大利面排序：首先，取一把未煮的意大利面，对于数组中的每一个数字，剪一根对应长度的意大利面条，用这根面条代表这个数字。用一只手拿着这一把面条，将其竖着立在桌子上，保证每一根的底部都碰到桌面。另一只手从面条的上方缓缓下落。显然，这只手碰到的第一根面条就是最长的，将其取出放至首位。重复此过程直至所有的面条取完，数字就完成了排序。

为什么要用意大利面呢？兰州拉面请求出战可不可以？这或许是因为意大利面是由小麦品种中最硬质的杜兰（durum）磨粉制成，较为坚硬，在桌上立得稳～

从排序流程可以看出，意大利面排序并不是什么新鲜的算法，它类似于「计数排序」章节中介绍的「伪计数排序」。

public static void spaghettiSort(int[] arr) {
// 假设数字大小都在 1～9 之间，准备一把长度在 1～9cm 之间的面条，用面条的长度记录数字大小。
// 注：为了便于理解，新建长度为 10 的数组，只使用数组的 1～9 位，不使用数组的第 0 位
int[] spaghettiLength = new int[10];
// 遍历数组中的每个数字
for (int element : arr) {
// 将每个数字的大小反映成面条的长短
spaghettiLength[element]++;
}
// 右手从高处落下，碰到的第一根面条对应的数字就是最大的数字，重复此过程直到排序完成
for (int i = 9, index = 0; i >= 1; i--) {
while (spaghettiLength[i] != 0) {
spaghettiLength[i]--;
arr[index++] = i;
}
}
}

由于「Scientific American」是美国发行的科普杂志，所以笔者猜测此算法诞生的目的是用通俗的方式向大众普及算法的魅力，每位读者都可以在家中轻易地做此实验。

睡眠排序：

睡眠排序是由当代网友们想出来的排序算法，传闻中发明此算法的程序员已被老板开除。

排序思路是：遍历数组，为每个数字开启一个线程。这个数字有多大，这个线程就睡眠多少秒。待线程睡醒后，输出此数字。利用「小的数字所在的线程会先于大的数字所在的线程醒来」这个特性完成排序。

举个例子，比如公司要对员工按年龄排序，那么睡眠排序的思路就是：为每个员工分配一个房间，自己有多少岁就在房间里睡多少个小时。员工睡醒后就走出房间，老板按照员工出房间的顺序完成排序。

public static void sleepSort(int[] arr) {
for (final int number : arr) {
new Thread(new Runnable() {
@Override
public void run() {
try {
Thread.sleep(number * 1000L);
System.out.println(number);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
}
}

由于此算法可能由于数字过大而迟迟不能算出结果，所以又被称之为「天地同寿排序法」。

整个过程只需要遍历一次数组，所以时间复杂度为O(n) 吗？在 stack overflow 上对此有过讨论，讨论的结果是它的时间复杂度应该是 O(max(input)+n)，这个表达式很奇怪，大多数排序算法的时间复杂度都只与数据量有关，而睡眠排序却是与数据本身有关。这一点类似于计数排序，计数排序的空间复杂度就和数据本身有关。所以我们可以说睡眠排序的时间复杂度是 O(n) 或 O(k)（k 表示数据范围，另外，想要达到 O(k)，还需要将所有数据都减去最小值）。O(n) 基于数据量，O(k) 基于数据本身。但这里的 O(k) 并不是真的那么快，它和数据的规模是两个维度的东西。或许讨论睡眠排序的时间复杂度是没有意义的，读者不妨在留言区说出你的看法。由于开启线程需要一些内存开销，所以空间复杂度为 O(n)。需要注意的是，线程的调度是由操作系统决定的，开发者无法控制操作系统何时调用哪一个线程。而且线程的调度也需要一定时间，所以睡眠排序算法不一定能得出正确的结果。

奇迹排序：

今天，业务部门让我给数组排序，我拿到数据后，马上检查了一下他们给我的数组是否有序。噢！糟糕，它是无序的！然后我静静等待了了两秒钟，又检查了一遍。噢！为什么？它还是无序的！那我待会再来检查看看，一定会有神迹发生。

public static void miracleSort(int[] arr) throws InterruptedException {
while (true) {
if (isSorted(arr)) break;
// 还没排好序，再等等...
Thread.sleep(2000);
}
}
private static boolean isSorted(int[] arr) {
if (arr == null || arr.length < 2) return true;
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) return false;
}
return true;
}

时间复杂度，空间复杂度。恭喜奇迹排序以最高时间复杂度获得了本次最慢排序大赛的冠军！🏆 奇迹排序或许没有任何实际意义，但它却可以有一个哲学角度的解释：如果只是等待，什么也不做，终究只会一事无成。

以上就是在《排序算法》章节非常有意思的一些内容，强烈建议刷LeetCode的同学，认真看一看这一章节，讲解浅显易懂很用心，是我看过的LeetCode感觉质量最好的几个章节之一。另外同事提醒今天是5.20，想到还有几个题的解法非常有意思，很契合5.20这个主题，作为旧闻重发的收尾吧：

160. 相交链表：走到尽头见不到你，于是走过你来时的路，等到遇见时才发现，你也走过我来时的路。