实现洗牌算法

洗牌算法

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

算法流程：

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

步骤：

各列含义：范围、当前数组随机交换的位置、剩余没有被选择的数、已经随机排列的数

洗牌步骤1.jpeg

第一轮：从1到8中随机选择一个数，得到6，则交换当前数组中第8和第6个数

洗牌步骤2.jpeg
第二轮：从1到7中随机选择一个数，得到2，则交换当前数组中第7和第2个数
洗牌步骤3.jpeg

下一个随机数从1到6中摇出，刚好是6，这意味着只需把当前线性表中的第6个数留在原位置，接着进行下一步；以此类推，直到整个排列完成。

洗牌步骤4.jpeg
截至目前，所有需要的置乱已经完成，所以最终的结果是：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