JS隨機洗牌演算法之數組隨機排序_javascript技巧

推薦閱讀：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随机洗牌算法之给数组随机排序的相关叙述，希望对大家有所帮助！