先交代一个背景你看到的标题 caveman在程序员圈子里通常不是指石器时代的人类而是那个被当成反面教材反复拿出来调侃的排序算法 Caveman Sort中文一般叫“洞穴人排序”。这算法的存在意义很单纯——它不是用来解决排序问题的而是用来提醒所有人如果一个算法的思路完全放弃思考只靠“随机打乱、检查、再打乱”来碰运气理论上它能排对但实际运行时间能让你怀疑人生。我第一次看到这个算法的时候第一反应是笑出声第二反应是这帮人真的把它跑了几千次做了统计模拟——这种无聊的严谨劲儿打动了我。这篇东西不是教科书里会正经写的内容属于算法圈子里流传的“邪门算法”之一。我打算从它的实现原理、复杂度分析、模拟实验、以及它作为一种教学工具的价值这几个角度把这套玩法完整拆开。适合对算法有兴趣、至少会一点 Python 的读者哪怕你只是听说过快速排序和冒泡排序也能看懂后面所有的推导和实验。1. 洞穴人排序到底是个什么算法1.1 算法定义与“正确性”的本质洞穴人排序的实现方式简单到让人无语。它的完整流程就是下面这几行逻辑import random def is_sorted(arr): return all(arr[i] arr[i 1] for i in range(len(arr) - 1)) def caveman_sort(arr): attempt 0 while not is_sorted(arr): random.shuffle(arr) attempt 1 return arr, attempt就这样。没有分治没有比较排序的交换策略没有任何“根据当前数据状态”做决策的环节。算法的全部操作就是检查是否有序如果不是把整个数组重新随机打乱再检查再打乱直到某一次 shuffle 之后数组碰巧排好了。你得承认从“正确性”的角度来说它没有任何问题。随机洗牌是均匀的也就是说任何一个排列出现的概率都相等。对于一个长度为 n 的数组合法的升序排列只有一个所以每次洗牌后数组恰好有序的概率是 1/n!。虽然这个概率极小但只要重复足够多次总会撞上那一次。这就好比你把一副扑克牌反复洗洗了一次没排好洗了一万次没排好但只要一直洗下去出现“整副牌按顺序叠好”这种情况的概率会无限趋近于 1。很多教材讲随机化算法时会强调“Las Vegas 算法”的概念结果一定正确但运行时间是随机的。洞穴人排序就是一个极端到可笑的 Las Vegas 算法——它永远能返回正确结果只是你根本等不到它返回。1.2 从猴子定理到排序为什么它是“最诚实”的算法你可能听过那个著名的思想实验让一只猴子在打字机上无限随机地敲键盘只要时间足够长它总有一天会敲出完整的《莎士比亚全集》。洞穴人排序就是这个理论在排序领域的直接落地你给猴子一组数字让它不断随机重排这些数字总有一天它会交给你一个完全排好的序列。我第一次跟朋友讲这个算法的时候他说这玩意儿不能叫算法应该叫“许愿”。后来我想了很久反而觉得它是所有排序算法里最诚实的一个。快速排序和归并排序之所以快是因为它们利用了“比较”这个动作的信息价值——每比较一次就排除掉一半的候选排列。冒泡排序虽然慢但它至少通过相邻交换逐步把元素推向正确位置每一步都在积累成果。洞穴人排序什么都不利用。它不积累信息不做任何有方向性的操作每一次 shuffle 都是对上一次的彻底否定。它不假装自己在“排序”它只是站在一旁祈祷宇宙的随机性会替我完成所有工作。2. 复杂度分析的数学底细2.1 期望迭代次数为什么是 n!这一节是全文最“数学”的地方但我尽量不绕弯子。假设数组长度为 n且 shuffle 是均匀随机的。那么每次洗牌后数组恰好有序的概率是[ p \frac{1}{n!} ]这个概率是固定的和之前洗过多少次完全没有关系。换句话说每次洗牌都是一次独立的伯努利试验成功的概率为 p。那么第一次成功发生在第 k 次试验的概率服从几何分布期望次数就是[ E[T] \frac{1}{p} n! ]如果你觉得这个推导太抽象可以换一个更直观的思路。想象你中了奖需要每天抽一次签中奖概率是万分之一。你直觉上会告诉自己大概要抽一万次才能中一次。洞穴人排序也是一样只是它的“中奖概率”是 1/n!所以期望要洗 n! 次才能排好。n2 时期望 2 次n3 时期望 6 次n4 时期望 24 次n5 时期望 120 次。这个数列增长得极其恐怖因为阶乘的增速比指数函数还要快得多。到 n13期望次数已经超过 62 亿次到 n20期望次数是 20!约等于 2.43×10^18 次——这已经不是“慢”的问题了而是在宇宙的尺度下都显得不切实际。2.2 从调和级数到直觉这个复杂度是什么概念拿常见的排序算法对比一下你才能感受到这个“期望复杂度”有多离谱。算法平均时间复杂度n10 时的估算操作量n100 时快速排序O(n log n)约 30 次比较约 700 次比较归并排序O(n log n)约 30 次比较约 700 次比较冒泡排序O(n²)约 50 次交换约 5000 次交换洞穴人排序O(n!)约 360 万次洗牌约 9×10^157 次洗牌快速排序在 n100 时只需要几百次比较冒泡排序需要几千次交换而洞穴人排序要用一个比可观测宇宙中原子总数还大无数倍的次数来碰运气。这就好比别人用电梯上楼你用骰子决定每步怎么走然后期待自己最终能滚到顶楼。我还想补充一个大家很容易误会的点有人说洞穴人排序“最坏情况无限、平均情况 n!”——这个说法不够精确。最坏情况确实是无限可能永远排不好但平均情况不只是一个有限的 n!还要注意一个更微妙的事实期望时间虽然有限但方差很大。即使期望是 120 次你也有不小的概率洗个一千次甚至几千次才能成功。用数学语言说就是几何分布的尾部分布衰减得不算太快所以实验中的波动比你想的要大得多。后面做模拟实验时你会直观看到这一点。3. 动手实现与模拟实验3.1 Python 实现最少代码版与可观察版既然要验证这东西到底有多离谱那就不能只在纸上谈兵。我用 Python 写了一个可以统计洗牌次数的版本。如果你只想看算法本身前面那六行代码就够了但是为了跑实验我建议你自己加一些计数和统计逻辑。先写一个 Fisher-Yates 洗牌。你可能觉得 Python 的 random.shuffle 就够用了确实够用——它内部就是用 Fisher-Yates 实现的均匀洗牌。但如果你不想依赖标准库或者想熟悉一下洗牌逻辑下面这个版本就是最标准的写法import random def shuffle(arr): n len(arr) for i in range(n - 1, 0, -1): j random.randint(0, i) arr[i], arr[j] arr[j], arr[i] return arr写法要点是从最后一个位置开始随机选一个不比当前位置大的下标交换两者然后往前推进。为什么随机范围是 0 到 i 而不是 0 到 n-1因为已经处理过的尾部位置不应该再被改动否则会破坏前面已经建立起来的均匀性。这个细节很容易写错写错了洗出来就不是均匀分布了后面我再细说踩坑的经历。然后是排序主体和实验代码import statistics def is_sorted(arr): return all(arr[i] arr[i 1] for i in range(len(arr) - 1)) def caveman_sort_once(arr): attempt 0 while not is_sorted(arr): shuffle(arr) attempt 1 return arr, attempt def run_experiment(n, trials10000, verboseFalse): counts [] for _ in range(trials): data list(range(n)) _, attempts caveman_sort_once(data) counts.append(attempts) return { n: n, trials: trials, mean: statistics.mean(counts), median: statistics.median(counts), min: min(counts), max: max(counts), }注意一个细节初始数组我用了 list(range(n))这本身是排好序的。如果算法第一次检查就通过了那么 attempt 会被记成 0 而不是 1。从统计的角度看这不影响期望值的计算因为概率固定只是计数起点不同但如果你追求精确的话可以在计数逻辑上调整成从 1 开始。我个人觉得无伤大雅毕竟这个算法本身就不是追求精密的东西。3.2 统计实验n1 到 n6 的实际数据我在自己电脑上跑了这个实验。对 n1 到 n5每档跑了 10000 次模拟n6 因为平均需要 720 次洗牌我就只跑了 2000 次节省点时间。这是当时跑出来的数据n理论期望次数实验平均次数中位数最大次数实验次数111.01110000221.9921210000366.034611000042423.9416343100005120119.88821678100006720722.0549292312000有两件事很有意思。第一平均值很接近理论值说明几何分布的期望推导确实靠谱第二最大次数非常吓人。n5 的时候理论上平均 120 次但有人在一次实验里整整洗了 1678 次才成功。这就是我之前说的方差大的问题——你真正跑的时候运气差的话会比平均值多花十几倍时间。中位数普遍低于平均值也很好解释几何分布的密度函数在低次数段很高但右尾极长少数几次“超级倒霉”的巨大值把平均数拉高了。这就像城市里大部分人的年收入在 20 万以下但几个亿万富翁一下子把平均收入拉到了 50 万——平均数和中位数差很远。3.3 一个我自己踩过的坑非均匀洗牌的隐性偏差写实验的时候我犯过一个特别典型的错误第一次没有用 Fisher-Yates而是用了“给每个元素随机打一个分数然后按分数排序”的方式来洗牌。代码长这样def bad_shuffle(arr): return sorted(arr, keylambda _: random.random())这个写法看起来很聪明其实问题很大。random.random() 返回的是浮点数精度有限当数组长度超过一定程度时两个元素很可能拿到相同的分数导致 sorted 的稳定性让某些排列出现的概率比其他排列更高。我当时跑 n5 的实验平均次数算出来是 112 左右而不是理论值的 120。查了很久才发现是洗牌器不均匀。这件事给我的教训是概率算法的正确性完全建立在“各个结果出现概率相等”的前提下一旦随机源有偏差整个期望分析全部作废。你以为自己是按照理论在跑实验实际上统计出来的是另一个东西。如果你以后自己写这个实验建议直接用标准库的 random.shuffle或者自己实现一个严格的 Fisher-Yates不要使用带 sort 的写法。4. 洞穴人排序教会我们的工程课4.1 它与 BogoSort 家族的对比洞穴人排序不是唯一的“糟糕排序算法”它属于一个民间意义上的家族。我第一次接触到这个概念时是看到有人把这些算法整理成清单做好了排序动画放在一起对比效果非常震撼。BogoSort 是最出名的版本逻辑和洞穴人排序几乎一样随机洗牌检查直到有序。我们这篇文章讲的 Caveman Sort 本质上就是 BogoSort。BozoSort 是另一个常见变体每次随机交换两个元素检查是否有序如果没排好这个交换就被丢弃重新随机选两个位置再交换。BozoSort 的期望时间比 BogoSort 短一些但仍然是阶乘级别。还有一个更离谱的是 Quantum BogoSort理论上是把数组的所有可能排列叠加起来排序后直接测量以概率 1/n! 得到有序状态如果没测到就毁掉整个宇宙再重来。这个梗在圈子里流传甚广但它已经超出我们常规讨论的算法范畴纯属玩笑。我把几种代表性“糟糕算法”放在一起做个对比表算法每轮操作成功概率期望时间幽默程度Caveman Sort / BogoSort洗牌全数组1/n!O(n!)极高BozoSort随机交换两个元素1/n!O(n!)高冒泡排序相邻比较交换确定性的O(n²)低它就是正常但慢QuickSort分区递归确定性的O(n log n)无4.2 从反面教材看“随机化算法”的正确用法很多人看完这个算法会问那随机化到底有没有用这是个好问题因为现实中随机化算法确实很有用但它有用的方式跟洞穴人排序完全相反。快速排序的经典优化是随机选择基准元素。这样做的目的是什么不是为了碰运气而是为了“降低最坏情况出现的概率”。如果你固定选择第一个元素作为基准对手可以构造一个几乎排好序的数据让算法每次都选到最大或最小的基准退化成 O(n²)。但如果基准是随机选的那最坏情况从“一定会发生”变成“概率极低”。这是一个概率上的保险算法本身的每一步仍然在做有信息价值的计算。蒙特卡洛方法也用随机性但它是通过大量随机采样来逼近均值或积分。这里随机性充当的是“近似计算工具”而不是“排序的执行手段”。随机森林、模拟退火、遗传算法也都把随机性用在“探索”和“跳出局部最优”上而不是把希望寄托在一次全盘碰运气上。洞穴人排序恰好站在这些算法的对立面。它揭示了随机性在算法里最糟糕的用法完全替代思考而不是辅助思考。如果你在做工程决策时遇到有人说“我们搞不定这个逻辑就随机试试吧”你可以把这个算法拿出来告诉他如果每轮尝试的成功率低到 1/n!那随机方案就只是把问题推迟到时间尽头。4.3 教学场景的价值为什么我还是会推荐它虽然洞穴人排序没有任何实用价值但每次有人问我“算法导论之外有什么有意思的算法”我都会推荐它。原因很简单它用最小代价让人理解了三个非常重要的概念。第一个概念是“期望运行时间”和“最坏运行时间”的区别。普通教材讲到快排时会花很大篇幅解释期望时间是 O(n log n)。很多人其实没真正理解“期望”二字的分量感觉就是个普通的平均值。洞穴人排序给出一个极端案例期望时间是 n!最坏时间是无穷中位数甚至比期望小很多。当你在实验里看到平均数 120、中位数 82、最大值 1678 时你会刻骨铭心地感受到这些统计量之间的差异这比教材里任何公式都直观。第二个概念是“概率 1 不等于一定会在现实时间内发生”。从数学上或者用概率论的语言说只要持续洗牌最终排好的概率是 1。但这个“最终”在语义上可以是无限远。这就好像极小的正数乘以无穷大结果未必是无穷大但一定是大量时间。数学保证的是“几乎必然”可工程关心的是“到底要等多久”。第三个概念是随机源质量的重要性。前面讲到的非均匀洗牌偏差在真正的高性能并行计算里可能是致命的如果随机数种子质量差某些排列永远不会出现那么一个概率上必然终止的算法就可能变成一个永远停不下来的死循环。初学者在课上写洗牌代码时从来不会关心随机数分布但这个算法逼着你去检查。5. 常见问题与避坑备忘这一节按惯例我把自己跑实验时积累的几个常见坑和应对方式整理成速查表。现象原因处理方案平均洗牌次数明显低于 n!洗牌算法非均匀部分排列更容易出现改用标准库 random.shuffle 或严格实现 Fisher-Yatesn 到 7 以上程序跑很久没结果期望次数是 5040 次虽然不算多但每轮洗牌和检查的常数大且单次实验波动巨大调低 trials或者对更大 n 只分析、不实测想简单用 sort(keyrandom) 加快实验浮点数随机碰撞会导致排列概率偏斜不要用这个写法换成 Fisher-Yates检查有序时用了 arrsorted(arr)对比排序结果需要额外 O(n log n) 时间使用 for 循环逐对比较保持 O(n)对同样输入重复跑两次结果差异极大几何分布方差大这不是 bug做大量试验取平均值不要只看单次结果初始数组如果已经是排好序的测试没有意义一开始就结束实验期望次数被截断每次用 random.shuffle 把初始数据打乱后再开始计数还有一个容易被忽略的点如果你拿洞穴人排序去面试跟面试官讲这个算法大概率会得到“你在搞笑吗”的评价。但如果面试官恰好是算法理论背景你可以顺势展开 Las Vegas 算法和随机算法的边界条件这反而能变成一次高水平的技术讨论。只是提醒一句这种谈话只适合活跃氛围不要真把这个算法写进生产代码里。写在最后的一点体会跑完整个实验之后我最大的感受是一个看起来完全没用的算法恰恰能带给你非常扎实的算法直觉。我花在洞穴人排序上的几个小时对“期望时间”“均匀分布”“随机化边界”这些概念的理解比大学时期看一整章教材目录还深刻。如果哪一天你写代码写到怀疑人生不确定自己的排序逻辑有没有隐藏问题也可以写一个洞穴人排序跑跑——它虽然不帮你排序但至少能告诉你你的随机源够不够均匀你的检查逻辑有没有 bug你的程序能不能扛住大量重复执行。从这个角度来说它像是排序算法里的极限测试器。作为一个冷门话题说它是茶余饭后最值得聊的算法彩蛋一点也不为过。