要把 ['a','b','c','d'] 隨機打亂順序,網路上流傳最廣的寫法是這個:
function RandomSort(a, b) {
return 0.5 - Math.random();
}
// arr.sort(RandomSort);
看起來很聰明,實際上分佈並不均勻。原因是 sort 需要一個「一致的比較結果」才能收斂,而每次呼叫都回傳隨機值,等於給排序演算法一份自相矛盾的輸入,某些排列出現的機率會明顯高於其他。元素一多,偏差還會被放大。
它的思路非常樸素:從後往前,每一格都跟「它自己或它前面的某一格」交換。這樣每個元素落到每個位置的概率都恰好是 1/n。
/* jshint -W054 */
(function (exports) {
'use strict';
// Fisher–Yates (Knuth) shuffle
function shuffle(array) {
var currentIndex = array.length, temporaryValue, randomIndex;
// 只要還有元素沒處理完
while (currentIndex !== 0) {
// 從剩餘的 0 ~ currentIndex-1 中挑一個
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
// 跟目前這格交換
temporaryValue = array[currentIndex];
array[currentIndex] = array[randomIndex];
array[randomIndex] = temporaryValue;
}
return array;
}
exports.knuthShuffle = shuffle;
}('undefined' !== typeof exports && exports
|| 'undefined' !== typeof window && window || global));
瀏覽器端用法(注意 shuffle 會直接改動原陣列,想保留原樣要先 slice 一份):
(function () {
'use strict';
var a = [2, 11, 37, 42], b;
// a.slice(0) 產生副本, shuffle 只動副本
b = window.knuthShuffle(a.slice(0));
console.log(b); // 例如 [37, 2, 42, 11]
console.log(a); // [2, 11, 37, 42] 不變
}());
Node.js 則透過 npm 安裝:
npm install -S knuth-shuffle
(function () {
'use strict';
var shuffle = require('knuth-shuffle').knuthShuffle;
var a = [2, 11, 37, 42];
var b = shuffle(a.slice(0));
console.log(b);
}());
倒數 for 迴圈版(Durstenfeld 寫法,最容易記):
/**
* 原地隨機重排陣列,使用 Durstenfeld 洗牌演算法
*/
function shuffleArray(array) {
for (var i = array.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1));
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}
ES2015 解構賦值版,省掉暫存變數:
Array.prototype.shuffle = function () {
let m = this.length, i;
while (m) {
i = (Math.random() * m--) >>> 0;
[this[m], this[i]] = [this[i], this[m]];
}
return this;
};
[1, 2, 3, 4, 5, 6, 7].shuffle();
不過擴充原型這件事最好避免,它會污染全域、也可能與其他函式庫衝突。改成獨立函式更安全:
function shuffle(arr) {
const result = arr.slice();
for (let i = result.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[result[i], result[j]] = [result[j], result[i]];
}
return result; // 不回傳原陣列,改動可控
}
中文搜尋「隨機演算法」會跑出大量 sort 變體,但均勻性、效率與相容性都經不起檢驗。需要打亂陣列時,直接用 Fisher–Yates 就對了;若你的場景是抽樣(例如抽獎、隨機出題),下一則的 getRandomArrayElements 是更省成本的寫法。