java实现猴子排序(BogoSort)

爱丁顿在1929年阐述过一个“无限猴子理论”，就是说“如果许多猴子任意敲打打字机键，最终可能会写出大英博物馆所有的书”。

书可以看作是字母的组合，大英博物馆所有的书作为有限集是包含在字母的组合这个无限集之中的。有限集在无限集中出现的概率不为零，这也是你说“概率肯定不为零”的原因。问题就在于“字母的组合”和“许多猴子任意敲打打字机键”两个无限集是否等价。

猴子排序引用了无限猴子定理，算法通过不停的随机排列数组，直到数组有序。

数组实现：

package com.allen.testDemo;

import java.util.Arrays;
import java.util.Date;
import java.util.Random;

//猴子排序算法
public class BogoSort {

    public static void main(String[] args) {
        Integer[] arr = {45, 21, 67, 12, 57, 23, 68, 74, 90, 47};
        Integer num = 0;
        Date startDate = new Date();
        System.out.println(Arrays.toString(arr));
        while(!BogoSort.judgeSort(arr)){
            num++;
            BogoSort.upset(arr);
        }
        System.out.println("共执行了" + num + "次，消耗时间" + (new Date().getTime() - startDate.getTime()) + "ms");
        System.out.println(Arrays.toString(arr));
    }

    //随机打乱数组
    public static Integer[] upset(Integer[] arr){
        Random rand = new Random();
        Integer tmp = null;
        for(int i = 0; i < arr.length; i++){
            //遍历到位置右侧未排序数组随机一个下标的值与左侧交换
            Integer randNum = rand.nextInt(arr.length - i) + i;
            tmp = arr[randNum];
            arr[randNum] = arr[i];
            arr[i] = tmp;
        }
        System.out.println(Arrays.toString(arr));
        return arr;
    }

    //判断数组是否正序排列
    public static boolean judgeSort(Integer[] arr){
        for(int i = 0; i < arr.length - 1; i++){
            if(arr[i] >= arr[i + 1]){
                return false;
            }
        }
        return true;
    }
}

list实现：

package com.allen.testDemo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.List;

public class MonkeySort {
    public static void main(String[] args) {

        List<Integer> list = new ArrayList<>();
        list.add(45);
        list.add(21);
        list.add(67);
        list.add(12);
        list.add(23);
        list.add(68);
        list.add(74);
        list.add(90);
        list.add(47);
        System.out.println(list.toString());

        Integer num = 0;
        Date startDate = new Date();
        while(!MonkeySort.judgeSort(list)){
            num++;
            Collections.shuffle(list);
            System.out.println(list.toString());
        }
        System.out.println("共执行了" + num + "次，消耗时间" + (new Date().getTime() - startDate.getTime()) + "ms");
        System.out.println(list.toString());
    }

    public static boolean judgeSort(List<Integer> list){
        for(int i = 0; i < list.size() - 1; i++){
            if(list.get(i) >= list.get(i + 1)){
                return false;
            }
        }
        return true;
    }
}

这个算法大家拿来娱乐一下就好，毕竟这个效率真的是“太高了”。