今天给大家分享一个，世界上最慢的排序算法，猴子排序（bogosort）。话不多说，先从伪代码说起：intbogo_sort(int&arr[],intn){while(false==is_sorted(arr[n])){random_shuffle(arr[n]);}return0;}它的原因叫做monkeysorting，源于一个典故：一只猴子随意敲击键盘，只要时间足够长，它一定能打出莎士比亚的诗篇。看完伪代码很容易理解，其核心思想是：（1）判断待排序的数组是否有序，如果有序则返回排序完成；(2)如果顺序乱了，就随机打乱数组；(3)重复(1);只要执行时间足够长，随机次数足够多，总能得到排序好的结果。它被称为世界上最慢的排序算法。那么问题来了，这个排序有什么用呢？能想到的就是大学里算法课上的时间复杂度推导练习，或者面试过程中的时间复杂度计算试题，或者伪装成13讲材料等等，好像都行不通。这个排序算法的时间复杂度是多少？我们简单分析一下。n个元素随机打乱，有n！种组合。排序成功的概率为p1=1/n!，排序失败的概率为p2=1-p1；两次排序成功的概率为p2*p1；画外音：第一次失败，第二次成功。3次排序成功的概率为p2^2*p1；画外音：前两次失败，第三次成功。...k次排序成功的概率是p2^(k-1)*p1画外音：前k-1次失败，第k次成功。...然后，平均排序成功次数的期望：E(X)=1次*一次成功的概率+2次*第二次成功的概率+3次*三次成功的概率+...+k次*k次成功的概率+...即：最后，根据大家在大学里学到的无限级数的数学知识，“很容易”得到，其时间复杂度为O(n*n!)，这是一个阶乘级算法。【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此阅读更多该作者好文
