Array.prototype.sort 方法被許多 JavaScript 程序員誤用來隨機排列數(shù)組。最近做的前端星計劃挑戰(zhàn)項目中，一道實現(xiàn) blackjack 游戲的問題，就發(fā)現(xiàn)很多同學使用了 Array.prototype.sort 來洗牌。

洗牌

以下就是常見的完全錯誤的隨機排列算法：

function shuffle(arr){
 return arr.sort(function(){
 return Math.random() - 0.5;
 });
}

以上代碼看似巧妙利用了 Array.prototype.sort 實現(xiàn)隨機，但是，卻有非常嚴重的問題，甚至是完全錯誤。

證明 Array.prototype.sort 隨機算法的錯誤

為了證明這個算法的錯誤，我們設(shè)計一個測試的方法。假定這個排序算法是正確的，那么，將這個算法用于隨機數(shù)組 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]，如果算法正確，那么每個數(shù)字在每一位出現(xiàn)的概率均等。因此，將數(shù)組重復(fù)洗牌足夠多次，然后將每次的結(jié)果在每一位相加，最后對每一位的結(jié)果取平均值，這個平均值應(yīng)該約等于 (0 + 9) / 2 = 4.5，測試次數(shù)越多次，每一位上的平均值就都應(yīng)該越接近于 4.5。所以我們簡單實現(xiàn)測試代碼如下：

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 瀏覽器中測試一下，可以得出結(jié)果，發(fā)現(xiàn)結(jié)果并不隨機分布，各個位置的平均值越往后越大，這意味著這種隨機算法越大的數(shù)字出現(xiàn)在越后面的概率越大。

為什么會產(chǎn)生這個結(jié)果呢？我們需要了解 Array.prototype.sort 究竟是怎么作用的。

首先我們知道排序算法有很多種，而 ECMAScript 并沒有規(guī)定 Array.prototype.sort 必須使用何種排序算法。

排序不是我們今天討論的主題，但是不論用何種排序算法，都是需要進行兩個數(shù)之間的比較和交換，排序算法的效率和兩個數(shù)之間比較和交換的次數(shù)有關(guān)系。

最基礎(chǔ)的排序有冒泡排序和插入排序，原版的冒泡或者插入排序都比較了 n(n-1)/2 次，也就是說任意兩個位置的元素都進行了一次比較。那么在這種情況下，如果采用前面的 sort 隨機算法，由于每次比較都有 50% 的幾率交換和不交換，這樣的結(jié)果是隨機均勻的嗎？我們可以看一下例子：

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);

上面的代碼的隨機結(jié)果也是不均勻的，測試平均值的結(jié)果越往后的越大。（筆者之前沒有復(fù)制原數(shù)組所以錯誤得出均勻的結(jié)論，已更正于 2016-05-10）

冒泡排序總是將比較結(jié)果較小的元素與它的前一個元素交換，我們可以大約思考一下，這個算法越后面的元素，交換到越前的位置的概率越?。ㄒ驗槊看沃挥?0%幾率“冒泡”），原始數(shù)組是順序從小到大排序的，因此測試平均值的結(jié)果自然就是越往后的越大（因為越靠后的大數(shù)出現(xiàn)在前面的概率越?。?。

我們再換一種算法，我們這一次用插入排序：

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);

由于插入排序找后面的大數(shù)與前面的數(shù)進行交換，這一次的結(jié)果和冒泡排序相反，測試平均值的結(jié)果自然就是越往后越小。原因也和上面類似，對于插入排序，越往后的數(shù)字越容易隨機交換到前面。

所以我們看到即使是兩兩交換的排序算法，隨機分布差別也是比較大。除了每個位置兩兩都比較一次的這種排序算法外，大多數(shù)排序算法的時間復(fù)雜度介于 O(n) 到 O(n2) 之間，元素之間的比較次數(shù)通常情況下要遠小于 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);

快速排序并沒有兩兩元素進行比較，它的概率分布也不隨機。

所以我們可以得出結(jié)論，用 Array.prototype.sort 隨機交換的方式來隨機排列數(shù)組，得到的結(jié)果并不一定隨機，而是取決于排序算法是如何實現(xiàn)的，用 JavaScript 內(nèi)置的排序算法這么排序，通?？隙ㄊ?strong>不完全隨機的。

經(jīng)典的隨機排列

所有空間復(fù)雜度 O(1) 的排序算法的時間復(fù)雜度都介于 O(nlogn) 到 O(n2) 之間，因此在不考慮算法結(jié)果錯誤的前提下，使用排序來隨機交換也是慢的。事實上，隨機排列數(shù)組元素有經(jīng)典的 O(n) 復(fù)雜度的算法：

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;
}

在上面的算法里，我們每一次循環(huán)從前 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);

從結(jié)果可以看出這個算法的隨機結(jié)果應(yīng)該是均勻的。不過我們的測試方法其實有個小小的問題，我們只測試了平均值，實際上平均值接近只是均勻分布的必要而非充分條件，平均值接近不一定就是均勻分布。不過別擔心，事實上我們可以簡單從數(shù)學上證明這個算法的隨機性。

隨機性的數(shù)學歸納法證明

對 n 個數(shù)進行隨機：

首先我們考慮 n = 2 的情況，根據(jù)算法，顯然有 1/2 的概率兩個數(shù)交換，有 1/2 的概率兩個數(shù)不交換，因此對 n = 2 的情況，元素出現(xiàn)在每個位置的概率都是 1/2，滿足隨機性要求。

假設(shè)有 i 個數(shù)， i >= 2 時，算法隨機性符合要求，即每個數(shù)出現(xiàn)在 i 個位置上每個位置的概率都是 1/i。

對于 i + 1 個數(shù)，按照我們的算法，在第一次循環(huán)時，每個數(shù)都有 1/(i+1) 的概率被交換到最末尾，所以每個元素出現(xiàn)在最末一位的概率都是 1/(i+1) 。而每個數(shù)也都有 i/(i+1) 的概率不被交換到最末尾，如果不被交換，從第二次循環(huán)開始還原成 i 個數(shù)隨機，根據(jù) 2. 的假設(shè)，它們出現(xiàn)在 i 個位置的概率是 1/i。因此每個數(shù)出現(xiàn)在前 i 位任意一位的概率是 (i/(i+1)) * (1/i) = 1/(i+1)，也是 1/(i+1)。

綜合 1. 2. 3. 得出，對于任意 n >= 2，經(jīng)過這個算法，每個元素出現(xiàn)在 n 個位置任意一個位置的概率都是 1/n。

總結(jié)

一個優(yōu)秀的算法要同時滿足結(jié)果正確和高效率。很不幸使用 Array.prototype.sort 方法這兩個條件都不滿足。因此，當我們需要實現(xiàn)類似洗牌的功能的時候，還是應(yīng)該采用巧妙的經(jīng)典洗牌算法，它不僅僅具有完全隨機性還有很高的效率。

除了收獲這樣的算法之外，我們還應(yīng)該認真對待這種動手分析和解決問題的思路，并且撿起我們曾經(jīng)學過而被大多數(shù)人遺忘的數(shù)學（比如數(shù)學歸納法這種經(jīng)典的證明方法）。

有任何問題歡迎與作者探討~

以上就是本文的全部內(nèi)容，希望本文的內(nèi)容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持腳本之家！

最新評論