推薦閱讀：JavaScript學(xué)習(xí)筆記之?dāng)?shù)組的增、刪、改、查

JavaScript學(xué)習(xí)筆記之?dāng)?shù)組求和方法

JavaScript學(xué)習(xí)筆記之?dāng)?shù)組隨機(jī)排序

洗牌算法是一個(gè)比較形象的術(shù)語(yǔ)，本質(zhì)上讓一個(gè)數(shù)組內(nèi)的元素隨機(jī)排列。舉例來(lái)說(shuō)，我們有一個(gè)如下圖所示的數(shù)組，數(shù)組長(zhǎng)度為 9，數(shù)組內(nèi)元素的值順次分別是 1~9：

從上面這個(gè)數(shù)組入手，我們要做的就是打亂數(shù)組內(nèi)元素的順序：

代碼實(shí)現(xiàn)

維基百科上的 Fisher–Yates shuffle 詞條對(duì)洗牌算法做了詳細(xì)介紹，下面演示的算法也是基于其中的理論編寫的：

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();
// and the result is...
alert(tempArray); 

在上面的代碼中，我們創(chuàng)建了一個(gè) shffle() 方法，該方法用于隨機(jī)排列數(shù)組內(nèi)的元素。此外，我們將該方法掛載在了 Array 對(duì)象的原型下面，所以任何數(shù)組都可以直接調(diào)用該方法：

var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle(); 

工作原理

看完代碼之后，讓我們看看它對(duì)數(shù)組都做了寫什么。首先，該方法選中數(shù)組的最后一個(gè)元素：

接下來(lái)確定挑選隨機(jī)元素的范圍，從數(shù)組的第一個(gè)元素到上一步選中的元素都屬于這一范圍：

確定范圍后，從中隨機(jī)挑選一個(gè)數(shù)，這里假設(shè)隨機(jī)選中的元素為 4：

然后交換最后一個(gè)元素和隨機(jī)選中的元素的值：

上面的交換完成后，相當(dāng)于我們完成了對(duì)數(shù)組最后一個(gè)元素的隨機(jī)處理。接下來(lái)選中數(shù)組內(nèi)倒數(shù)第二的元素：

之所以從后往前處理，是因?yàn)檫@樣便于確定隨機(jī)選擇的范圍。這次我們假定隨機(jī)到的元素為 2:

接著交換倒數(shù)第一個(gè)元素和 2 號(hào)元素的值，完成對(duì)倒數(shù)第二個(gè)元素隨機(jī)排列的處理。然后是選中倒數(shù)第三個(gè)元素，重復(fù)之前的操作：

剩下的就是一些重復(fù)性的工作，不多做介紹了。

分析代碼

在上一節(jié)給各位用圖例演示了洗牌流程，下面我們從代碼本身看看洗牌流程。先從 shuffle 函數(shù)說(shuō)起吧：

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

shuffle 函數(shù)掛載在 Array 對(duì)象的原型之下，便于數(shù)組直接調(diào)用該函數(shù)。在 shuffle 函數(shù)內(nèi)部，this 引用的就是調(diào)用該 shuffle 的數(shù)組：

var input = this;

在上面的代碼中，我用一個(gè)新的變量引用 this，也就是調(diào)用 shuffle 函數(shù)的數(shù)組。下一步，看一下 for 循環(huán)內(nèi)都干了什么：

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

該循環(huán)用于遍歷所有數(shù)組內(nèi)的所有元素，并進(jìn)行隨機(jī)交換。注意，遍歷順序是從后往前進(jìn)行的，也就是說(shuō)從 input.length-1 位置的元素開始，知道遍歷到數(shù)組中的第一個(gè)元素。遍歷過(guò)程中的位置由變量 i 指定。

這里的變量 i 就是上面圖例中被選中的元素：

洗牌算法

接下來(lái)，使用了兩行代碼在指定范圍內(nèi)挑選一個(gè)隨機(jī)元素：

var randomIndex = Math.floor(Math.random()*(i+1)); 
var itemAtIndex = input[randomIndex];

變量 randomIndex 存儲(chǔ)了一個(gè)隨機(jī)數(shù)，該隨機(jī)數(shù)可以用作數(shù)組的索引，進(jìn)而提取一個(gè)隨機(jī)元素。注意，該隨機(jī)數(shù)的最大值并不是數(shù)組的長(zhǎng)度，而是變量 i 的值。

確定了隨機(jī)元素的索引之后，用新的變量保存該元素的值，然后交換選中元素和隨機(jī)元素的值：

var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i]; 
input[i] = itemAtIndex;

在這三行代碼中，第一行使用新的變量保存了隨機(jī)元素的值；第二行將選中元素 input[i] 的值賦給隨機(jī)元素 input[randomIndex]；第三行就隨機(jī)元素的值 itemAtIndex 賦給選中元素 input[i]。本質(zhì)上是一個(gè)互換兩個(gè)元素的值的過(guò)程，并不難理解。

至此，循環(huán)內(nèi)的邏輯就介紹完了，剩下的都是重復(fù)操作。

隨機(jī)性測(cè)試

上圖是使用 Highcharts 制作的隨機(jī)性測(cè)試圖表，以可視化的方式校驗(yàn)本文中洗牌算法的隨機(jī)性。每次刷新頁(yè)面都會(huì)重新計(jì)算和生成該圖表。

生成上圖的數(shù)據(jù)是這樣計(jì)算而來(lái)的：首先創(chuàng)建一個(gè)數(shù)組（上圖使用的數(shù)組為 [0, 1, 2 ... 18, 19, 20]），然后使用本文中的洗牌算法重新排序，排序完成后記錄每一個(gè)元素的值……以此步驟執(zhí)行 100000 次，最后對(duì)同一索引位置上的數(shù)值進(jìn)行求和。如此執(zhí)行 10000 次之后，索引之間的總值應(yīng)該相差不大。

由計(jì)算可得：

以上內(nèi)容是小編給大家介紹的JS隨機(jī)洗牌算法之給數(shù)組隨機(jī)排序的相關(guān)敘述，希望對(duì)大家有所幫助！

最新評(píng)論