洗牌算法(洗牌算法实现)
真?扑克牌洗牌算法实现
大家好，我是前端西瓜哥。
最近在试图做一个在线斗地主的游戏，为此需要实现一个洗牌算法，最后是给它实现了。一起来看看我是怎么将它实现的吧。
思路其实也不复杂，就两步：
我们先从顶层的算法出发，将上面的两个流程抽为两个子函数。
下面我们先看看 getCards 子算法。该算法的作用是返回一个完整扑克牌数组。
我们用字符串来表示一张牌。
对于牌的大小：
至于扑克牌花色，我们用 0 到 3 表示。也可以用它们英文的首字母来表示：S、H、C、D，都可以。
然后对它们做组合，就能表示一张特定的卡牌：
这里还缺两张比较特殊的大小王。因为他们花色的概念，所以要做特殊处理，随意找两个字符来表示。
大小王的英文为 Joker，可以考虑 J（Joker）或 K（王），但它们都被占用了。最后我就随意找两个连续字母 M 和 N 来表示了。你看这个两个字母是不是很像小丑的帽子，其实还挺像的。
这里返回的是完整的一副扑克牌数组。
我用了闭包，主要是为了做缓存，因为我们每次调用这个函数的返回值其实都是一样的，缓存一下能够用空间换时间，降低时间复杂度。
这里需要注意的是，我们需要返回缓存数组的拷贝，而不是直接返回缓存数组。如果你直接返回缓存数组，返回的其实是对缓存数组的引用，因为它们指向同一个内存对象。
如果你想返回两副牌，你可以在 return 前将数组自拷贝一下再放到数组尾部。
shuffle 方法是一个通用的洗牌算法，它会将传入的数组随机打乱。实现如下；
核心逻辑为：从后往前遍历，i 递减。从 0 ～ i 的索引范围内随机找一个元素，和 arr[i] 交换。
在 i 的动态变化过程中，i 右侧为打乱的元素区间，当 i 递减到 0，整个数组就洗完了。
这种实现是一种原地算法，空间复杂度为 O(1)，时间复杂度为 O(n)。
两个子函数实现完了，我们来看看执行 getShuffledCards 函数的输出结果：
西瓜哥我很满意。
这里我们再扩展一下，实现一下将乱序的牌排好序的算法。
假设我们在玩斗地主，我们把牌洗好了，先留下给地主的 3 张牌，然后每人发 17 张牌，但都是乱序的。
玩家问：“你 TMD 能不能给我把牌排好序？日内瓦！退钱！”
玩家貌似很愤怒（无感情），我们赶紧来实现上面将卡牌数组排序的 sortCards 方法。
首先明确平时我们平时打牌时的排序规则。
实现思路就是用 JS 自带的 Math.sort() 方法进行排序，难点是怎么对比两个字符串。
我们 无法用字典序 ，因为 A 比 K 大，大小王 M 和 N 又比较特殊。我使用的方案就是 计算出它们的等价的数值，通过它们来比较 。实现如下：
我们把牌大小作为更高的位（ parseInt(num) * 10 ）。
对于花色，则要采取负收益的做法 ，因为我是用 1 来表示黑桃，3 来表示方块，排序要求从大到小，且黑桃要最左，所以需要对它取反，来保证黑桃的值要比方块的要大。
有些非数字字符，我们需要依照它们的大小，给它们提供对应的数字。然后是大小王，需要最特殊处理，直接返回非常大的比其他牌要大的等价数。
真正地给扑克牌洗牌，然后将它们发给玩家，再帮他们拍好牌，你们学会了吗？
我们看到，实现扑克牌洗牌的算法其实并没有想象中的那么简单，当然也不难。因为我们可以使用工程化的思维，将一个大问题不断地拆分，拆分成合适大小的子问题。一个个将子问题解决，大问题自然也就被解决了。
Knuth 洗牌算法
思考：洗牌的结果是所有元素的一个排列。一副牌如果有 n 个元素，最终排列的可能性一共有 n! 个。 公平的洗牌算法，应该能等概率地给出这 n! 个结果中的任意一个 。 如思考虑到这一点，我们就能设计出一个简单的暴力算法了：对于 n 个元素，生成所有的 n! 个排列，然后，随机抽一个。 这个算法绝对是公平的。但问题是，复杂度太高。复杂度是多少呢？O(n!)。因为，n 个元素一共有 n! 种排列，我们求出所有 n! 种排列，至少需要 n! 的时间。所以，这个算法确实是公平的，但是，时间不可容忍。
我们再换一个角度思考“公平”这个话题。其实，我们也可以认为，公平是指， 对于生成的排列，每一个元素都能独立等概率地出现在每一个位置。 或者反过来， 每一个位置都能独立等概率地放置每个元素。
基于这个定义，我们就可以给出一个简单的算法了。说这个算法简单，是因为他的逻辑太容易了，就一个循环：
这么简单的一个算法，可以保证上面我所说的，对于生成的排列，每一个元素都能独立等概率的出现在每一个位置。或者反过来，每一个位置都能独立等概率的放置每个元素。 大家可以先简单的理解一下这个循环在做什么。其实非常简单，i 从后向前，每次随机一个 [0...i] 之间的下标，然后将 arr[i] 和这个随机的下标元素，也就是 arr[rand(0， i)] 交换位置。 大家注意，由于每次是随机一个 [0...i] 之间的下标，所以，在每一轮，是可以自己和自己交换的。 这个算法就是大名鼎鼎的 Knuth-Shuffle，即 Knuth 洗牌算法。
几种扑克牌洗牌算法
洗牌的
几种话先设定好洗牌方式几种比方对分上下交l以及交织洗牌然扑克牌后用随机数生成函数确定单步洗牌作牌的数量多反复几遍即可。
的一个合理的定义就是算法
一副扑克张牌有种陈列方式。
这样做的好处：
给出的洗牌算算法应该可以等概率地生成这种结果中的一种