亂序的意思想必沒有不知道：就是將數(shù)組打亂。聽到亂序一般都會想到js的隨機函數(shù)Math.random();

var values = [1, 2, 3, 4, 5];values.sort(function() { return Math.random() - 0.5;});console.log(values)

利用數(shù)組的sort方法，判斷隨機出來的0~1值與0.5的大小，實現(xiàn)排序。看似一個很不錯的方案，代碼邏輯也沒毛病，一般情況下也確實能夠做到亂序。但是，這是一個偽排序，是的還有但是（我也是今天才知道的，不求甚解的毛病啊~），為什么呢？先看看這個亂序的結果吧：

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萬次，計算亂序后數(shù)組的最后一個元素是1,2,3,4,5的次數(shù)分別是多少。

運行幾次得到的結果為：

由這幾次運行得到的結果可以看出：2出現(xiàn)的最后的次數(shù)明顯少于其他數(shù)字，不是隨機嗎？按理說概率應該是相差不多才對啊！其實問題是在sort方法，各個瀏覽器對sort的實現(xiàn)方式不一樣。

Chrome的sort

基于V8引擎，它的排序算進行了很多的優(yōu)化，但是核心是小于等于10的數(shù)組用插入排序（穩(wěn)定），大于10的采用了quickSort（不穩(wěn)定）

FireFox的sort

基于SpiderMonkey引擎，采用了歸并排序（穩(wěn)定）

Safari的sort

基于Nitro（JavaScriptCore ）引擎，如果沒有自定義的排序規(guī)則傳入，采用桶排序（不一定穩(wěn)定， 桶排序的穩(wěn)定性取決于桶內排序的穩(wěn)定性, 因此其穩(wěn)定性不確定。），傳入自定義規(guī)則，采用歸并排序（穩(wěn)定）

Microsoft Edge/IE9+

基于Chakra引擎，采用快排（不穩(wěn)定）

以下用chrome測試亂序各種結果的概率：

var times = 100000;var res = {};for(var i = 0; i < times; i++){ var arr = [1, 2, 3]; arr.sort(() => Match.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);

結果如下

幾種結果出現(xiàn)的概率相差很大...所以說不是一個真正的亂序。

Fisher-Yates算法【也叫“洗牌算法”】：為什么叫 Fisher?Yates 呢？ 因為這個算法是由 Ronald Fisher 和 Frank Yates 首次提出的。代碼如下：

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

其原理就是：遍歷數(shù)組元素，然后將當前元素與以后隨機位置的元素進行交換，這樣亂序更加徹底。

如果用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)

得到結果如下：

各種結果的概率都基本相同了，所以真正實現(xiàn)了亂序的效果！

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持好吧啦網(wǎng)。