猴子排序

前言

首先得介绍一下无限猴子定理，这个定理是来自埃米尔·博雷尔一本1909年出版谈概率的书籍，当中介绍了“打字的猴子”的概念。

猴子定理定义如下：

一般关于此定理的叙述为：有无限只猴子用无限的时间会产生特定的文章。
其他取代的叙述，可能是用大英图书馆或美国国会图书馆取代法国国家图书馆；另一个常见的版本是英语使用者常用的，就是猴子会打出莎士比亚的著作。欧洲大陆还有一种说法版是猴子打出大英百科全书。在《从一到无穷大》中，作者则引用了哈姆雷特的例子。

详细推导过程参考百度百科
那么根据猴子定理，如果我们不断随机打乱一个可排序的数组，在无限长的时间里，这个数组肯定会变成有序数组。

代码

package org.example;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class MonkeySort {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> nums = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            nums.add(scanner.nextInt());
        }
        //排序
        monkeySort(nums);
        //输出有序数组
        for (Integer num : nums) {
            System.out.println(num);
        }
    }

    private static void monkeySort(ArrayList<Integer> nums) {
        while (!checkSort(nums)) {
            upset3(nums);
        }
    }

    /*
     * 随机打乱传入的集合
     * 洗牌算法
     */

    /**暴力
     * 每次将原集合中随机一个元素，放到新集合中，然后删除原集合中这个元素。
     */
    private static void upset1(ArrayList<Integer> nums) {
        ArrayList<Integer> arr = (ArrayList<Integer>) nums.clone();
        int length = arr.size();
        nums.clear();
        for (int i = 0; i < length; i++) {
            int j = (int) (Math.random() * arr.size());
            nums.add(arr.get(j));
            arr.remove(j);
        }
    }

    /**Fisher-Yates 洗牌算法
     * 是对暴力算法的优化
     * 我们可以不删除那个元素，而是将它和需打乱集合中最后一个元素交换位置
     * 第一次将交换完，将前n-1个作为新地需要打乱的集合，最后1个元素作为乱序后的结果
     * 第二次将交换完，将前n-2个作为新地需要打乱的集合，倒数两个元素作为乱序后的结果
     * ...
     * 直至集合全为乱序。
     */
    private static void upset2(ArrayList<Integer> nums) {
        for (int i = nums.size() - 1; i >= 0; i--) {
            int j = (int) (Math.random() * (i));
            nums.add(j, nums.get(i));
            nums.remove(i + 1);
            nums.add(nums.get(j + 1));
            nums.remove(j + 1);
        }
    }

    //使用shuffle()方法
    private static void upset3(ArrayList<Integer> nums) {
        Collections.shuffle(nums);
    }

    /**
     * 判断集合是否有序
     */
    private static boolean checkSort(ArrayList<Integer> nums) {
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums.get(i) > nums.get(i + 1)) return false;
        }
        return true;
    }
}

总结

猴子排序，看运气的算法。