猴子排序

猴子排序（Bogo Sort）

听说过“猴子和打字机”的理论吗？

无限猴子定理（Infinite Monkey Theorem）与薛定谔的猫、电车实验等并列为常见的思想实验，所谓思想实验即用想象力去进行，而在现实中基本无法去实现的实验。

无限猴子定理讲的是如果让一只猴子在打字机上胡乱打字，只要有无限的时间，总有一天可以恰好打出莎士比亚的著作。如果让无限只猴子在无限的空间、无限的时间里不停地敲打打字机，总有一天可以完整打出一本《哈姆雷特》，甚至是可以打出所有可能的文章。

这个看似不可能的事情，却可以用现有数学原理被推导出来。但在现实中往往被认为是无法实现的，因为人们认为“无限”这个条件通常无法被满足。在特定的概率估算模型下，即使可观测宇宙中充满了猴子一直不停地打字，能够在有限时间内打出一部《哈姆雷特》的概率仍可小于$1 \over 10^{183900}$。

无限猴子定理同样可以用在排序中。如果给数组随机排列顺序，每一次排列之后验证数组是否有序，在独立均匀随机排列的前提下，重复次数趋于无穷时，以概率1最终会得到有序数组，但不存在保证成功的有限次数。可是要想真的随机出有序数列，恐怕要等到猴年马月了。