奇葩算法系列——猴子排序

首先我们介绍无限猴子定理

无限猴子定理最早是由埃米尔·博雷尔在1909年出版的一本谈概率的书籍中提到的，此书中介绍了“打字的猴子”的概念。无限猴子定理是概率论中的柯尔莫哥洛夫的零一律的其中一个命题的例子。大概意思是，如果让一只猴子在打字机上随机地进行按键，如果一直不停的这样按下去，只要时间达到无穷时，这只猴子就几乎必然可以打出任何给定的文字，甚至是莎士比亚的全套著作也可以打出来。

根据猴子定理，如果我们不断用随机的数字组成一个数列，那么在无限长的时间里，这个数列在某次肯定会变成有序。

关于猴子定理的实现，网上也有很多实例，但是大部分都是和上述一样，生成随机数字的数列，然后验证是否有序，我觉得这样实际上并不一种排序，我理解的排序就是对现有的数列进行排序，因此实现时做了一定的改造

给出一个固定的乱序数列
随机从这个乱序数列中取出数字放在第一位，然后重复取数字放在第二位，第三位....
验证新的数列是否有序

这样做能更好的切合排序的概念

private static int [] array = new int[10];
private static int [] result = new int[10];

array用于存储固定的乱序数列，result用于存储每次生成的新数列

private static boolean checkOrder (int array[]){for (int i = 1; i < 10; i++){if (array[i] <= array[i-1]){return false;}}return true;}

chekorder检查数组是否有序

private static void sort(int num, Random random){Set<Integer> numberSet = new HashSet<Integer>();System.out.println("第" + num + "次");for (int i = 0; i < 10; i++){int index = random.nextInt(10);while (numberSet.contains(index)){index = random.nextInt(10);}numberSet.add(index);int number = array[index];result[i] = number;System.out.print(" " + result[i]);}System.out.println();}

sort是随机取数进行排序，这里为了能每次都取出不同数字，用Set做了已经使用过的验证，这样主要是为了能更快的得到结果

最后运行程序

可以看到猴子排序在这次排序共生成41781次数列，耗时2S就生成了一组有序的数列，这样看是不是猴子排序比睡眠排序的效率要高很多。

全部代码：

public class MonkeySort {private static int [] array = new int[10];private static int [] result = new int[10];static{generate();}/*** 检查数组是否有序* @return*/private static boolean checkOrder (int array[]){for (int i = 1; i < 10; i++){if (array[i] <= array[i-1]){return false;}}return true;}private static void sort(int num, Random random){Set<Integer> numberSet = new HashSet<Integer>();System.out.println("第" + num + "次");for (int i = 0; i < 10; i++){int index = random.nextInt(10);while (numberSet.contains(index)){index = random.nextInt(10);}numberSet.add(index);int number = array[index];result[i] = number;System.out.print(" " + result[i]);}System.out.println();}private static void generate(){array[0]=8;array[1]=5;array[2]=3;array[3]=6;array[4]=4;array[5]=9;array[6]=7;array[7]=10;array[8]=1;array[9]=2;}public static void main(String[] args){Random random = new Random();int num = 0;long startTime = System.currentTimeMillis();while(true){sort(num++,random);boolean isOrder = checkOrder(result);if (isOrder){break;}}long endTime = System.currentTimeMillis();System.out.println("排序完成，耗时：" + (endTime-startTime)/1000 + " S");}}

微信公众号：二虎程序