这里是修真院前端小课堂，每篇分享文从
【背景介绍】【知识剖析】【常见问题】【解决方案】【编码实战】【扩展思考】【更多讨论】【参考文献】
八个方面深度解析前端知识/技能，本篇分享的是：
【洗牌算法具体指的是什么？ 】
1）背景介绍：
为了让游戏更加公平，我们希望洗牌时得到一个随机的排序，一个简单有效的办法就是把牌随
机选一叠放
另外一边做一个新的牌堆，并且重复这一步。只要从剩余牌堆中选出来的牌的概率是相等的，
就会得到公平的牌堆。
相似的，对于数组【0,n】，如何对它随机排列元素呢
（2）知识剖析：
JavaScript 开发中有时会遇到要将一个数组随机排序（shuffle）的需求，一个常见的写法是这样：
function shuffle(arr) {
arr.sort(function () {
return Math.random() - 0.5;
});
}
或者使用更简洁的 ES6 的写法（箭头函数创建更简短的函数和不引入this）：
function shuffle(arr) {
arr.sort(() => Math.random() - 0.5);
}
（3）常见问题：
但是这种写法有问题，并不能实现真正的随机
这样排序的问题
看下面的代码，我们生成一个长度为 10 的数组['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
'j']，使用上面的方法将数组乱序，执行多次后，会发现每个元素仍然有很大机率在它原来的位置附近出现。
let n = 10000;
let count = (new Array(10)).fill(0);
for (let i = 0; i < n; i ++) {
let arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'];
arr.sort(() => Math.random() - 0.5);
count[arr.indexOf('a')]++;
}
console.log(count);
如果排序真的是随机的，那么每个元素在每个位置出现的概率都应该一样，
但是这种排序各个位置的字母会在原位置的左右徘徊。
因此，我们可以认为，使用形如arr.sort(() => Math.random() - 0.5)这样的方法得到的并不是真正的随机排序。
浏览器打印台：(10) [2892, 2939, 1968, 1040, 582, 288, 161, 66, 44, 20]
国外有人写了一个Shuffle算法可视化的页面，
在上面可以更直观地看到使用arr.sort(() => Math.random() - 0.5)的确是很不随机的。
（4）解决方案：
Fisher–Yates shuffle算法
这个算法由 Ronald Fisher 和 Frank Yates 于 1938 年提出，然后在 1964 年由 Richard Durstenfeld 改编为适用于电脑编程的版本。
（5）编码实战：
ES6实现方法：
function shuffle(arr) {
let i = arr.length;
while (i) {
let j = Math.floor(Math.random() * i--);
[arr[j], arr[i]] = [arr[i], arr[j]];
}
}
ES5实现：
function shuffle(arr) {
var i = arr.length, t, j;
while (i) {
j = Math.floor(Math.random() * i--);
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
比较清晰的一种写法
Array.prototype.shuffle = function () {
var input = this;
for (var i = input.length - 1; i >= 0; i--) {
var randomIndex = Math.floor(Math.random() * (i + 1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
return input;
}
var tempArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] ;
tempArray.shuffle(); // and the result is... alert(tempArray);
prototype 属性是在函数作为构造器使用的时候，作为其构造对象的原型
this 引用的就是调用该 shuffle 的数组：
for循环遍历数组，顺序是从后往前，从input.length-1位置开始，直到第一个元素
var randomIndex = Math.floor(Math.random() * (i + 1));存储一个随机数，用作数组的索引，来提取一个随机元素，最大值是i的值
var itemAtIndex = input[randomIndex];用新变量保存该随机元素值，比如随机生产的索引2，那么该随机值就是3
最后两行是把选中的元素和随机的元素交换一下
（6）拓展思考：
除了洗牌算法，类似的，还有哪些对数组的排序方式？
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，
也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。
（7）参考文献：
参考一：
（8）更多讨论：
提问1：
除了Fisher–Yates shuffle算法还有哪些随机算法？
回答：比如上面提到的arr.sort(() => Math.random() - 0.5)算法就是一个常用的方法。尽管得到的并不是完全的随机
提问2：洗牌算法的实际运用？
回答：比如听歌软件的随便听听功能
提问3：fisher算法比sort算法究竟好在哪里
回答：
再拿抽牌举例，因为fisher利用了抽卡本身的顺序，保证到了每一张原本序列中的卡，而sort方法抽取存在出现重复位置的可能性，就等于浪费了一次排序的机会，换句话说，其等效抽卡次数因为出现了过去相同的洗法，有效洗牌次数下降，样本空间缩小，无法充满整个n！空间，所以有效性会下降。而Fisher–Yates算法在原理上保证了不会出现浪费次数，重复选择的情况，导致样本空间一直保持n！，没有坍缩，这就是其在数学意义上优秀的原因。