1.背景介绍

洗牌算法，顾名思义，它的产生是用来解决类似洗牌这种场景的问题的，目的是产生一串等概率的随机列，使得很难去预测牌的顺序，洗牌算法是我们常见的随机问题，在玩游戏，随机排序时经常用到。同时它也是一道经典的面试题。

2.知识剖析

何为洗牌算法

一个1到n的序列，随机打乱，保证每个数出现在任意一个位置的概率相同。

3.常见问题

有哪些实现洗牌的算法？

4.解决方案

一般化方法

假如要洗牌，那么最随机的做法无疑是从牌堆里随便抽一张出来，然后放在一边，之后从剩下的牌里重复之前的操作，直到所有牌都被抽出来放到了另一堆中。抽象到代码世界，按相同的做法，就是随机从数组里取出一个元素，保存到另一个数组，然后重复之，直到原数组中所有元素都处理掉。

                function shuffle(array) {
                 var copy = [], n = array.length, i;
               // 如果还有剩余元素则继续
               while (n) {
               // 随机取一个元素
               i = Math.floor(Math.random() * array.length);
                // 如果这个元素之前没有被选中过
               if (i in array) {
               copy.push(array[i]);
                delete array[i];
               n--;
               }
             }
                return copy;
             }
            

改进方法

处理完一个元素后，我们用Array的splice()方法将其从目标数组中移除同时也更新了目标数组的长度，如此一来下次遍历的时候是从新的长度开始，不会重复处理的情况了。

             function shuffle(array) {
                 var copy = [], n = array.length, i;
              // 如果还有剩余元素
              while (n) {
              //随机选取一个元素
              i = Math.floor(Math.random() * n--);
              // 移到新数组中
                copy.push(array.splice(i, 1)[0]);
               }
                return copy;
             }
            

再次优化的方法

考虑不创建新的数组来保存已经抽取的元素:随机从数组中抽出一个元素，然后与最后个元素交换，相当于把这个随机抽取的元素放到了数组最后面去，表示它已经是被随机过了，同时被换走的那个元素跑到前面去了，会在后续的重复操作中被随机掉。一轮操作过后，下一轮我们只在剩下的n-1个元素也就是数组的前n-1个元素中进行相同的操作，直到进行到第一个。

                function shuffle(array) {
                    var m = array.length, t, i;
                //如果还有剩余元素
                while (m) {
                //随机选取一个元素
                i = Math.floor(Math.random() * m--);
                // 与当前元素进行交换
                t = array[m];
                array[m] = array[i];
                array[i] = t;
                }
                 return array;
              }
            

5.编码实战

6.扩展思考

除了洗牌算法，还有哪些经典的排序算法？

1.冒泡排序 2.快速排序

3.插入排序 4.二分查找

5.选择排序 6.希尔排序

7.归并排序 8.堆排序

9.基数排序 10.基数排序

7.参考文献

8.更多讨论

1.什么是好的洗牌算法？

2，洗牌中抽牌法指的是什么？

                //每次抽出一张牌，放在另一堆。把最后一张未抽的牌放在空位子上。
                function shuffle_pick_1(m) //洗牌 //抽牌法
                {
                //生成m张牌
                var arr = new Array(m);
                for (var i=0; i
                arr[i] = i;
                }
                //每次抽出一张牌，放在另一堆。因为要在数组里抽出元素，把后面的所有元素向前拉一位，所以很耗时。
                var arr2 = new Array();
                for (var i=m; i>0; i--) {
                var rnd = Math.floor(Math.random()*i);
                arr2.push(arr[rnd]);
                arr.splice(rnd,1);
                }
                return arr2;
                }
            

3，洗牌中换牌法指的是什么？

               //第i张与任意一张牌换位子，换完一轮即可。
                function shuffle_swap(m) //洗牌 //换牌法
                {
                //生成m张牌
                var arr = new Array(m);
                for (var i=0; i
                arr[i] = i;
                }
                //第i张与任意一张牌换位子，换完一轮即可
                for (var i=0; i
                var rnd = Math.floor(Math.random()*(i+1)),
                temp = arr[rnd];
                arr[rnd] = arr[i];
                arr[i]=temp;
                }
                return arr;
                }
            

感谢大家观看

BY : 张新