洗牌算法Fisher_Yates原理

[TOC]

算法

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

简单的原理如下图所示:

原理

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

做法就是

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

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

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

以此类推。

实际应用

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

func shuffle(indexes []int)  {
	for i:=len(indexes);i>0;i-- {
		lastIdx := i-1;
		idx := rand.Intn(i)
		indexes[lastIdx], indexes[idx] = indexes[idx], indexes[lastIdx]
	}
}

在Go的标准库中已经为我们内置了该算法:

func shuffle(n int) []int {
    b := rand.Perm(n)
    return b
}

参考自 [柴树衫的Go语言高级编程](