13.6 洗牌

大多数纸牌游戏都需要洗牌，也就是让纸牌随机排列。在第10.5节，我们看到了怎样生成随机数，但怎样利用随机数实现洗牌功能却并非显然意见的。

一种可行的方案是，模拟人洗牌的方法，将牌分为两堆，然后通过在每个牌堆中轮流选择的方式实现原牌堆的重新组织。因为一般而言，人并不能做到完美地洗牌，而程序经过大约7次迭代之后，牌堆中纸牌的顺序已经相当随机了。但是计算机程序每次在做完美洗牌的时候有一个令人讨厌的属性——它并非真正随机的。实际上，经过8次完美洗牌之后，你会发现牌堆又回到原来的排列了。关于这一结论的讨论，请参考http://www.wiskit.com/marilyn/craig.html，或者以“perfect shuffle”为关键词通过搜索引擎查询相关信息。

还有一个更好的洗牌算法：遍历牌堆，每次选择一张纸牌，每次迭代时选择两张纸牌并交换其位置。

下面代码是该算法工作原理的大体轮廓。为了大概说出程序的意思，我混用了C++语句和自然语言句子，这有时也称为伪代码：

for (int i=0; i<cards.length(); i++) {
// 在i和cards.length()之间选择一个随机数
// 将第i张牌和随机选择的纸牌交换
}

伪代码的优点是能清晰地表达出你需要的函数。在这个例子中，我们需要像randomInt这样的函数用于在参数low和high之间选择一个随机数，也需要swapCards这样的函数用于交换两个索引值指定的位置的纸牌。

看一下第10.5节，你就应该能想出怎么编写randomInt函数了，尽管还是要小心处理生成的可能在区间之外的索引值。

你也可以自己想出swapCards函数。这些函数的剩余实现就作为作业留给读者。