Array.prototype.sort 方法被許多 JavaScript 程序員誤用來隨機排列數組。最近做的前端星計劃挑戰項目中，一道實現 blackjack 游戲的問題，就發現很多同學使用了 Array.prototype.sort 來洗牌。
洗牌
以下就是常見的完全錯誤的隨機排列算法：
function shuffle(arr){
return arr.sort(function(){
return Math.random() - 0.5;
});
}
以上代碼看似巧妙利用了 Array.prototype.sort 實現隨機，但是，卻有非常嚴重的問題，甚至是完全錯誤。
證明 Array.prototype.sort 隨機算法的錯誤
為了證明這個算法的錯誤，我們設計一個測試的方法。假定這個排序算法是正確的，那麼，將這個算法用於隨機數組 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]，如果算法正確，那麼每個數字在每一位出現的概率均等。因此，將數組重復洗牌足夠多次，然後將每次的結果在每一位相加，最後對每一位的結果取平均值，這個平均值應該約等於 (0 + 9) / 2 = 4.5，測試次數越多次，每一位上的平均值就都應該越接近於 4.5。所以我們簡單實現測試代碼如下：
var arr = [0,1,2,3,4,5,6,7,8,9];
var res = [0,0,0,0,0,0,0,0,0,0];
var t = 10000;
for(var i = 0; i < t; i++){
var sorted = shuffle(arr.slice(0));
sorted.forEach(function(o,i){
res[i] += o;
});
}
res = res.map(function(o){
return o / t;
});
console.log(res);
將上面的 shuffle 方法用這段測試代碼在 chrome 浏覽器中測試一下，可以得出結果，發現結果並不隨機分布，各個位置的平均值越往後越大，這意味著這種隨機算法越大的數字出現在越後面的概率越大。
為什麼會產生這個結果呢？我們需要了解 Array.prototype.sort 究竟是怎麼作用的。
首先我們知道排序算法有很多種，而 ECMAScript 並沒有規定 Array.prototype.sort 必須使用何種排序算法。
排序不是我們今天討論的主題，但是不論用何種排序算法，都是需要進行兩個數之間的比較和交換，排序算法的效率和兩個數之間比較和交換的次數有關系。
最基礎的排序有冒泡排序和插入排序，原版的冒泡或者插入排序都比較了 n(n-1)/2 次，也就是說任意兩個位置的元素都進行了一次比較。那麼在這種情況下，如果采用前面的 sort 隨機算法，由於每次比較都有 50% 的幾率交換和不交換，這樣的結果是隨機均勻的嗎？我們可以看一下例子：
function bubbleSort(arr, compare){
var len = arr.length;
for(var i = 0; i < len - 1; i++){
for(var j = 0; j < len - 1 - i; j++){
var k = j + 1;
if(compare(arr[j], arr[k]) > 0){
var tmp = arr[j];
arr[j] = arr[k];
arr[k] = tmp;
}
}
}
return arr;
}
function shuffle(arr){
return bubbleSort(arr, function(){
return Math.random() - 0.5;
});
}
var arr = [0,1,2,3,4,5,6,7,8,9];
var res = [0,0,0,0,0,0,0,0,0,0];
var t = 10000;
for(var i = 0; i < t; i++){
var sorted = shuffle(arr.slice(0));
sorted.forEach(function(o,i){
res[i] += o;
});
}
res = res.map(function(o){
return o / t;
});
console.log(res);
上面的代碼的隨機結果也是不均勻的，測試平均值的結果越往後的越大。（筆者之前沒有復制原數組所以錯誤得出均勻的結論，已更正於 2016-05-10）
冒泡排序總是將比較結果較小的元素與它的前一個元素交換，我們可以大約思考一下，這個算法越後面的元素，交換到越前的位置的概率越小（因為每次只有50%幾率“冒泡”），原始數組是順序從小到大排序的，因此測試平均值的結果自然就是越往後的越大（因為越靠後的大數出現在前面的概率越小）。
我們再換一種算法，我們這一次用插入排序：
function insertionSort(arr, compare){
var len = arr.length;
for(var i = 0; i < len; i++){
for(var j = i + 1; j < len; j++){
if(compare(arr[i], arr[j]) > 0){
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
return arr;
}
function shuffle(arr){
return insertionSort(arr, function(){
return Math.random() - 0.5;
});
}
var arr = [0,1,2,3,4,5,6,7,8,9];
var res = [0,0,0,0,0,0,0,0,0,0];
var t = 10000;
for(var i = 0; i < t; i++){
var sorted = shuffle(arr.slice(0));
sorted.forEach(function(o,i){
res[i] += o;
});
}
res = res.map(function(o){
return o / t;
});
console.log(res);
由於插入排序找後面的大數與前面的數進行交換，這一次的結果和冒泡排序相反，測試平均值的結果自然就是越往後越小。原因也和上面類似，對於插入排序，越往後的數字越容易隨機交換到前面。
所以我們看到即使是兩兩交換的排序算法，隨機分布差別也是比較大。除了每個位置兩兩都比較一次的這種排序算法外，大多數排序算法的時間復雜度介於 O(n) 到 O(n2) 之間，元素之間的比較次數通常情況下要遠小於 n(n-1)/2，也就意味著有一些元素之間根本就沒機會相比較（也就沒有了隨機交換的可能），這些 sort 隨機排序的算法自然也不能真正隨機。
我們將上面的代碼改一下，采用快速排序：
function quickSort(arr, compare){
arr = arr.slice(0);
if(arr.length <= 1) return arr;
var mid = arr[0], rest = arr.slice(1);
var left = [], right = [];
for(var i = 0; i < rest.length; i++){
if(compare(rest[i], mid) > 0){
right.push(rest[i]);
}else{
left.push(rest[i]);
}
}
return quickSort(left, compare).concat([mid])
.concat(quickSort(right, compare));
}
function shuffle(arr){
return quickSort(arr, function(){
return Math.random() - 0.5;
});
}
var arr = [0,1,2,3,4,5,6,7,8,9];
var res = [0,0,0,0,0,0,0,0,0,0];
var t = 10000;
for(var i = 0; i < t; i++){
var sorted = shuffle(arr.slice(0));
sorted.forEach(function(o,i){
res[i] += o;
});
}
res = res.map(function(o){
return o / t;
});
console.log(res);
快速排序並沒有兩兩元素進行比較，它的概率分布也不隨機。
所以我們可以得出結論，用 Array.prototype.sort 隨機交換的方式來隨機排列數組，得到的結果並不一定隨機，而是取決於排序算法是如何實現的，用 JavaScript 內置的排序算法這麼排序，通常肯定是不完全隨機的。
經典的隨機排列
所有空間復雜度 O(1) 的排序算法的時間復雜度都介於 O(nlogn) 到 O(n2) 之間，因此在不考慮算法結果錯誤的前提下，使用排序來隨機交換也是慢的。事實上，隨機排列數組元素有經典的 O(n) 復雜度的算法：
function shuffle(arr){
var len = arr.length;
for(var i = 0; i < len - 1; i++){
var idx = Math.floor(Math.random() * (len - i));
var temp = arr[idx];
arr[idx] = arr[len - i - 1];
arr[len - i -1] = temp;
}
return arr;
}
在上面的算法裡，我們每一次循環從前 len - i 個元素裡隨機一個位置，將這個元素和第 len - i 個元素進行交換，迭代直到 i = len - 1 為止。
我們同樣可以檢驗一下這個算法的隨機性：
function shuffle(arr){
var len = arr.length;
for(var i = 0; i < len - 1; i++){
var idx = Math.floor(Math.random() * (len - i));
var temp = arr[idx];
arr[idx] = arr[len - i - 1];
arr[len - i -1] = temp;
}
return arr;
}
var arr = [0,1,2,3,4,5,6,7,8,9];
var res = [0,0,0,0,0,0,0,0,0,0];
var t = 10000;
for(var i = 0; i < t; i++){
var sorted = shuffle(arr.slice(0));
sorted.forEach(function(o,i){
res[i] += o;
});
}
res = res.map(function(o){
return o / t;
});
console.log(res);
從結果可以看出這個算法的隨機結果應該是均勻的。不過我們的測試方法其實有個小小的問題，我們只測試了平均值，實際上平均值接近只是均勻分布的必要而非充分條件，平均值接近不一定就是均勻分布。不過別擔心，事實上我們可以簡單從數學上證明這個算法的隨機性。
隨機性的數學歸納法證明
對 n 個數進行隨機：
首先我們考慮 n = 2 的情況，根據算法，顯然有 1/2 的概率兩個數交換，有 1/2 的概率兩個數不交換，因此對 n = 2 的情況，元素出現在每個位置的概率都是 1/2，滿足隨機性要求。
假設有 i 個數， i >= 2 時，算法隨機性符合要求，即每個數出現在 i 個位置上每個位置的概率都是 1/i。
對於 i + 1 個數，按照我們的算法，在第一次循環時，每個數都有 1/(i+1) 的概率被交換到最末尾，所以每個元素出現在最末一位的概率都是 1/(i+1) 。而每個數也都有 i/(i+1) 的概率不被交換到最末尾，如果不被交換，從第二次循環開始還原成 i 個數隨機，根據 2. 的假設，它們出現在 i 個位置的概率是 1/i。因此每個數出現在前 i 位任意一位的概率是 (i/(i+1)) * (1/i) = 1/(i+1)，也是 1/(i+1)。
綜合 1. 2. 3. 得出，對於任意 n >= 2，經過這個算法，每個元素出現在 n 個位置任意一個位置的概率都是 1/n。
總結
一個優秀的算法要同時滿足結果正確和高效率。很不幸使用 Array.prototype.sort 方法這兩個條件都不滿足。因此，當我們需要實現類似洗牌的功能的時候，還是應該采用巧妙的經典洗牌算法，它不僅僅具有完全隨機性還有很高的效率。
除了收獲這樣的算法之外，我們還應該認真對待這種動手分析和解決問題的思路，並且撿起我們曾經學過而被大多數人遺忘的數學（比如數學歸納法這種經典的證明方法）。
有任何問題歡迎與作者探討~
以上就是本文的全部內容，希望本文的內容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持！