Range

Roll

Scratch

Result

1 - 8

3

1 2 3 4 5 6 7 8

3

現在我們從 1 ~ 6 選擇下一個隨機數，然後從 1 ~ 5 選擇依此類推，總是重複上述過程：

Richard Durstenfeld 於 1964 年推出了現代版本的 Fisher–Yates shuffle，並由 Donald E. Knuth 在 The Art of Computer Programming 以 “Algorithm P (Shuffling)” 進行了推廣。Durstenfeld 所描述的演算法與 Fisher 和 Yates 所給出的演算法有很小的差異，但意義重大。

-- To shuffle an array a of n elements (indices 0..n-1):  for i from n−1 downto 1 do  // 陣列從 n-1 到 0 迴圈執行 n 次  j ← random integer such that 0 ≤ j ≤ i  // 生成一個 0 到 n-1 之間的隨機索引  exchange a[j] and a[i] // 將交換之後剩餘的序列中最後一個元素與隨機選取的元素交換

Durstenfeld 的解決方案是將“刪除”的數字移至陣列末尾，即將每個被刪除數字與最後一個未刪除的數字進行交換。

實現

// ES6 寫法function shuffle(arr) {  let i = arr.length  while (--i) {    let j = Math.floor(Math.random() * i)    ;[arr[j], arr[i]] = [arr[i], arr[j]]  }  return arr}// ES5 寫法function shuffle(arr) {  var i = arr.length  var j  var t  while (--i) {    j = Math.floor(Math.random() * i)    t = arr[i]    arr[i] = arr[j]    arr[j] = t  }    return arr}

Knuth-Durstenfeld Shuffle 將演算法的時間複雜度降低到 O(n)，而 Fisher–Yates shuffle 的時間複雜度為 O(n2)。後者在計算機實現過程中，將花費不必要的時間來計算每次剩餘的數字（可以理解成陣列長度）。

舉例

同樣，假設我們有 1 ~ 8 的數字

表格每列分別表示：範圍、當前隨機數（即隨機互動的位置）、剩餘未交換的數、已隨機排列的數。

我們從 1 ~ 8 中隨機選擇一個數，得到隨機數 k 為 6，然後交換 Scratch 中的第 6 和第 8 個數字：

接著，從 1 ~ 7 中隨機選擇一個數，得到隨機數 k 為 2，然後交換 Scratch 中的第 2 和第 7 個數字：

繼續，下一個隨機數是1 ~ 6，得到的隨機數恰好是 6，這意味著我們將列表中的第 6 個數字保留下來（經過上面的交換，現在是 8），然後移到下一個步。同樣，我們以相同的方式進行操作，直到完成排列：

因此，結果是 7 5 4 3 1 8 2 6。

若要實現隨機打亂陣列的需求，就不要再使用 arr.sort(() => Math.random() - 0.5) 這種方法了。目前用得較多的是 Knuth-Durstenfeld Shuffle 演算法。