摘要：源碼地址為了簡(jiǎn)化篇幅，我們對(duì)這個(gè)數(shù)組進(jìn)行分析，數(shù)組長(zhǎng)度為，此時(shí)采用的是插入排序。插入排序的源碼是其原理在于將第一個(gè)元素視為有序序列，遍歷數(shù)組，將之后的元素依次插入這個(gè)構(gòu)建的有序序列中。

JavaScript 專(zhuān)題系列第十九篇，講解數(shù)組亂序，重點(diǎn)探究 Math.random() 為什么不能真正的亂序？

亂序的意思就是將數(shù)組打亂。

嗯，沒(méi)有了，直接看代碼吧。

一個(gè)經(jīng)常會(huì)遇見(jiàn)的寫(xiě)法是使用 Math.random()：

var values = [1, 2, 3, 4, 5];

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

console.log(values)

Math.random() - 0.5 隨機(jī)得到一個(gè)正數(shù)、負(fù)數(shù)或是 0，如果是正數(shù)則降序排列，如果是負(fù)數(shù)則升序排列，如果是 0 就不變，然后不斷的升序或者降序，最終得到一個(gè)亂序的數(shù)組。

看似很美好的一個(gè)方案，實(shí)際上，效果卻不盡如人意。不信我們寫(xiě)個(gè) demo 測(cè)試一下：

var times = [0, 0, 0, 0, 0];

for (var i = 0; i < 100000; i++) {
    
    let arr = [1, 2, 3, 4, 5];
    
    arr.sort(() => Math.random() - 0.5);
    
    times[arr[4]-1]++;

}

console.log(times)

測(cè)試原理是：將 [1, 2, 3, 4, 5] 亂序 10 萬(wàn)次，計(jì)算亂序后的數(shù)組的最后一個(gè)元素是 1、2、3、4、5 的次數(shù)分別是多少。

一次隨機(jī)的結(jié)果為：

[30636, 30906, 20456, 11743, 6259]

該結(jié)果表示 10 萬(wàn)次中，數(shù)組亂序后的最后一個(gè)元素是 1 的情況共有 30636 次，是 2 的情況共有 30906 次，其他依此類(lèi)推。

我們會(huì)發(fā)現(xiàn)，最后一個(gè)元素為 5 的次數(shù)遠(yuǎn)遠(yuǎn)低于為 1 的次數(shù)，所以這個(gè)方案是有問(wèn)題的。

可是我明明感覺(jué)這個(gè)方法還不錯(cuò)吶？初見(jiàn)時(shí)還有點(diǎn)驚艷的感覺(jué)，為什么會(huì)有問(wèn)題呢？

是的！我很好奇！

如果要追究這個(gè)問(wèn)題所在，就必須了解 sort 函數(shù)的原理，然而 ECMAScript 只規(guī)定了效果，沒(méi)有規(guī)定實(shí)現(xiàn)的方式，所以不同瀏覽器實(shí)現(xiàn)的方式還不一樣。

為了解決這個(gè)問(wèn)題，我們以 v8 為例，v8 在處理 sort 方法時(shí)，當(dāng)目標(biāo)數(shù)組長(zhǎng)度小于 10 時(shí)，使用插入排序；反之，使用快速排序和插入排序的混合排序。

所以我們來(lái)看看 v8 的源碼，因?yàn)槭怯?JavaScript 寫(xiě)的，大家也是可以看懂的。

源碼地址：https://github.com/v8/v8/blob/master/src/js/array.js

為了簡(jiǎn)化篇幅，我們對(duì) [1, 2, 3] 這個(gè)數(shù)組進(jìn)行分析，數(shù)組長(zhǎng)度為 3，此時(shí)采用的是插入排序。

插入排序的源碼是：

function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
        var element = a[i];
        for (var j = i - 1; j >= from; j--) {
            var tmp = a[j];
            var order = comparefn(tmp, element);
            if (order > 0) {
                a[j + 1] = tmp;
            } else {
                break;
            }
        }
        a[j + 1] = element;
    }
};

其原理在于將第一個(gè)元素視為有序序列，遍歷數(shù)組，將之后的元素依次插入這個(gè)構(gòu)建的有序序列中。

我們來(lái)個(gè)簡(jiǎn)單的示意圖：

明白了插入排序的原理，我們來(lái)具體分析下 [1, 2, 3] 這個(gè)數(shù)組亂序的結(jié)果。

演示代碼為：

var values = [1, 2, 3];

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

注意此時(shí) sort 函數(shù)底層是使用插入排序?qū)崿F(xiàn)，InsertionSort 函數(shù)的 from 的值為 0，to 的值為 3。

我們開(kāi)始逐步分析亂序的過(guò)程：

因?yàn)椴迦肱判蛞暤谝粋€(gè)元素為有序的，所以數(shù)組的外層循環(huán)從 i = 1 開(kāi)始，a[i] 值為 2，此時(shí)內(nèi)層循環(huán)遍歷，比較 compare(1, 2)，因?yàn)?Math.random() - 0.5 的結(jié)果有 50% 的概率小于 0 ，有 50% 的概率大于 0，所以有 50% 的概率數(shù)組變成 [2, 1, 3]，50% 的結(jié)果不變，數(shù)組依然為 [1, 2, 3]。

