目录

1.背景介绍

2.知识剖析

3.常见问题

4.解决方案

5.扩展思考

6.参考文献

7.更多讨论

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);
                    }
            

但是这种写法有问题，并不能实现真正的随机

这样排序的问题

看下面的代码，我们生成一个长度为 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)这样的方法得到的并不是真正的随机排序。

国外有人写了一个Shuffle算法可视化的页面， 在上面可以更直观地看到使用arr.sort(() => Math.random() - 0.5)的确是很不随机的。

解决方案

Fisher–Yates shuffle

Fisher–Yates shuffle洗牌算法

介绍以及实现

这个算法由 Ronald Fisher 和 Frank Yates 于 1938 年提出，然后在 1964 年由 Richard Durstenfeld 改编为适用于电脑编程的版本。

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); 
                

在上面的代码中，我们创建了一个 shffle() 方法，该方法用于随机排列数组内的元素。此外，我们将该方法挂载在了 Array 对象的原型下面，所以任何数组都可以直接调用该方法

这种方法的工作原理

在编辑器内讲解

3.常见问题

随机的效率？

上帝掷骰子吗？世界上存在真正的随机吗？

4.解决方案

5.扩展思考

6.参考文献

参考一： 大神博客

随机结果查看

箭头函数mdn

7.更多讨论

鸣谢

感谢大家观看

宋恒