排序算法这个方向通常给人的印象是老老实实的 O(n log n)。但网上偶尔会出现一个标题叫“一个不该存在的排序算法”后面还跟着一句“却意外能跑通”。我第一次看到时也以为是标题党。后来自己把代码写出来跑了几轮才发现这类算法的确能跑通但不是靠常规比较而是靠概率、外部计时或者干脆绕开比较排序的边界。这篇文章就以排序算法为主题从代码实测的角度拆一拆这些反常识排序到底为什么能跑、跑到什么程度会崩、哪些可以进生产哪些只适合当学习素材。如果你常看 Stand-up Maths 这类数学与算法分享内容应该对这种“不可能但能用”的展开不陌生。它真正有意思的地方不是“某段代码很搞笑”而是背后隐藏了一个问题我们凭什么判断一个排序算法“应该存在”只看最终输出结果所有排序算法都能排序但看时间、空间、稳定性、前提假设差距就大了。下面这几类“不该存在”的排序分别对应不同的突破口。1. 先分清三类“不该存在”的排序1.1 博戈排序排序全靠随机命中的概率问题博戈排序英文叫 Bogosort也叫乱序排序、笨蛋排序。核心思路极其简单先检查数组是否有序如果无序就随机打乱再检查再打乱直到某一次碰巧得到有序结果。听起来不像算法更像在赌。但严格从数学上看它确实有终止概率只要数组长度有限随机排列总有可能落到有序排列那一种。问题是概率随数组长度迅速下降。对于 n 个不重复元素任意一次随机打乱能排好的概率是 1 / n!。n5 时期望次数是 120 次n10 时期望次数是 3628800 次。你可能会想“120 次也没多少”但 n 到 20 以后期望次数已经超过 2.4 乘以 10 的 18 次方这个量级在普通机器上不可能靠随机命中跑完。所以博戈排序属于那种“理论上存在、实践上劝退”的算法。它最适合的场景是教学和喜剧不适合任何真实排序需求。但它能跑通这件事本身并不假前提是把数组控制在非常小的规模或者接受超长等待。1.2 睡眠排序排序靠等待而不是比较的并发算法睡眠排序英文叫 Sleep Sort同样是一眼看上去不像排序算法的东西。做法是为数组里每个元素启动一个线程线程做的事就是“睡一段时间再输出”。睡的时长和元素值成正比值越大睡得越久输出越晚。如果一切顺利最终输出的顺序就等于升序排序结果。它跑通的要件是线程调度和计时器足够稳定。实际执行时线程启动顺序、系统调度抖动、sleep 精度、重复值竞争等问题都会影响输出。但它依然能跑通尤其在小规模、无重复、非负整数的场景下你会看到输出基本有序。这类算法的价值不在生产而在展示“排序不一定非要比较大小也可以借助外部时间轴”。它提醒我们算法效率的讨论大多建立在同一个抽象模型里一旦引入并发和真实硬件很多假设会变。1.3 非比较排序用额外信息绕开比较下界的正规军第三类“不该存在”的排序其实不是笑话而是正经算法计数排序和基数排序。计算机科学里有一个著名结论基于比较的排序最坏情况下至少需要 n log n 次比较。比如快速排序、归并排序、堆排序都在这个框架里。但计数排序和基数排序不走“比较大小”这条路而是利用输入本身的数值范围、位数等信息把元素直接放到对应位置。于是它们可以把时间复杂度做到 O(n k) 或 O(n * d)看起来突破了 n log n。很多人误以为“线性排序不存在”其实是忽略了前提比较排序下界只对比较排序有效。非比较排序能更快是因为它额外假设了输入是有限范围内的整数、或者有固定长度的键。前提变了结论自然不同。这类算法看起来“不该存在”实际上在数据库、字符串排序、高性能计算里站得很稳。2. 真正让人误会的是“比较排序下界”2.1 下界是怎么来的要理解为什么博戈排序、睡眠排序会被当成“不该存在”首先得弄明白那个 n log n 下界是什么意思。对任意一个基于比较的排序算法比如快速排序、归并排序、插入排序它们能获得的唯一信息来自两两比较结果。一次比较只会产生两个结果大于或小于。于是整个算法执行过程可以画成一颗决策树每个节点是一次比较左右分支分别对应不同结果叶子节点是最终排列。n 个互不相同的元素可能的排列一共有 n! 种。要让一个比较排序算法能区分所有这些排列决策树至少需要 n! 个叶子节点。二叉树里如果要容纳 n! 个叶子树的深度至少是 log2(n!) 的数量级。用斯特林公式展开log2(n!) 约等于 n log2 n。这就是为什么基于比较的排序不可能稳定突破 O(n log n)。所以如果你在网上看到某个排序算法号称“比快速排序还快但只用了比较”第一反应应该是怀疑它是否真的只用了比较。2.2 反常识算法各自钻了什么空子博戈排序其实没有突破下界它只是把代价从“比较次数”转移到了“随机重排次数”。它不需要做很多比较因为排序这件事交给随机性去碰运气。最终结果虽然有序但付出了巨大的时间成本。睡眠排序更没有突破下界它把有序性建立在“时间流逝”这个外部过程上。每个元素对应的线程按照数值休眠等于把排序信息编码到系统计时器里。它绕开了抽象模型里的比较操作但没有得到任何效率优势反而引入了新的不稳定因素。计数排序和基数排序才是真正意义上的“突破”。它们不做元素间的关键字比较而是直接看数值本身是什么、在哪一位、应该放进哪个桶。这类算法能够成立靠的是输入具有可计算的结构。比如计数排序要求整数范围有限基数排序要求键可以拆成固定位数的数字。2.3 用一句话概括核心判断“不该存在的排序算法”通常不是逻辑错误而是“在一个不太合理的假设下也能把输出排好”。一个算法是否能存在不只看最终结果还要看它有没有满足可终止、可预测、资源可控这些实际要求。博戈排序和睡眠排序在严格定义下甚至不能算可靠的排序算法但它们作为实验现象非常有价值。3. 实测博戈排序小数组能跑大数组别试3.1 先准备一个最简环境实测博戈排序不需要 GPU不需要大数据集Python 3 就够了。关键依赖只有标准库 random。我用的是 Python 3.10Windows 和 Linux 上都能跑。先写一个最基础的判断函数再写博戈排序主体。不要一上来就开多线程或加各种可视化先跑通最小闭环。import random def is_sorted(arr): return all(arr[i] arr[i 1] for i in range(len(arr) - 1)) def bogosort(arr): data arr[:] attempts 0 while not is_sorted(data): random.shuffle(data) attempts 1 return data, attempts这段代码里有两个关键点。第一个是拷贝输入数组避免排序过程修改外部数据。第二个是 attempts 用来记录随机打乱了多少次方便判断运行成本。3.2 用最小样例验证正确性我先用 [3, 1, 2] 这个经典小数组跑了几轮。逻辑上三个互不相同的元素一共有 6 种排列其中只有 [1, 2, 3] 是有序的。也就是说每次随机打乱后命中的概率是 1 / 6期望打乱次数是 6 次。实测时不要只看一次运行我建议跑多轮取平均total 0 rounds 200 for _ in range(rounds): _, attempts bogosort([3, 1, 2]) total attempts print(total / rounds)理论平均是 6 次左右。因为随机性单次可能 2 次也可能 20 次但多跑 200 轮后平均值会往 6 附近靠。如果这个结果对不上优先检查 is_sorted 是否写错了大小关系或者 random.shuffle 是否污染了原数组。3.3 不同长度数组的期望尝试次数为了更直观地说明“不该存在为什么真的存在”可以看下面这张表。这里按不重复整数、随机打乱完全均匀来计算。数组长度 n期望随机打乱次数直观感受36一顿饭的功夫424还能接受5120开始变慢6720明显卡顿840320基本没法等103628800不要在生产环境跑这个表是理论值实际单次运行会在周围波动。但方向很清楚数组长度每增加 1期望尝试次数不是线性增加而是阶乘级增加。到 n8 时就已经不适合在普通命令行里反复试验了。如果你只想看博戈排序“确实能排完”我建议把数组长度控制在 5 以内。如果你想展示它为什么不能进生产就放到 10 并设置一个打乱次数上限观察它长时间不结束。3.4 报错和卡住时要查什么博戈排序最常见的现象不是报错而是“看起来像死循环”。这不是程序卡死而是它在等待一次概率极低的事件。遇到这种情况可以按这个顺序排查先确认数组长度是不是已经超过 8。再确认 is_sorted 的符号方向是升序还是降序。然后用固定种子跑。给 random.seed(0) 加一行方便复现。最后设置最大尝试次数比如超过 100000 次就退出避免一直耽误。不要把博戈排序跑太久。它的核心意义是让人理解“概率终止”和“实际终止”的区别不是真的替代归并排序。4. 实测睡眠排序能出结果但要靠系统调度配合4.1 一个能跑通的 Python 版本睡眠排序的实现思路比博戈排序更贴近真实操作系统。下面这个版本用线程池加锁先把每个元素交给一个线程线程按数值大小 sleep然后写入结果列表。import threading import time def sleep_sort(values): results [] lock threading.Lock() def worker(value): time.sleep((value 1) * 0.01) with lock: results.append(value) threads [threading.Thread(targetworker, args(v,)) for v in values] for t in threads: t.start() for t in threads: t.join() return results print(sleep_sort([3, 1, 2, 5, 4]))这里给每个值加 1是为了避免值为 0 时完全不等待。乘 0.01 的目的是把时间放大到毫秒级否则线程还没真正启动几微秒的 sleep 就结束了输出顺序会很混乱。放大之后系统调度的抖动相对变小排序更容易稳定。4.2 为什么它能排序又为什么不能保证睡眠排序能排序靠的是“谁的值小谁就先醒”。如果所有线程几乎同时被创建并且部分创建顺序不会带来太大偏差那么最终按休眠时间唤醒的顺序应该近似等于数值升序。但这里有一个很关键的坑系统不保证线程按你想的顺序执行。线程启动本身需要时间循环创建线程时前一个线程可能已经先进入休眠也可能还没开始。如果数值差距很小比如 [10, 11, 12]10 毫秒和 11 毫秒的差距太短结果可能因为调度抖动而乱掉。我实测时发现小规模、数值差异明显的列表比如 [3, 1, 8, 5, 20]多跑几次基本能保持升序。但一旦出现重复值比如 [2, 2, 3]两个 2 的唤醒顺序没有保证结果可能是 [2, 3, 2] 或 [2, 2, 3]不稳定。负数就需要整体平移否则 sleep(负数) 会直接报错。所以睡眠排序的正确用法是当成“并发与计时器”的演示不要当成排序算法。它无法保证排序稳定也无法控制最坏情况更不可能在生产环境替代系统自带排序。4.3 如果真要做实验建议加一个顺序条件为了验证睡眠排序的边界可以在多次运行中检查输出是否始终有序arr [3, 1, 8, 5, 20] bad 0 for _ in range(100): out sleep_sort(arr) if out ! sorted(arr): bad 1 print(ffail count: {bad})如果 fail count 为 0说明当前机器上这个数组规模下还比较稳定。如果 fail count 很高不要急着改排序逻辑先考虑是不是线程启动开销太慢、sleep 时间太短、重复值太多。通过调大 time.sleep 的系数通常能缓解但永远不能绝对消除。这个案例正好说明程序能跑通和你敢不敢把它用于生产是两回事。一个算法演示效果不错不代表它具备算法必须有的确定性保证。5. 计数排序和基数排序看起来不该存在却是正规军5.1 计数排序的落地代码对比前面两个“段子型”算法计数排序是真正能用于生产环境的线性排序。它适合非负整数输入且数值范围相对可控。def counting_sort(arr): if not arr: return [] min_val min(arr) max_val max(arr) span max_val - min_val 1 count [0] * span for value in arr: count[value - min_val] 1 output [] for i, c in enumerate(count): value min_val i output.extend([value] * c) return output这里用 min_val 做偏移是为了让负数也能排序。比如 [-3, 5, 1] 经过偏移后对应的桶下标是 0、8、4最终再映射回来。5.2 为什么它能突破 O(n log n)计数排序的耗时主要在两部分扫描原数组构建 count以及根据 count 输出结果。这两部分都和 n 相关同时 count 的长度取决于数值范围 k。所以时间复杂度是 O(n k)。当 k 远小于 n 时计数排序能做到近似线性明显快于快速排序。但它的代价是空间如果最小值是 0最大值是 1 亿你就得创建一个长度约 1 亿的 count 数组。这时候虽然时间复杂度好看内存却可能撑不住。低配机器尤其要留意不要看到“线性排序”就觉得一定适合你。如果你想实测计数排序建议先用小范围整数比如 [5, 3, 8, 1, 9, 2]然后逐步把范围拉大观察内存和耗时变化。不要一上来就跑 0 到 10 亿的数据多数普通开发机器会被内存卡死。5.3 基数排序是计数排序的“多轮版本”基数排序把整数或字符串拆成多位数每一轮按某一位进行排序。对十进制整数来说可以从个位开始按 0 到 9 分桶收集后处理十位再处理百位。每轮使用稳定排序最终整体有序。基数排序的时间复杂度是 O(d * (n k))其中 d 是数字位数k 是基数范围。对于位数少、数据量大的场景它也可能比常规比较排序更快。它同样需要额外的桶空间并且对数据格式有要求。这种“看着像作弊”的排序方式其实在很多底层库里都有应用。它没有违反任何数学规律只是跳出了比较排序的模型。如果有人再跟你说“排序必须 O(n log n)”你可以先反问一句是基于比较的排序吗输入是任意可比较元素还是有限范围内的小整数6. 如果自己动手验证建议按这个顺序排查6.1 先想清楚你的排序结论要证明什么做这类实验最容易犯的错是拿搞笑算法的跑通结果去否定常规算法复杂度结论。你得先确定自己想要验证哪个点是“博戈排序能不能在极短数组下碰巧跑通”还是“睡眠排序在特定机器上能输出有序”又或是“计数排序能处理负数”。目标不同代码设计和结果判断完全不同。不要把所有反常识算法混在一起也不要因为一个算法在小样本下成功就得出它能替代生产排序的结论。6.2 准备好输入先跑最小样例无论哪种排序第一轮测试都要用最小样例。博戈排序用 [3, 1, 2]睡眠排序用 [3, 1, 8, 5, 20]计数排序用带负数的 [5, -3, 8, 1]。最小样例出问题改起来最快。第二轮的测试条件是加入重复值。重复值对博戈排序能降低期望尝试次数对睡眠排序会暴露线程竞争对计数排序则要求 count 输出逻辑正确处理数量。这一轮最容易暴露算法边界。第三轮再测随机数据但要固定随机种子避免结果不可复现。比如random.seed(42)这样别人复现时能看到同样的现象。6.3 判断结果时看四个维度跑通一个排序不等于它好用。我建议从下面四个维度打分维度怎么看典型反例正确性多次运行输出是否始终等于 sorted(arr)睡眠排序偶发乱序确定性相同输入是否一定产生相同输出博戈排序随机次数不定时间单次耗时、批量吞吐是否可控博戈排序 n8 就很难等资源内存占用是否与输入规模匹配计数排序遇到超大范围这四个维度对应不同使用场景。学习实验可以只关注正确性生产选型必须同时考虑时间和资源。6.4 常见报错和排查链路如果睡眠排序报“ValueError: sleep length must be non-negative”说明输入里有负数。处理方式是整体平移到正数但要注意平移后的顺序关系保持不变。如果计数排序内存占用异常高先看 max 和 min 的差。差值越大count 数组越长。不要在不知道数据分布的情况下直接跑计数排序。如果博戈排序长时间没结果先看 n 是否过大再看随机种子是否固定最后看是不是不小心把数组传成了原引用导致外部数据被反复打乱。这类问题的排查顺序有通用套路先看输入再看环境最后看参数。输入是否包含负数、重复值、极大值环境依赖是不是 Python 3参数是不是用了不合理的数组长度或休眠系数。很多时候不是算法本身不“不存在”而是没满足它暗含的条件。6.5 哪些排序方案真正值得用普通开发里最值得用的排序其实是各语言内置排序。Python 的 TimSort、Java 的 DualPivotQuickSort、C 的 IntroSort都针对现实数据做过优化。它们有稳定性保证有内存边界也有异常处理。不要因为学了一个反常识算法就放弃内置方案。真正能把“线性排序”用在生产里的场景一般是数据已经被预处理成整数键、范围可控或者做大数据量字符串排序。比如搜索引擎倒排索引、数据库哈希分桶、外部排序的部分环节都会用到类似思想。但落地时还要考虑桶大小、磁盘读写、并行度和稳定性不能只看大 O 复杂度。最后留几个自己排查时会优先看的点反常识排序最迷人的地方是它让你重新审视“排序算法”的定义边界。博戈排序靠概率硬等睡眠排序靠系统时钟计数排序和基数排序靠输入结构。它们都能输出有序结果但可预测性和资源成本天差地别。如果只是写博客或学习我建议先把这三个样例分别跑通博戈排序跑 n5睡眠排序跑无重复小数组计数排序跑带负数的小整数数组。能跑通之后不要急着给结论还要再看一眼多次运行是否稳定、内存增长是否可接受、失败时日志能不能帮助定位。踩过几次之后你会发现很多问题不是算法能力不够而是前置假设没有满足。排序不是终点判断一个排序算法“为什么能跑通”比背下它的复杂度结论更有意思。