经典和量子的"冒牌排序"

计算机科学中有一个近乎玩笑的排序算法称为"冒牌排序" (bogosort), 又叫作"猴子排序" (Monkey Sort). 这个算法被称为"典型的糟糕算法". 实现它的步骤是:

第一步: 检查数组是否有序;
如果有序返回结果;
如果乱序:
第二步: 随机排列该数组, 返回第一步.

"冒牌排序"等价于把一堆扑克随机洗牌, 然后检视是否有序. 如果无序, 则继续重复下去. 可想而知, 这个算法的效率是极其低下的. 它的平均时间复杂度为$O(n \cdot n!)$. 相对比之下, 常用的快速排序平均只需要 $O(n \cdot \log n)$ 次操作.

有个调侃量子计算机的笑话, 说利用冒牌排序可以在 $O(n)$ 次操作中完成排序. 原理如下:

第一步: 利用量子计算机将数组随机排列. 根据量子力学的多世界诠释, 每一种可能的排列都会出现在某一个宇宙中.
第二步: 检查每一个宇宙中的数组是否有序. 在每个宇宙中, 这需要 $n-1$ 次操作.
第三步: 摧毁仍然乱序的宇宙. 唯一的幸存者只看到过 $n-1$ 次操作.

算法第三步的实现交给读者作为练习.

当然实际上这个算法的第三步是不可能实现的 (假定多世界诠释是对的, 并且这个数组是量子数组). 因为首先每次测量将会使观察者选择某一个具体的世界, 量子数组亦将选择某一种排列方式. 观察者当然不可能再跳出这个宇宙 (即使摧毁这个宇宙, 因为观察者是宇宙的一部分), 更不用说摧毁其他宇宙.