今天,和大家分享一个,世界上最慢的排序算法,猴子排序(bogo sort)。int bogo_sort(int& arr[], int n){
while(false== is_sorted(arr[n])){
random_shuffle(arr[n]);
}
return 0;
}
之所以叫猴子排序,源自典故:一只猴子随机敲击键盘,只要时间足够久,一定能敲出莎士比亚的诗。(1)判断待排序的数组是否有序,有序则返回排序完毕;只要执行的时间足够长,随机的次数足够久,总能够得到排序后的结果,它号称是世界上最慢的排序算法。我能够想到的,就是大学里作为算法课的时间复杂度推导习题,或者面试过程中时间复杂度计算考题了,又或者装13的谈资了,其他好像没有什么用。一次排序成功的概率是p1 = 1/n!,一次排序失败的概率是p2 = 1-p1;![]()
最后,根据大家大学里学的无穷级数的数学知识,“很容易”得到,其时间复杂度是O(n*n!),这是一个阶乘级别的算法。
答应我,装13可以,不要用这个考题去为难候选人,好么?谢谢大家!