关于JavaScript的数组随机排序

, 'j', 'k']; // 长度为11

let n = 10000;

let count = (new Array(a.length)).fill(0);

for (let i = 0; i < n; i ++) {

let arr = [].concat(a);

arr.sort(() => Math.random() - 0.5);

count[arr.indexOf('a')]++;

}

console.log(count);

在 Node.JS 6 中履行，结不雅为[ 785, 819, 594, 679, 941, 1067, 932, 697, 624, 986, 1876 ]，个中第一个元素'a'的分布图如下：

分布不合的原因是 v8 引擎中针对短数组和长数组应用了不合的排序办法(下面会讲)。可以看到，两种算法的结不雅固然不合，但都明显不敷平均。

国外有人写了一个Shuffle算法可视化的页面，在膳绫擎可以更直不雅地看到应用arr.sort(() => Math.random() - 0.5)切实其实是很不随机的。

摸索

看了一下ECMAScript中关于Array.prototype.sort(comparefn)的标准，个中并没针砭定具体的实现算法，然则提到一点：

Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments.

也就是说，对同一组a、b的值，comparefn(a, b)须要老是返回雷同的值。而膳绫擎的() => Math.random() - 0.5(即(a, b) => Math.random() - 0.5)显然不知足这个前提。

翻看v8引擎数组部分的源码，留意到它出于对机能的┞峰酌，对短数组应用的是插入排序，对长数组则应用了快速排序，至此，也就能懂得为什么() => Math.random() - 0.5并不克不及真正随机打乱数组排序了。(有一个没明白的处所：源码中说的是对长度小于等于 22 的应用插入排序，大年夜于 22 的应用快排，但实际测试结不雅显示分界长度是 10。)

解决筹划

知道问题地点，解决筹划也就比较简单了。

既然(a, b) => Math.random() - 0.5的问题是不克不及包管针对同一组a、b每次返回的值雷同，那么我们不妨将数组元素改革一下，比如将每个元素i改革为：

let new_i = { 
 
    v: i, 
 
    r: Math.random() 
 
};

即将它改革为一个对象，本来的值存储在键v中，同时给它增长一个键r，值为一个随机数，然后排序时比较这个随机数：

arr.sort((a, b) => a.r - b.r);

完全代码如下：

function shuffle(arr) { 
 
    let new_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)); 
 
} 
 
  
 
let a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'	
			 2/4   首页 上一页 1 2 3 4 下一页 尾页	
			

　　推荐阅读
　　智能数据湖势在必行
            
            由大年夜数据触发的数据驱动的做法是一种最好的懂得。如今，各个组织正在各类数据构造，格局和分布式地舆数据源地位等方面进行竞争，并在时光框架和数量上跨越了现有体系的才能。以往人们>>>详细阅读


本文标题：关于JavaScript的数组随机排序
地址：http://www.17bianji.com/lsqh/34614.html
 1/2    1