0%

洗牌算法

发表于 分类于

文章字数：170,阅读全文大约需要1分钟

介绍

洗牌算法, Fisher–Yates随机置乱算法也被称做高纳德置乱算法, 作用是生成一个有限集合的随机排列，即打乱集合，并使每个排列的可能都相等。

步骤

  1. 从n个数组中选取低（1到n-1）中随机选择一个，并和n替换
  2. 再从（1到n-2）中随机选择一个，和n-2个替换
    …
    直到全部替换完成

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void main(String[] args) {
    int[] arr = new int[10];
    int i;

    // 初始的有序数组
    for (i = 0; i < 10; i++) {
        arr[i] = i + 1;
    }

    // 费雪耶兹置乱算法
    // 每次生成的随机交换位置:
    for (i = arr.length - 1; i > 0; i--) {
        // 随机数生成器，范围[0, i]
        int rand = (new Random()).nextInt(i + 1);

        int temp = arr[i];
        arr[i] = arr[rand];
        arr[rand] = temp;
    }
}