資訊專欄INFORMATION COLUMN
摘要：比如元素大概率出現在數組的頭部，元素大概率出現在數組的尾部，所有元素大概率停留在自己初始位置。當目標數組長度小于時，使用插入排序反之，使用快排。而在排序算法中，大多數情況都不會滿足這樣的條件。
最近看了一篇非常有趣的文章：關于JavaScript的數組隨機排序，其作者為oldj前輩。文中指出我們用來“將一個數組隨機排序”的經典寫法所存在的問題，獲益匪淺。
本文將以更加詳盡的材料和更多樣的code demo進行闡述。并嘗試用“Fisher–Yates shuffle”洗牌算法進行終極解答。
多個熟悉的場景將一個數組進行亂序處理，是一個非常簡單但是非常常用的需求。
比如，“猜你喜歡”、“點擊換一批”、“中獎方案”等等，都可能應用到這樣的處理。包括我自己在寫代碼的時候，也確實遇到過。
一般比較經典且流行的方案為：對對象數組采用array.sort()方法，并傳入一個比較函數（comparison function），這個比較函數隨機返回一個介于［－0.5， 0.5］之間的數值：
var numbers = [12,4,16,3];
numbers.sort(function() {
return .5 - Math.random();
});
關于這么做的理論基礎這里不再進行闡釋。如果您不明白，可以了解一下JS中sort函數的使用方法。
有毒的array.sort方法正像oldj前輩文章指出的那樣，其實使用這個方法亂序一個數組是有問題的。
為此，我寫了一個腳本進行驗證。并進行了可視化處理。強烈建議讀者去Github圍觀一下，clone下來自己試驗。
腳本中，我對
var letters = ["A","B","C","D","E","F","G","H","I","J"];
letters這樣一個數組使用array.sort方法進行了10000次亂序處理，并把亂序的每一次結果存儲在countings當中。
結果在頁面上進行輸出：
var countings = [
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0}
];
var letters=["A","B","C","D","E","F","G","H","I","J"];
for (var i = 0; i < 10000; i++) {
var r = ["A","B","C","D","E","F","G","H","I","J"].sort(function() {
return .5 - Math.random();
});
for(var j = 0; j <= 9; j++) {
countings[j][r[j]]++;
}
}
for(var i = 0; i <= 9;i++) {
for(var j = 0;j <= 9;j++) {
document.getElementById("results").rows[i + 1].cells[j + 1].firstChild.data = countings[i][letters[j]];
}
}
得到結果如圖：
這個結果對數組中的每一項元素在亂序后的結果進行了統計。
如果點擊“recalculate”按鈕，可以進行多次10000次取樣試驗。
不管點擊按鈕幾次，你都會發現整體亂序之后的結果絕對不是“完全隨機”。
比如A元素大概率出現在數組的頭部，J元素大概率出現在數組的尾部，所有元素大概率停留在自己初始位置。
由此可以先粗暴地得出結論：
使用array.sort方法進行亂序處理，絕對是有問題的。
但是為什么會有問題呢？這需要從array.sort方法排序底層說起。
在Chrome v8引擎源碼中，可以清晰看到，
v8在處理sort方法時，使用了插入排序和快排兩種方案。當目標數組長度小于10時，使用插入排序；反之，使用快排。
Chrome’s v8 uses a combination of InsertionSort and QuickSort. That is, if the array is less than 10 elements in length, it uses an InsertionSort.
其實不管用什么排序方法，大多數排序算法的時間復雜度介于O(n)到O(n2)之間，元素之間的比較次數通常情況下要遠小于n(n-1)/2，也就意味著有一些元素之間根本就沒機會相比較（也就沒有了隨機交換的可能），這些 sort 隨機排序的算法自然也不能真正隨機。
怎么理解上邊這句話呢？其實我們想使用array.sort進行亂序，理想的方案或者說純亂序的方案是數組中每兩個元素都要進行比較，這個比較有50%的交換位置概率。這樣一來，總共比較次數一定為n(n-1)。
而在sort排序算法中，大多數情況都不會滿足這樣的條件。因而當然不是完全隨機的結果了。
順便說一下，關于v8引擎的排序方案，源碼使用JS實現的，非常利于前端程序員閱讀。其中，對應不同的數組長度，使用了快排和插入排序不同方法。同時使用了大量的性能優化技巧，尤其是關于快排的pivot選擇上十分有意思。感興趣的讀者不妨研究一下。
真正意義上的亂序要想實現真正意義上的亂序，其實不難。我們首先要規避不穩定的array.sort方法。
在計算機科學中，有一個專門的：洗牌算法Fisher–Yates shuffle。如果你對算法天生遲鈍，也不要慌張。這里我一步一步來實現，相信您一定要得懂。
先來整體看一下所有代碼實現，一共也就10行：
Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
return input;
}
var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle();
console.log(tempArray);
解析：
首先我們有一個已經排好序的數組：
Step1：
第一步需要做的就是，從數組末尾開始，選取最后一個元素。
在數組一共9個位置中，隨機產生一個位置，該位置元素與最后一個元素進行交換。
Step2：
上一步中，我們已經把數組末尾元素進行隨機置換。
接下來，對數組倒數第二個元素動手。在除去已經排好的最后一個元素位置以外的8個位置中，隨機產生一個位置，該位置元素與倒數第二個元素進行交換。
Step3：
理解了前兩部，接下來就是依次進行，如此簡單。
以上方法，是基于Fisher–Yates shuffle洗牌算法。下面，我們就需要自己開動腦筋，完成一個亂序方案。
其實這并不難，關鍵在于如何生產真正的亂序。因為往往生成的并不是完全意義上的亂序，關于這一點，讀者可以參考The Danger of Na?veté一文。
我們來看一下社區上劉哇勇的一系列進階方案：
function shuffle (array) {
var copy = [],
n = array.length,
i;
while (n) {
i = Math.floor(Math.random() * array.length);
if (i in array) {
copy.push(array[i]);
delete array[i];
n--;
}
}
return copy;
}
關于這種方案，也給出了分析：
我們創建了一個copy數組，然后遍歷目標數組，將其元素復制到copy數組里，同時將該元素從目標數組中刪除，這樣下次遍歷的時候就可以跳過這個序號。而這一實現的問題正在于此，即使一個序號上的元素已經被處理過了，由于隨機函數產生的數是隨機的，所有這個被處理過的元素序號可能在之后的循環中不斷出現，一是效率問題，另一個就是邏輯問題了，存在一種可能是永遠運行不完。
改進的方案為：
function shuffle(array) {
var copy = [],
n = array.length,
i;
while (n) {
i = Math.floor(Math.random() * n--);
copy.push(array.splice(i, 1)[0]);
}
return copy;
}
改進的做法就是處理完一個元素后，用Array的splice()方法將其從目標數組中移除，同時也更新了目標數組的長度。如此一來下次遍歷的時候是從新的長度開始，不會重復處理的情況了。
當然這樣的方案也有不足之處：比如，我們創建了一個copy數組進行返回，在內存上開辟了新的空間。
不過，這可以完全避免：
function shuffle(array) {
var m = array.length,
t, i;
while (m) {
i = Math.floor(Math.random() * m--);
t = array[m];
array[m] = array[i];
array[i] = t;
}
return array;
}
有趣的是，這樣的實現已經完全等同于上文洗牌算法Fisher–Yates shuffle的方案了。
總結本文剖析了“數組亂序”這么一個簡單，但是有趣的需求場景。
對這個場景的深入分析，讓我們認識到JS和計算機算法中的一些玄妙。
文章簡要提到了V8引擎對array.sort的處理、洗牌算法Fisher–Yates等內容。希望對讀者有所啟發。
Happy Coding!
PS: 作者Github倉庫，歡迎通過代碼各種形式交流。
最近看了一篇非常有趣的文章：關于JavaScript的數組隨機排序，其作者為oldj前輩。文中指出我們用來“將一個數組隨機排序”的經典寫法所存在的問題，獲益匪淺。
本文將以更加詳盡的材料和更多樣的code demo進行闡述。并嘗試用“Fisher–Yates shuffle”洗牌算法進行終極解答。
多個熟悉的場景將一個數組進行亂序處理，是一個非常簡單但是非常常用的需求。
比如，“猜你喜歡”、“點擊換一批”、“中獎方案”等等，都可能應用到這樣的處理。包括我自己在寫代碼的時候，也確實遇到過。
一般比較經典且流行的方案為：對對象數組采用array.sort()方法，并傳入一個比較函數（comparison function），這個比較函數隨機返回一個介于［－0.5， 0.5］之間的數值：
var numbers = [12,4,16,3];
numbers.sort(function() {
return .5 - Math.random();
});
關于這么做的理論基礎這里不再進行闡釋。如果您不明白，可以了解一下JS中sort函數的使用方法。
有毒的array.sort方法正像oldj前輩文章指出的那樣，其實使用這個方法亂序一個數組是有問題的。
為此，我寫了一個腳本進行驗證。并進行了可視化處理。強烈建議讀者去Github圍觀一下，clone下來自己試驗。
腳本中，我對
var letters = ["A","B","C","D","E","F","G","H","I","J"];
letters這樣一個數組使用array.sort方法進行了10000次亂序處理，并把亂序的每一次結果存儲在countings當中。
結果在頁面上進行輸出：
var countings = [
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0},
{A:0,B:0,C:0,D:0,E:0,F:0,G:0,H:0,I:0,J:0}
];
var letters=["A","B","C","D","E","F","G","H","I","J"];
for (var i = 0; i < 10000; i++) {
var r = ["A","B","C","D","E","F","G","H","I","J"].sort(function() {
return .5 - Math.random();
});
for(var j = 0; j <= 9; j++) {
countings[j][r[j]]++;
}
}
for(var i = 0; i <= 9;i++) {
for(var j = 0;j <= 9;j++) {
document.getElementById("results").rows[i + 1].cells[j + 1].firstChild.data = countings[i][letters[j]];
}
}
得到結果如圖：
這個結果對數組中的每一項元素在亂序后的結果進行了統計。
如果點擊“recalculate”按鈕，可以進行多次10000次取樣試驗。
不管點擊按鈕幾次，你都會發現整體亂序之后的結果絕對不是“完全隨機”。
比如A元素大概率出現在數組的頭部，J元素大概率出現在數組的尾部，所有元素大概率停留在自己初始位置。
由此可以先粗暴地得出結論：
使用array.sort方法進行亂序處理，絕對是有問題的。
但是為什么會有問題呢？這需要從array.sort方法排序底層說起。
在Chrome v8引擎源碼中，可以清晰看到，
v8在處理sort方法時，使用了插入排序和快排兩種方案。當目標數組長度小于10時，使用插入排序；反之，使用快排。
Chrome’s v8 uses a combination of InsertionSort and QuickSort. That is, if the array is less than 10 elements in length, it uses an InsertionSort.
其實不管用什么排序方法，大多數排序算法的時間復雜度介于O(n)到O(n2)之間，元素之間的比較次數通常情況下要遠小于n(n-1)/2，也就意味著有一些元素之間根本就沒機會相比較（也就沒有了隨機交換的可能），這些 sort 隨機排序的算法自然也不能真正隨機。
怎么理解上邊這句話呢？其實我們想使用array.sort進行亂序，理想的方案或者說純亂序的方案是數組中每兩個元素都要進行比較，這個比較有50%的交換位置概率。這樣一來，總共比較次數一定為n(n-1)。
而在sort排序算法中，大多數情況都不會滿足這樣的條件。因而當然不是完全隨機的結果了。
順便說一下，關于v8引擎的排序方案，源碼使用JS實現的，非常利于前端程序員閱讀。其中，對應不同的數組長度，使用了快排和插入排序不同方法。同時使用了大量的性能優化技巧，尤其是關于快排的pivot選擇上十分有意思。感興趣的讀者不妨研究一下。
真正意義上的亂序要想實現真正意義上的亂序，其實不難。我們首先要規避不穩定的array.sort方法。
在計算機科學中，有一個專門的：洗牌算法Fisher–Yates shuffle。如果你對算法天生遲鈍，也不要慌張。這里我一步一步來實現，相信您一定要得懂。
先來整體看一下所有代碼實現，一共也就10行：
Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
return input;
}
var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle();
console.log(tempArray);
解析：
首先我們有一個已經排好序的數組：
Step1：
第一步需要做的就是，從數組末尾開始，選取最后一個元素。
在數組一共9個位置中，隨機產生一個位置，該位置元素與最后一個元素進行交換。
Step2：
上一步中，我們已經把數組末尾元素進行隨機置換。
接下來，對數組倒數第二個元素動手。在除去已經排好的最后一個元素位置以外的8個位置中，隨機產生一個位置，該位置元素與倒數第二個元素進行交換。
Step3：
理解了前兩部，接下來就是依次進行，如此簡單。
以上方法，是基于Fisher–Yates shuffle洗牌算法。下面，我們就需要自己開動腦筋，完成一個亂序方案。
其實這并不難，關鍵在于如何生產真正的亂序。因為往往生成的并不是完全意義上的亂序，關于這一點，讀者可以參考The Danger of Na?veté一文。
我們來看一下社區上劉哇勇的一系列進階方案：
function shuffle (array) {
var copy = [],
n = array.length,
i;
while (n) {
i = Math.floor(Math.random() * array.length);
if (i in array) {
copy.push(array[i]);
delete array[i];
n--;
}
}
return copy;
}
關于這種方案，也給出了分析：
我們創建了一個copy數組，然后遍歷目標數組，將其元素復制到copy數組里，同時將該元素從目標數組中刪除，這樣下次遍歷的時候就可以跳過這個序號。而這一實現的問題正在于此，即使一個序號上的元素已經被處理過了，由于隨機函數產生的數是隨機的，所有這個被處理過的元素序號可能在之后的循環中不斷出現，一是效率問題，另一個就是邏輯問題了，存在一種可能是永遠運行不完。
改進的方案為：
function shuffle(array) {
var copy = [],
n = array.length,
i;
while (n) {
i = Math.floor(Math.random() * n--);
copy.push(array.splice(i, 1)[0]);
}
return copy;
}
改進的做法就是處理完一個元素后，用Array的splice()方法將其從目標數組中移除，同時也更新了目標數組的長度。如此一來下次遍歷的時候是從新的長度開始，不會重復處理的情況了。
當然這樣的方案也有不足之處：比如，我們創建了一個copy數組進行返回，在內存上開辟了新的空間。
不過，這可以完全避免：
function shuffle(array) {
var m = array.length,
t, i;
while (m) {
i = Math.floor(Math.random() * m--);
t = array[m];
array[m] = array[i];
array[i] = t;
}
return array;
}
有趣的是，這樣的實現已經完全等同于上文洗牌算法Fisher–Yates shuffle的方案了。
總結本文剖析了“數組亂序”這么一個簡單，但是有趣的需求場景。
對這個場景的深入分析，讓我們認識到JS和計算機算法中的一些玄妙。
文章簡要提到了V8引擎對array.sort的處理、洗牌算法Fisher–Yates等內容。希望對讀者有所啟發。
Happy Coding!
PS: 作者Github倉庫，歡迎通過代碼各種形式交流。
百度知識搜索部大前端繼續招兵買馬，有意向者火速聯系。。。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/82482.html
摘要：比如元素大概率出現在數組的頭部，元素大概率出現在數組的尾部，所有元素大概率停留在自己初始位置。當目標數組長度小于時，使用插入排序反之，使用快排。而在排序算法中，大多數情況都不會滿足這樣的條件。 最近看了一篇非常有趣的文章：關于JavaScript的數組隨機排序，其作者為oldj前輩。文中指出我們用來將一個數組隨機排序的經典寫法所存在的問題，獲益匪淺。 本文將以更加詳盡的材料和更多樣的c...
摘要：毫無疑問，設計模式于己于他人于系統都是多贏的設計模式使代碼編寫真正工程化設計模小書前端掘金這是一本關于的小書。 JavaScript 常見設計模式解析 - 掘金設計模式（Design pattern）是一套被反復使用、多數人知曉的、經過分類編目的、代碼設計經驗的總結。使用設計模式是為了可重用代碼、讓代碼更容易被他人理解、保證代碼可靠性。毫無疑問，設計模式于己于他人于系統都是多贏的；設計...
摘要：并嘗試用為什么你統計的方式是錯的掘金翻譯自工程師的文章。正如你期望的，文中的前端開發單一職責原則前端掘金單一職責原則又稱單一功能原則，面向對象五個基本原則之一。 單頁式應用性能優化 - 首屏數據漸進式預加載 - 前端 - 掘金前言 針對首頁和部分頁面打開速度慢的問題，我們開始對單頁式應用性能進行優化。本文介紹其中一個方案：基于 HTTP Chunk 的首屏數據漸進式預加載方案，該方案總...
摘要：源碼地址為了簡化篇幅，我們對這個數組進行分析，數組長度為，此時采用的是插入排序。插入排序的源碼是其原理在于將第一個元素視為有序序列，遍歷數組，將之后的元素依次插入這個構建的有序序列中。 JavaScript 專題系列第十九篇，講解數組亂序，重點探究 Math.random() 為什么不能真正的亂序？ 亂序 亂序的意思就是將數組打亂。 嗯，沒有了，直接看代碼吧。 Math.random ...
閱讀 3391·2023-04-25 14:07
閱讀 3458·2021-09-28 09:35
閱讀 2091·2019-08-30 15:55
閱讀 1405·2019-08-30 13:48
閱讀 2502·2019-08-30 13:16
閱讀 3202·2019-08-30 12:54
閱讀 3238·2019-08-30 11:19
閱讀 1876·2019-08-29 17:17
