JavaScript專題之亂序

I_Am 發布于2019-08-21 17:00 / 1571人閱讀

摘要：源碼地址為了簡化篇幅，我們對這個數組進行分析，數組長度為，此時采用的是插入排序。插入排序的源碼是其原理在于將第一個元素視為有序序列，遍歷數組，將之后的元素依次插入這個構建的有序序列中。

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

亂序

亂序的意思就是將數組打亂。

嗯，沒有了，直接看代碼吧。

Math.random

一個經常會遇見的寫法是使用 Math.random()：

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

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

console.log(values)

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

看似很美好的一個方案，實際上，效果卻不盡如人意。不信我們寫個 demo 測試一下：

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)

測試原理是：將 [1, 2, 3, 4, 5] 亂序 10 萬次，計算亂序后的數組的最后一個元素是 1、2、3、4、5 的次數分別是多少。

一次隨機的結果為：

[30636, 30906, 20456, 11743, 6259]

該結果表示 10 萬次中，數組亂序后的最后一個元素是 1 的情況共有 30636 次，是 2 的情況共有 30906 次，其他依此類推。

我們會發現，最后一個元素為 5 的次數遠遠低于為 1 的次數，所以這個方案是有問題的。

可是我明明感覺這個方法還不錯吶？初見時還有點驚艷的感覺，為什么會有問題呢？

是的！我很好奇！

插入排序

如果要追究這個問題所在，就必須了解 sort 函數的原理，然而 ECMAScript 只規定了效果，沒有規定實現的方式，所以不同瀏覽器實現的方式還不一樣。

為了解決這個問題，我們以 v8 為例，v8 在處理 sort 方法時，當目標數組長度小于 10 時，使用插入排序；反之，使用快速排序和插入排序的混合排序。

所以我們來看看 v8 的源碼，因為是用 JavaScript 寫的，大家也是可以看懂的。

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

為了簡化篇幅，我們對 [1, 2, 3] 這個數組進行分析，數組長度為 3，此時采用的是插入排序。

插入排序的源碼是：

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

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

我們來個簡單的示意圖：

具體分析

明白了插入排序的原理，我們來具體分析下 [1, 2, 3] 這個數組亂序的結果。

演示代碼為：

var values = [1, 2, 3];

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

注意此時 sort 函數底層是使用插入排序實現，InsertionSort 函數的 from 的值為 0，to 的值為 3。

我們開始逐步分析亂序的過程：

因為插入排序視第一個元素為有序的，所以數組的外層循環從 i = 1 開始，a[i] 值為 2，此時內層循環遍歷，比較 compare(1, 2)，因為 Math.random() - 0.5 的結果有 50% 的概率小于 0 ，有 50% 的概率大于 0，所以有 50% 的概率數組變成 [2, 1, 3]，50% 的結果不變，數組依然為 [1, 2, 3]。

假設依然是 [1, 2, 3]，我們再進行一次分析，接著遍歷，i = 2，a[i] 的值為 3，此時內層循環遍歷，比較 compare(2, 3)：

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

有 50% 的概率變成 [1, 3, 2]，因為還沒有找到 3 正確的位置，所以還會進行遍歷，所以在這 50% 的概率中又會進行一次比較，compare(1, 3)，有 50% 的概率不變，數組為 [1, 3, 2]，此時遍歷結束，有 50% 的概率發生變化，數組變成 [3, 1, 2]。

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

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

數組	i = 1	i = 2	總計
[1, 2, 3]	50% [1, 2, 3]	50% [1, 2, 3]	25% [1, 2, 3]
		25% [1, 3, 2]	12.5% [1, 3, 2]
		25% [3, 1, 2]	12.5% [3, 1, 2]
	50% [2, 1, 3]	50% [2, 1, 3]	25% [2, 1, 3]
		25% [2, 3, 1]	12.5% [2, 3, 1]
		25% [3, 2, 1]	12.5% [3, 2, 1]

為了驗證這個推算是否準確，我們寫個 demo 測試一下：

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

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

console.log(res)

這是一次隨機的結果：

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

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

那么如何實現真正的亂序呢？而這就要提到經典的 Fisher–Yates 算法。

Fisher–Yates

