JavaScript开发有时会遇到随机排序（洗牌）数组的需求。一种常见的写法是这样的：functionshuffle(arr){arr.sort(function(){returnMath.random()-0.5;});}或者用更简洁的ES6写法：functionshuffle(arr){arr.sort(()=>Math.random()-0.5);}我经常用这种写法，不久前才意识到这种写法有问题，不能真正随机打乱数组。问题看下面代码，我们生成一个长度为10的数组['a','b','c','d','e','f','g','h','i','j']，用上面的方法对数组进行打乱，多次执行后，你会发现每个元素仍然有很大概率出现在它原来的位置附近。letn=10000;letcount=(newArray(10)).fill(0);for(leti=0;iMath.random()-0.5);count[arr.indexOf('a')]++;}console.log(count);在Node.JS6中执行，输出[2891,2928,1927,1125,579,270,151,76,34,19]（具有一定的随机性，每次结果不同，但分布应该大致相同），即经过10000次排序，字母'a'（数组中的第一个元素）在第一个位置出现了大约2891次，在第二个位置出现了2928次，第一个位置对应的出现次数只有19次。如果把这个分布画成图像，会是这样：同理，我们可以计算出字母'f'（数组中的第六个元素）在每个位置的分布为[312,294,579,1012,1781,2232,1758,1129,586,317]，图像如下：如果排序真的是随机的，那么每个元素出现在每个位置的概率应该是一样的，实验结果表明，每个元素中的数字位置应该很近，不应该像现在这样明显集中在原位置附近。因此，我们可以认为使用arr.sort(()=>Math.random()-0.5)这样的方法并不是真正的随机排序。另外需要注意的是，上面的分布只适用于数组长度不超过10的情况，如果数组更长，比如长度为11，则会是另一种分布。例如：leta=['a','b','c','d','e','f','g','h','i','j','k'];//长度为11letn=10000;letcount=(newArray(a.length)).fill(0);for(leti=0;iMath.random()-0.5);count[arr.indexOf('a')]++;}console.log(count);在Node.JS6中执行，结果为[785,819,594,679,941,1067,932,697,624,986,1876]，其中第一个元素'a'的分布如下：原因对于sort_03的不同分布是v8引擎使用短数组和长数组有不同的排序方式（下面讨论）。可以看出，两种算法的结果虽然不同，但显然不够统一。国外有人为Shuffle算法的可视化写了一个页面。在上面可以更直观的看出，使用arr.sort(()=>Math.random()-0.5)确实是非常随机的。探索看一下ECMAScript中关于Array.prototype.sort(comparefn)的标准，没有具体说明具体的实现算法，但是提到了一点：Callingcomparefn(a,b)alwaysreturnsthesamevaluevwhengivenaspecificpair值a和b作为它的两个参数。也就是说，对于同一组a和b值，comparefn(a,b)需要始终返回相同的值。上面的()=>Math.random()-0.5（即(a,b)=>Math.random()-0.5）显然不满足这个条件。查看v8引擎数组部分的源码，我注意到它出于性能考虑，对短数组使用插入排序，对长数组使用快速排序。至此，我们可以理解为什么()=>Math.random()-0.5不再真正随机打乱数组排序。（有一点不明白：源码说长度小于等于22使用插入排序，长度大于22使用快速排序，但是实际测试结果发现边界长度为10.)解题就知道了，解法也比较简单。解法1既然(a,b)=>Math.random()-0.5的问题是不能保证每次对同一组a和b返回的值都一样，那我们不妨修改数组元素，例如每个元素i变换为：letnew_i={v:i,r:Math.random()};即转化为一个对象，将原来的值存入键v中，在其上增加一个键r，值是一个随机数，然后在排序时比较这个随机数：arr.sort((a,b)=>a.r-b.r);完整代码如下：functionshuffle(arr){letnew_arr=arr.map(i=>({v:i,r:Math.random()}));new_arr.sort((a,b)=>a.r-b.r);arr.splice(0,arr.length,...new_arr.map(i=>i.v));}leta=['a','b','c','d','e','f','g','h','i','j'];letn=10000;letcount=(newArray(a.length)).fill(0);for(leti=0;iMath.random()-0.5。目前，Fisher-Yatesshuffle算法应该是最好的选择。
