Bogo 排序(Bogo Sort)算法又称为猴子排序(Monkey Sort)算法,顾名思义,是非常愚蠢的排序算法,就像是请猴子帮忙排序一样。

Bogo 排序法(Bogo Sort)

Bogo 排序法的概念

Bogo 排序法十分简单,一开始先检查串行是否已经排序完成,如果没有的话就不断地随机弄乱它的元素顺序,直到刚好完成排序为止。

Bogo 排序法的过程

假设现在有个数组数据,内容如下:

索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

要如何将它递增排列呢?

由于它还不是一个已递增排列好的数组,所以要将它的元素顺序随机弄乱。弄乱之后的结果可能如下:

索引    0   1   2   3   4   5   6   7   8   9
数值   79  38  81   2  30  47   9  69  32  61

因为还没排序完成,所以继续随机弄乱。弄乱之后的结果可能如下:

索引    0   1   2   3   4   5   6   7   8   9
数值   38  81   2  30  79  61  47   9  32  69

此时也还是没有排序完成,所以继续随机弄乱。重复进行上述动作之后,总会有一次可以恰好弄乱成已排序好的串行。

索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81

Bogo 排序法的程序实作

Bogo 排序法的复杂度

以 #{{n}}# 来表示要排序的数据笔数。

项目 值 备注
最差时间复杂度 #{{O(\infty)}}# 随机乱排总是不巧地都没猜中。
最佳时间复杂度 #{{O(n)}}# 排序已经正向排序过的串行。
平均时间复杂度 #{{O({n \times n!})}}# 随机乱排猜中的概率为 #{{1/n!}}#,平均要乱排 #{{n!}}# 次,再乘上每次乱排前检查是否已排序的时间复杂度。
最差空间复杂度 #{{O(1)}}#
是否稳定 否