假設(shè)依然是 [1, 2, 3]，我們?cè)龠M(jìn)行一次分析，接著遍歷，i = 2，a[i] 的值為 3，此時(shí)內(nèi)層循環(huán)遍歷，比較 compare(2, 3)：

有 50% 的概率數(shù)組不變，依然是 [1, 2, 3]，然后遍歷結(jié)束。

有 50% 的概率變成 [1, 3, 2]，因?yàn)檫€沒(méi)有找到 3 正確的位置，所以還會(huì)進(jìn)行遍歷，所以在這 50% 的概率中又會(huì)進(jìn)行一次比較，compare(1, 3)，有 50% 的概率不變，數(shù)組為 [1, 3, 2]，此時(shí)遍歷結(jié)束，有 50% 的概率發(fā)生變化，數(shù)組變成 [3, 1, 2]。

綜上，在 [1, 2, 3] 中，有 50% 的概率會(huì)變成 [1, 2, 3]，有 25% 的概率會(huì)變成 [1, 3, 2]，有 25% 的概率會(huì)變成 [3, 1, 2]。

另外一種情況 [2, 1, 3] 與之分析類(lèi)似，我們將最終的結(jié)果匯總成一個(gè)表格：

為了驗(yàn)證這個(gè)推算是否準(zhǔn)確，我們寫(xiě)個(gè) demo 測(cè)試一下：

var times = 100000;
var res = {};

for (var i = 0; i < times; i++) {
    
    var arr = [1, 2, 3];
    arr.sort(() => Math.random() - 0.5);
    
    var key = JSON.stringify(arr);
    res[key] ? res[key]++ :  res[key] = 1;
}

// 為了方便展示，轉(zhuǎn)換成百分比
for (var key in res) {
    res[key] = res[key] / times * 100 + "%"
}

console.log(res)

這是一次隨機(jī)的結(jié)果：

我們會(huì)發(fā)現(xiàn)，亂序后，3 還在原位置(即 [1, 2, 3] 和 [2, 1, 3]) 的概率有 50% 呢。

所以根本原因在于什么呢？其實(shí)就在于在插入排序的算法中，當(dāng)待排序元素跟有序元素進(jìn)行比較時(shí)，一旦確定了位置，就不會(huì)再跟位置前面的有序元素進(jìn)行比較，所以就亂序的不徹底。

那么如何實(shí)現(xiàn)真正的亂序呢？而這就要提到經(jīng)典的 Fisher–Yates 算法。

為什么叫 Fisher–Yates 呢？ 因?yàn)檫@個(gè)算法是由 Ronald Fisher 和 Frank Yates 首次提出的。

話不多說(shuō)，我們直接看 JavaScript 的實(shí)現(xiàn)：

function shuffle(a) {
    var j, x, i;
    for (i = a.length; i; i--) {
        j = Math.floor(Math.random() * i);
        x = a[i - 1];
        a[i - 1] = a[j];
        a[j] = x;
    }
    return a;
}

原理很簡(jiǎn)單，就是遍歷數(shù)組元素，然后將當(dāng)前元素與以后隨機(jī)位置的元素進(jìn)行交換，從代碼中也可以看出，這樣亂序的就會(huì)更加徹底。

如果利用 ES6，代碼還可以簡(jiǎn)化成：

function shuffle(a) {
    for (let i = a.length; i; i--) {
        let j = Math.floor(Math.random() * i);
        [a[i - 1], a[j]] = [a[j], a[i - 1]];
    }
    return a;
}

還是再寫(xiě)個(gè) demo 測(cè)試一下吧：

var times = 100000;
var res = {};

for (var i = 0; i < times; i++) {
    var arr = shuffle([1, 2, 3]);

    var key = JSON.stringify(arr);
    res[key] ? res[key]++ :  res[key] = 1;
}

// 為了方便展示，轉(zhuǎn)換成百分比
for (var key in res) {
    res[key] = res[key] / times * 100 + "%"
}

console.log(res)

這是一次隨機(jī)的結(jié)果：

真正的實(shí)現(xiàn)了亂序的效果！

JavaScript專(zhuān)題系列目錄地址：https://github.com/mqyqingfeng/Blog。

JavaScript專(zhuān)題系列預(yù)計(jì)寫(xiě)二十篇左右，主要研究日常開(kāi)發(fā)中一些功能點(diǎn)的實(shí)現(xiàn)，比如防抖、節(jié)流、去重、類(lèi)型判斷、拷貝、最值、扁平、柯里、遞歸、亂序、排序等，特點(diǎn)是研(chao)究(xi) underscore 和 jQuery 的實(shí)現(xiàn)方式。

如果有錯(cuò)誤或者不嚴(yán)謹(jǐn)?shù)牡胤?，?qǐng)務(wù)必給予指正，十分感謝。如果喜歡或者有所啟發(fā)，歡迎 star，對(duì)作者也是一種鼓勵(lì)。