洗牌算法

假定给一个0 - 9 的数组。使用洗牌算法来保证每个数字出现在每个位置的概率都是1/10

洗牌算法:遍历数组,第n个与后边的数字(包含自己)的某一个进行位置互换。

数组初始状态:0,1,2,3,4,5,6,7,8,9
第一次交换用0和1,2,3,4,5,6,7,8,9以及0 自己交换,所以每个数字出现在第一位的概率都是1/10.
那么此时的数组状态已经 (0,1,2,3,4,5,6,7,8,9),(0,1),(0,2),......(0,9) 此时已经保证每个数字出现在第一位的概率都是1/10
第二次交换 交换后第二位的数是 1 的概率为9/10(第二位是1的概率,1-1/10) * 1/9
第二次交换 交换后第二位的数是 2 的概率为9/10(第三位是2的概率,1-1/10) * 1/9
。。。
依次类推,第二次交换后。已经保证每个数字出现在第二位的概率都是1/10。



遍历结束之后就保证了每个数字出现在每个位置的概率都是1/10。

原文地址:https://www.cnblogs.com/dg-blog/p/13158994.html