雷氏排序

这不是真相

thumb

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

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

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

复杂度分析

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

根据误差原理，显然n!>n，因此有$ \ln n+\ln n!=\ln n!=\sum _{i=1}^{n}\ln n $。

由Jumping恒等式得，$ \sum \ln n={\dfrac {\ln n}{2}}=\ln {\sqrt {n}} $。

因此，$ O(n\cdot n!)=O(e^{\ln n+\ln n!})=O(e^{\ln {\sqrt {n}}})=O({\sqrt {n}}) $。

影响

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