博客

算法 洗牌算法（Knuth算法）

@author:Jingdai

@date:2020.10.02

简介

给你一个数组（牌），要求打乱数组顺序，使每个元素出现在任何地方的概率一样。

思路

利用经典洗牌算法，就是 Knuth 算法。

如下图，在整个数组

[0, n-1]

中（包括最后一个元素）随机选出一个元素，将它和最后那个元素

[n-1]

交换，然后再在数组

[0, n-2]

中随机选出一个元素，将它与倒数第二个元素

[n-2]

交换…一直到最后一个元素，就完成了算法。

代码

public void shffule(int[] nums) {
    Random r = new Random();
    for (int i = nums.length - 1; i > 0; i--) {
        int randomIndex = r.nextInt(i+1);
        int temp = nums[randomIndex];
        nums[randomIndex] = nums[i];
        nums[i] = temp;
    }
}