為什么叫 Fisher–Yates 呢？因為這個算法是由 Ronald Fisher 和 Frank Yates 首次提出的。

話不多說，我們直接看 JavaScript 的實現：

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

原理很簡單，就是遍歷數組元素，然后將當前元素與以后隨機位置的元素進行交換，從代碼中也可以看出，這樣亂序的就會更加徹底。

如果利用 ES6，代碼還可以簡化成：

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

還是再寫個 demo 測試一下吧：

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

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

console.log(res)

這是一次隨機的結果：

真正的實現了亂序的效果！

專題系列

JavaScript專題系列目錄地址：https://github.com/mqyqingfeng/Blog。

JavaScript專題系列預計寫二十篇左右，主要研究日常開發中一些功能點的實現，比如防抖、節流、去重、類型判斷、拷貝、最值、扁平、柯里、遞歸、亂序、排序等，特點是研(chao)究(xi) underscore 和 jQuery 的實現方式。

如果有錯誤或者不嚴謹的地方，請務必給予指正，十分感謝。如果喜歡或者有所啟發，歡迎 star，對作者也是一種鼓勵。

云服務器 GPU云服務器 javascript專題系列亂序 webrtc亂序亂序排列

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/89008.html

JavaScript專題系列20篇正式完結！

摘要：寫在前面專題系列是我寫的第二個系列，第一個系列是深入系列。專題系列自月日發布第一篇文章，到月日發布最后一篇，感謝各位朋友的收藏點贊，鼓勵指正。寫在前面 JavaScript 專題系列是我寫的第二個系列，第一個系列是 JavaScript 深入系列。 JavaScript 專題系列共計 20 篇，主要研究日常開發中一些功能點的實現，比如防抖、節流、去重、類型判斷、拷貝、最值、扁平、柯里...

sixleaves 2019-08-21 17:15 評論0 收藏0
JavaScript專題系列文章

摘要：專題系列共計篇，主要研究日常開發中一些功能點的實現，比如防抖節流去重類型判斷拷貝最值扁平柯里遞歸亂序排序等，特點是研究專題之函數組合專題系列第十六篇，講解函數組合，并且使用柯里化和函數組合實現模式需求我們需要寫一個函數，輸入，返回。 JavaScript 專題之從零實現 jQuery 的 extend JavaScritp 專題系列第七篇，講解如何從零實現一個 jQuery 的 ext...

Maxiye 2019-08-21 17:57 評論0 收藏0
2017-10-12 前端日報

摘要：前端日報精選帶來了什么以及對的解釋專題之亂序第期如何無痛降低面條代碼復雜度道阻且長啊前端面試總結附答案上前端安全知識中文開源許可證教程阮一峰的網絡日志裝飾器讓你的代碼更簡潔掘金什么是函數眾成翻譯和十分鐘快速入門眾成翻譯設計最佳實 2017-10-12 前端日報精選 React 16 帶來了什么以及對 Fiber 的解釋JavaScript專題之亂序【第1076期】如何無痛降低 if...

DangoSky 2019-08-21 17:00 評論0 收藏0
JavaScript專題之惰性函數

摘要：專題系列第十五篇，講解惰性函數需求我們現在需要寫一個函數，這個函數返回首次調用時的對象，注意是首次。解決四惰性函數不錯，惰性函數就是解決每次都要進行判斷的這個問題，解決原理很簡單，重寫函數。 JavaScript 專題系列第十五篇，講解惰性函數需求我們現在需要寫一個 foo 函數，這個函數返回首次調用時的 Date 對象，注意是首次。解決一：普通方法 var t; functio...

Jackwoo 2019-08-20 18:52 評論0 收藏0
JavaScript專題之如何求數組的最大值和最小值

摘要：專題系列第八篇，講解多種方式求數組的最大值和最小值前言取出數組中的最大值或者最小值是開發中常見的需求，但你能想出幾種方法來實現這個需求呢提供了函數返回一組數中的最大值，用法是值得注意的是如果有任一參數不能被轉換為數值，則結果為。 JavaScritpt 專題系列第八篇，講解多種方式求數組的最大值和最小值前言取出數組中的最大值或者最小值是開發中常見的需求，但你能想出幾種方法來實現這個...

zhaochunqi 2019-08-20 18:08 評論0 收藏0