推薦閱讀:JavaScript學習筆記之數組的增、刪、改、查
JavaScript學習筆記之數組求和方法
JavaScript學習筆記之數組隨機排序
洗牌算法是一個比較形象的術語,本質上讓一個數組內的元素隨機排列。舉例來說,我們有一個如下圖所示的數組,數組長度為 9,數組內元素的值順次分別是 1~9:
從上面這個數組入手,我們要做的就是打亂數組內元素的順序:
代碼實現
維基百科上的 Fisher–Yates shuffle 詞條對洗牌算法做了詳細介紹,下面演示的算法也是基於其中的理論編寫的:
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);
在上面的代碼中,我們創建了一個 shffle() 方法,該方法用於隨機排列數組內的元素。此外,我們將該方法掛載在了 Array 對象的原型下面,所以任何數組都可以直接調用該方法:
var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] tempArray.shuffle();
工作原理
看完代碼之後,讓我們看看它對數組都做了寫什麼。首先,該方法選中數組的最後一個元素:
接下來確定挑選隨機元素的范圍,從數組的第一個元素到上一步選中的元素都屬於這一范圍:
確定范圍後,從中隨機挑選一個數,這裡假設隨機選中的元素為 4:
然後交換最後一個元素和隨機選中的元素的值:
上面的交換完成後,相當於我們完成了對數組最後一個元素的隨機處理。接下來選中數組內倒數第二的元素:
之所以從後往前處理,是因為這樣便於確定隨機選擇的范圍。這次我們假定隨機到的元素為 2:
接著交換倒數第一個元素和 2 號元素的值,完成對倒數第二個元素隨機排列的處理。然後是選中倒數第三個元素,重復之前的操作:
剩下的就是一些重復性的工作,不多做介紹了。
分析代碼
在上一節給各位用圖例演示了洗牌流程,下面我們從代碼本身看看洗牌流程。先從 shuffle 函數說起吧:
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 函數掛載在 Array 對象的原型之下,便於數組直接調用該函數。在 shuffle 函數內部,this 引用的就是調用該 shuffle 的數組:
var input = this;
在上面的代碼中,我用一個新的變量引用 this,也就是調用 shuffle 函數的數組。下一步,看一下 for 循環內都干了什麼:
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; }
該循環用於遍歷所有數組內的所有元素,並進行隨機交換。注意,遍歷順序是從後往前進行的,也就是說從 input.length-1 位置的元素開始,知道遍歷到數組中的第一個元素。遍歷過程中的位置由變量 i 指定。
這裡的變量 i 就是上面圖例中被選中的元素:
洗牌算法
接下來,使用了兩行代碼在指定范圍內挑選一個隨機元素:
var randomIndex = Math.floor(Math.random()*(i+1)); var itemAtIndex = input[randomIndex];
變量 randomIndex 存儲了一個隨機數,該隨機數可以用作數組的索引,進而提取一個隨機元素。注意,該隨機數的最大值並不是數組的長度,而是變量 i 的值。
確定了隨機元素的索引之後,用新的變量保存該元素的值,然後交換選中元素和隨機元素的值:
var itemAtIndex = input[randomIndex]; input[randomIndex] = input[i]; input[i] = itemAtIndex;
在這三行代碼中,第一行使用新的變量保存了隨機元素的值;第二行將選中元素 input[i] 的值賦給隨機元素 input[randomIndex];第三行就隨機元素的值 itemAtIndex 賦給選中元素 input[i]。本質上是一個互換兩個元素的值的過程,並不難理解。
至此,循環內的邏輯就介紹完了,剩下的都是重復操作。
隨機性測試
上圖是使用 Highcharts 制作的隨機性測試圖表,以可視化的方式校驗本文中洗牌算法的隨機性。每次刷新頁面都會重新計算和生成該圖表。
生成上圖的數據是這樣計算而來的:首先創建一個數組(上圖使用的數組為 [0, 1, 2 ... 18, 19, 20]),然後使用本文中的洗牌算法重新排序,排序完成後記錄每一個元素的值……以此步驟執行 100000 次,最後對同一索引位置上的數值進行求和。如此執行 10000 次之後,索引之間的總值應該相差不大。
由計算可得:
以上內容是小編給大家介紹的JS隨機洗牌算法之給數組隨機排序的相關敘述,希望對大家有所幫助!