ECMAScript常用之sort打乱数组方法确实中?

JavaScript
开发被有时见面逢要将一个数组随机排序(shuffle)的要求,一个广大的写法是这么:

function shuffle(arr) {
   arr.sort(function () {
      return Math.random() - 0.5;
   });
}

还是用还简明的 ES6 的写法:

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

在 Node.JS 6 中执行,输出[ 2891, 2928, 1927, 1125, 579, 270, 151, 76,
34, 19 ](带有自然随机性,每次结果还不比,但大体分布应该同样),即进行
10000 次排序后,字母’a’(数组中之首先独要素)有约 2891
次出现在第一个职务、2928 次出现在第二单职位,与的对应之无非发 19
次出现在末一个职位。如果管这个分布绘制成图像,会是下边这样:

ECMAScript 1

类似地,我们可算是有字母’f’(数组中之第六个要素)在各个位置出现的遍布为[
312, 294, 579, 1012, 1781, 2232, 1758, 1129, 586, 317 ],图像如下:

ECMAScript 2

倘若排序真的是即兴的,那么每个元素于每个位置出现的概率都应一致,实验结果各个位置的数字应该格外类似,而不应像现在如此明确地集中在原来位置紧邻。因此,我们好当,使用形如arr.sort(() => Math.random() - 0.5)如此这般的计获得的连无是真的随机排序。

另外,需要留意的凡方的遍布就适用于数组长度不超越 10
的景,如果数组更增长,比如长度也 11,则会是其余一样种植分布。比如:

let a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', '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’的遍布图如下:

ECMAScript 3

遍布不同之由来是 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'];
let n = 10000;
let count = (new Array(a.length)).fill(0);

for (let i = 0; i < n; i ++) {
    shuffle(a);
    count[a.indexOf('a')]++;
}

console.log(count);

如出一辙浅实施结果吧:[ 1023, 991, 1007, 967, 990, 1032, 968, 1061, 990, 971
]。多次认证,同时以这查看shuffle(arr)函数结果的可视化分布,可以看来,这个办法可当足够随机了。

方案二(Fisher–Yates shuffle)

待注意的凡,上面的法门则满足随机性要求了,但当性能上连无是可怜好,需要遍历几涂鸦数组,还要针对数组进行splice等操作。

考察Lodash 库中的 shuffle 算法,注意到她应用的莫过于是Fisher–Yates
洗牌算法,这个算法由 Ronald Fisher 和 Frank Yates 于 1938 年提出,然后于
1964 年由 Richard Durstenfeld
改编为适用于计算机编程的本子。用伪代码描述如下:

-- To shuffle an array a of n elements (indices 0..n-1):  
    for i from n−1 downto 1 do  
        j ← random integer such that 0 ≤ j ≤ i  
        exchange a[j] and a[i]

一个贯彻如下(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;
  }
}

小结

一旦假定以数组随机排序,千万不要还就此(a, b) => Math.random() - 0.5如此的法。
眼下而言,Fisher–Yates shuffle 算法应该是无与伦比好之精选。