一点一点前进...

0%

洗牌算法

发表于 分类于 ， Disqus：

给你54张牌，写一个洗牌算法，要求等概率的出现54!种不同的排列。

这个一个众所周知的面试题，也是一个众所周知的算法。

算法的思想很简单，就是遍历每一张，让后面（包括当前这张）的牌等概率的出现在这个位置上。比如index从0开始，那么每张牌都等概率的出现在0这个位置上，index等于1时，0位置上的那一张，其余的牌等概率出现在位置1上，以此类推。这样，排列总数就是54!，且每一种是等概率出现的。
下面是代码： 

1
2
3
4
5
6
7
8
9
10
11
public static void Shuffle(int[] cards)
{
    Random rand = new Random(DateTime.Now.Ticks);
    for (int i = 0; i < cards.Length; i++)
    {
        int k = rand.Next(i, cards.Length);
        int temp = cards[k];
        cards[k] = cards[i];
        cards[i] = temp;
    }
}

我曾经看过有人在生成随机数的时候，生成(0, length)范围内的随机数，这是不对的。这样子，每个位置上的数字还会从前面已经排好的数字里面取，这样排列总数是54^54，是伪洗牌算法，是错误的。