实现洗牌算法

时间:2021-06-01 03:39:40

洗牌算法

Fisher–Yates随机置乱算法也被称做高纳德置乱算法,通俗说就是生成一个有限集合的随机排列。
Fisher-Yates随机置乱算法是无偏的,所以每个排列都是等可能的,当前使用的Fisher-Yates随机置乱算法是相当有效的,需要的时间正比于要随机置乱的数,不需要额为的存储空间开销。

算法流程:

需要随机置乱的n个元素的数组array:
for( i =n-1;i>=1;i–)
(0 =< j <= i)
交换array[i]和array[j]
end

步骤:

各列含义:范围、当前数组随机交换的位置、剩余没有被选择的数、已经随机排列的数
实现洗牌算法
第一轮:从1到8中随机选择一个数,得到6,则交换当前数组中第8和第6个数
实现洗牌算法
第二轮:从1到7中随机选择一个数,得到2,则交换当前数组中第7和第2个数
实现洗牌算法
下一个随机数从1到6中摇出,刚好是6,这意味着只需把当前线性表中的第6个数留在原位置,接着进行下一步;以此类推,直到整个排列完成。
实现洗牌算法
截至目前,所有需要的置乱已经完成,所以最终的结果是:7 5 4 3 1 8 2 6

代码

        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;
}

参考文章:

1.参考Fisher–Yates shuffle wiki

2.由乱序播放说开了去-数组的打乱算法Fisher–Yates Shuffle