长见识了！世界上最慢的排序算法！

原创 KG沈剑架构师之路

前段时间，分享了《算法导论》中的一些排序算法。

最美排序：

《世界上最美的排序算法！》

时间复杂度为O(n)的三种排序：

《这个排序酷，O(n)》

《这个排序靓，O(n)》

《这个排序跩，O(n)》

今天，和大家分享一个，世界上最慢的排序算法，猴子排序（bogo sort）。

话不多说，先上伪代码：

int bogo_sort(int& arr[], int n){

while(false== is_sorted(arr[n])){

random_shuffle(arr[n]);

}

return 0;

}

之所以叫猴子排序，源自典故：一只猴子随机敲击键盘，只要时间足够久，一定能敲出莎士比亚的诗。

看了伪代码，很容易理解其核心思路是：

（1）判断待排序的数组是否有序，有序则返回排序完毕；

（2）无序，则随机打乱数组；

（3）重复（1）；

只要执行的时间足够长，随机的次数足够久，总能够得到排序后的结果，它号称是世界上最慢的排序算法。

那么问题来了，这个排序有什么用呢？

我能够想到的，就是大学里作为算法课的时间复杂度推导习题，或者面试过程中时间复杂度计算考题了，又或者装13的谈资了，其他好像没有什么用。

那这个排序算法的时间复杂度是多少呢？

简单来分析一下。

n个元素随机打乱，有n!种组合。

一次排序成功的概率是p1 = 1/n!，一次排序失败的概率是p2 = 1-p1；

两次排序成功的概率是p2*p1；

画外音：第1次失败，第2次成功。

三次排序成功的概率是p2^2*p1；

画外音：前2次失败，第3次成功。

…

k次排序成功的概率是p2^(k-1)*p1

画外音：前k-1次失败，第k次成功。

…

于是，平均排序成功次数的期望：

E(X) =

1次 * 一次成功的概率

2次 * 二次成功的概率

3次 * 三次成功的概率

…

k次 * k次成功的概率

…

即：

最后，根据大家大学里学的无穷级数的数学知识，“很容易”得到，其时间复杂度是O(n*n!)，这是一个阶乘级别的算法。

架构师之路-分享可落地的技术文章

答应我，装13可以，不要用这个考题去为难候选人，好么？谢谢大家！

调研：

你还见过更奇葩的排序算法吗？

阅读原文

继续滑动看下一个