作為一個前端吕晌，在開發(fā)過程中有時會遇到要將一個數組隨機排序（shuffle）的需求，一個常見的寫法是這樣:
function shuffle(arr) {
arr.sort(function () {
return Math.random() - 0.5;
});
}
或者使用更簡潔的 ES6 的寫法：
function shuffle(arr) {
arr.sort(() => Math.random() - 0.5);
}
我也曾經經常使用這種寫法临燃，不久前才意識到睛驳，這種寫法是有問題的，它并不能真正地隨機打亂數組谬俄。
具體是什么問題，看下面：
看下面的代碼弃理，我們生成一個長度為 10 的數組['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']溃论，使用上面的方法將數組亂序，執(zhí)行多次后痘昌，會發(fā)現每個元素仍然有很大機率在它原來的位置附近出現钥勋。
let n = 10000;
let count = (new Array(10)).fill(0);
for (let i = 0; i < n; i ++) {
let arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'];
arr.sort(() => Math.random() - 0.5);
count[arr.indexOf('a')]++;
}
console.log(count);
如果排序真的是隨機的，那么每個元素在每個位置出現的概率都應該一樣辆苔，實驗結果各個位置的數字應該很接近算灸，而不應像現在這樣明顯地集中在原來位置附近。因此驻啤，我們可以認為菲驴，使用形如arr.sort(() => Math.random() - 0.5)這樣的方法得到的并不是真正的隨機排序。
另外骑冗，需要注意的是上面的分布僅適用于數組長度不超過 10 的情況赊瞬，如果數組更長，比如長度為 11，則會是另一種分布。比如：
let a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']; // 長度為11
let n = 10000;
let count = (new Array(a.length)).fill(0);
for (let i = 0; i < n; i ++) {
let arr = [].concat(a);
arr.sort(() => Math.random() - 0.5);
count[arr.indexOf('a')]++;
}
console.log(count);
探索
看了一下ECMAScript中關于Array.prototype.sort(comparefn)的標準基跑，其中并沒有規(guī)定具體的實現算法峦阁，但是提到一點：
Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments.
也就是說，對同一組a退渗、b的值，comparefn(a, b)需要總是返回相同的值。而上面的() => Math.random() - 0.5（即(a, b) => Math.random() - 0.5）顯然不滿足這個條件缩筛。
翻看v8引擎數組部分的源碼，注意到它出于對性能的考慮堡称，對短數組使用的是插入排序歪脏，對長數組則使用了快速排序，至此粮呢，也就能理解為什么() => Math.random() - 0.5并不能真正隨機打亂數組排序了婿失。（有一個沒明白的地方：源碼中說的是對長度小于等于 22 的使用插入排序钞艇，大于 22 的使用快排，但實際測試結果顯示分界長度是 10豪硅。）
解決方案
知道問題所在哩照，解決方案也就比較簡單了懒浮。
方案一
既然(a, b) => Math.random() - 0.5的問題是不能保證針對同一組a飘弧、b每次返回的值相同砚著，那么我們不妨將數組元素改造一下，比如將每個元素i改造為：
let new_i = {
v: i,
r: Math.random()
};
即將它改造為一個對象稽穆，原來的值存儲在鍵v中，同時給它增加一個鍵r舌镶，值為一個隨機數，然后排序時比較這個隨機數：
arr.sort((a, b) => a.r - b.r);
完整代碼如下：
function shuffle(arr) {
let new_arr = arr.map(i => ({v: i, r: Math.random()}));
new_arr.sort((a, b) => a.r - b.r);
arr.splice(0, arr.length, ...new_arr.map(i => i.v));
}
let a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'];
let n = 10000;
let count = (new Array(a.length)).fill(0);
for (let i = 0; i < n; i ++) {
shuffle(a);
count[a.indexOf('a')]++;
}
console.log(count);
方案二（Fisher–Yates shuffle）
需要注意的是餐胀，上面的方法雖然滿足隨機性要求了，但在性能上并不是很好否灾，需要遍歷幾次數組，還要對數組進行splice等操作墨技。
考察Lodash 庫中的 shuffle 算法磨镶，注意到它使用的實際上是Fisher–Yates 洗牌算法琳猫，這個算法由 Ronald Fisher 和 Frank Yates 于 1938 年提出，然后在 1964 年由 Richard Durstenfeld 改編為適用于電腦編程的版本私痹。用偽代碼描述如下：
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n?1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
一個實現如下（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]];
}
}
或者對應的 ES5 版本：
function shuffle(arr) {
var i = arr.length, t, j;
while (i) {
j = Math.floor(Math.random() * i--);
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
因為有的同學直接看代碼可能會有些困難脐嫂，所以在這里重新給大家講解一下
首先我們有一個已經排好序的數組：
Step1：
第一步需要做的就是，從數組末尾開始紊遵，選取最后一個元素账千。
在數組一共9個位置中，隨機產生一個位置暗膜，該位置元素與最后一個元素進行交換匀奏。
Step2：
上一步中，我們已經把數組末尾元素進行隨機置換学搜。
接下來娃善，對數組倒數第二個元素動手论衍。在除去已經排好的最后一個元素位置以外的8個位置中，隨機產生一個位置聚磺，該位置元素與倒數第二個元素進行交換坯台。
Step3：
理解了前兩部，接下來就是依次進行瘫寝，如此簡單蜒蕾。
小結
如果要將數組隨機排序，千萬不要再用(a, b) => Math.random() - 0.5這樣的方法焕阿。目前而言咪啡，Fisher–Yates shuffle 算法應該是最好的選擇。
