洗牌算法Fisher_Yates原理

1.算法

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

简单的原理如下图所示:

洗牌算法Fisher_Yates原理

2.原理

总结下,洗牌算法Fisher_Yates的原理就是把从1到n的顺序候选集随机打乱,

做法就是

第1次从1-n的候选集合随机选个数,拿出此数,并把它从候选集合剔除(候选集合n-1)。

第2次从1-n-1的候选集合随机选个数,拿出此数,并把它从候选集合剔除(候选集合n-2)。

第2次从1-n-2的候选集合随机选个数,拿出此数,并把它从候选集合剔除(候选集合n-3)。

以此类推。

3.理论保证

个人理解,如有错误请大家纠正:

a,b,c

第1次取出a的概率 1/3

第2次取出a的概率 2/3(取出b概率+取出c概率) * 1/2 (剩下2个中取出a的概率) = 1/3

第3次取出a的概率 2/3 * 1/2 * 1/1 = 1/3

以此类推可以算出b和c,得到如下表格:

字符/出现位置概率 1 2 3
a 1/3 1/3 1/3
b   1/3 1/3 1/3
c 1/3 1/3 1/3

  

4.实际应用

有个时间复杂度是O(n)的实现,如下:

void ShuffleArray_Fisher_Yates(char* arr, int len)
{
int i = len, j;
char temp; if ( i == ) return;
while ( --i ) {
j = rand() % (i+);
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
上一篇:Uart串口


下一篇:[google面试CTCI] 1-7.将矩阵中特定行、列置0