資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究什麼是 JavaScript 中的 Fisher-Yates 洗牌演算法？
給定一個數組，生成陣列元素的隨機排列。這類似於洗牌或隨機化一個數組，並且洗牌後每次的結果都應該相同且等機率出現。
輸入輸出場景
假設一個數組包含一些元素，並且我們對該陣列進行了 Fisher-Yates 洗牌。輸出陣列將被隨機洗牌，每次執行都會進行不同的洗牌。所有排列都是等機率的。
Input = [2, 4, 6, 8, 10]
Output = 4, 10, 6, 2, 8 // first iteration
8, 10, 2, 6, 4 // second iteration
2, 10, 8, 6, 4 // third iteration
考慮一個 arr[] 陣列。一種更簡單的解決方法是建立一個最初是 arr[] 陣列副本的 temp[] 陣列。從 temp[] 中隨機選擇一個元素，並將此元素複製到 arr[0]，然後刪除 temp[] 中的元素。重複此過程，直到從 temp[] 中隨機選擇每個元素並將其移動到 arr[]。
演算法
該演算法反覆執行將陣列中隨機選擇的元素與陣列中最後一個元素交換的操作。
以下是洗牌陣列的步驟：
在給定陣列的第一個索引和最後一個索引之間選擇一個隨機索引號。
現在，將該元素與最後一個索引元素交換。
重複步驟一，但將該元素排除在選擇之外。
當隨機選擇中只剩下第一個索引時，停止洗牌。
每次都重複步驟一，並且前一次隨機選擇的最後一個索引應從選擇中排除。
以下是 Fisher-Yates 陣列洗牌的工作原理：
為了瞭解 Fisher-Yates 陣列洗牌的工作原理，讓我們假設一個數組 arr=[10, 20, 30, 40, 50]。
從第一個索引 arr[0] 和最後一個索引位置 arr[4] 中，隨機選擇 30 並交換 30 和 50。
從第一個索引 arr[0] 和最後一個索引位置 arr[3]（排除之前的選擇）。
隨機選擇 20 並交換 20 和 40。
從第一個索引 arr[0] 到最後一個索引位置 arr[2]（排除之前的選擇）。
隨機選擇 30，不會發生交換，因為隨機選擇的索引不在 arr[0] 和 arr[2] 之間。
從第一個索引 arr[0] 到最後一個索引位置 arr[1]（排除之前的選擇）。
隨機選擇 10 並交換 10 和 40。
洗牌後的最終陣列如下面的圖片所示。(此處應插入圖片)
示例 1
在下面的示例中，我們建立了一個包含元素的陣列。還建立了一個 while 迴圈，只要陣列長度大於 0，迴圈就會執行。
每次 while 迴圈重複時，Array.length 都會遞減 1，並且一旦交換，最後一個索引就會從迴圈中刪除。
元素將在 temp 和 i 之間交換。當 while 迴圈迭代所有可能性時，它將列印輸出。每次再次執行程式時，輸出都會有所不同。
<!DOCTYPE html> <html> <title>Fisher-Yates shuffle in JavaScript</title> <head> <button onClick = "fisher_yates()"> Fisher Yates</button> <p id = "para"></p> <script> function fisher_yates(){ let array = [40, 90, 50, 70, 80, 30, 60, 10, 20]; let i = array.length; while (--i > 0) { let temp = Math.floor(Math.random() * (i + 1)); [array[temp], array[i]] = [array[i], array[temp]]; } document.getElementById("para").innerHTML = array; }; </script> </head> <body> </body> </html>
示例 2
在下面的示例中，我們建立了一個包含元素的陣列。還建立了一個 for 迴圈，只要陣列長度大於 0，迴圈就會執行。
陣列長度每次 for 迴圈重複時都會遞減 1，並且一旦交換，最後一個索引就會從迴圈中刪除。
我們還建立了一個按鈕並在其中傳遞了 fy() 函式。每當單擊按鈕時，迴圈就會再次開始執行，並且每次單擊時都會列印洗牌後的陣列。
<!DOCTYPE html> <html> <body> <button onclick="fy()">Try Fisher-Yates</button> <p id="para"></p> <script> let Array = [25,1,5,10,40,100]; let len = Array.length; let x; function fy() { for (x = len -1; x > 0; x--) { var y = Math.floor(Math.random() * x) var temp = Array[x] Array[x] = Array[y] Array[y] = temp } document.getElementById("para").innerHTML = Array; }; </script> </body> </html>
5000+ 次瀏覽
