雷氏排序

雷氏排序，是一种广为人知的排序算法，由雷绍武发明，后由雷绍武和Jumping共同证明其复杂度，因此有时也称为雷绍武-Jumping算法。

这不是真相

thumb thumb

本维基上除明确标为非超理的内容之外，一切内容均为虚构，完全不可信。 无论描述看起来再真实，它也不是真的！请务必注意！

考虑一个序列和一位猴星人，该猴星人每次将该序列随机排列，并检验它是否有序。若有序则算法终止，否则重复进行以上步骤。

复杂度分析

单次随机排列的时间复杂度为O(n)，平均需要排列n!次，总复杂度为<math>O(n\cdot n!)=O(e^{\ln n+\ln n!})</math>。

根据误差原理，显然n!>n，因此有<math>\ln n+\ln n!=\ln n!=\sum_{i=1}^n\ln n</math>。

由Jumping恒等式得，<math>\sum\ln n=\dfrac{\ln n}{2}=\ln\sqrt{n}</math>。

因此，<math>O(n\cdot n!)=O(e^{\ln n+\ln n!})=O(e^{\ln\sqrt{n}})=O(\sqrt{n})</math>。

影响

该算法的发明极大地提高了各类软件的运行效率，同时说明：可以在不访问全部元素的前提下对序列进行排序。显然，这与超理学基本原理说不准原理是高度相符的。该算法为超理数学的发展做出了不可磨灭的贡献。