Bogo排序

十大经典排序算法

大家应该听过无限猴子定理（Infinite monkey theorem），让一只猴子在打字机上随机地按键，当按键时间达到无穷时，必然能够打出任何给定的文字，比如莎士比亚的全套著作。Bogo排序（bogo-sort）的基本思想和无限猴子定理类似，就是把数组随机打乱，然后检查数组是否有序，如果不是有序在重新打乱，然后在检查是否有序……，直到有序为止。Bogo排序靠的是运气，他是一种非常低效率的排序算法。

public void bogoSort(int[] nums) {
    Random random = new Random();
    while (!checkOrder(nums)) // 检查是否有序，如果无序就继续打乱。
        shuffle(random, nums);
}

// 打乱数组
private void shuffle(Random random, int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int index = random.nextInt(i + 1);
        int tmp = nums[i];
        nums[i] = nums[index];
        nums[index] = tmp;
    }
}

// 检查是否有序
private boolean checkOrder(int[] nums) {
    for (int i = 1; i < nums.length; i++)
        if (nums[i - 1] > nums[i])
            return false;
    return true;
}

相关链接