洗牌算法
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;
}