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

洗牌

以下就是常見的完全錯(cuò)誤的隨機(jī)排列算法：

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

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

證明 Array.prototype.sort 隨機(jī)算法的錯(cuò)誤

為了證明這個(gè)算法的錯(cuò)誤，我們設(shè)計(jì)一個(gè)測試的方法。假定這個(gè)排序算法是正確的，那么，將這個(gè)算法用于隨機(jī)數(shù)組 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]，如果算法正確，那么每個(gè)數(shù)字在每一位出現(xiàn)的概率均等。因此，將數(shù)組重復(fù)洗牌足夠多次，然后將每次的結(jié)果在每一位相加，最后對每一位的結(jié)果取平均值，這個(gè)平均值應(yīng)該約等于 (0 + 9) / 2 = 4.5，測試次數(shù)越多次，每一位上的平均值就都應(yīng)該越接近于 4.5。所以我們簡單實(shí)現(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é)果并不隨機(jī)分布，各個(gè)位置的平均值越往后越大，這意味著這種隨機(jī)算法越大的數(shù)字出現(xiàn)在越后面的概率越大。

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

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

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

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

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

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

冒泡排序總是將比較結(jié)果較小的元素與它的前一個(gè)元素交換，我們可以大約思考一下，這個(gè)算法越后面的元素，交換到越前的位置的概率越?。ㄒ?yàn)槊看沃挥?0%幾率“冒泡”），原始數(shù)組是順序從小到大排序的，因此測試平均值的結(jié)果自然就是越往后的越大（因?yàn)樵娇亢蟮拇髷?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ù)進(jìn)行交換，這一次的結(jié)果和冒泡排序相反，測試平均值的結(jié)果自然就是越往后越小。原因也和上面類似，對于插入排序，越往后的數(shù)字越容易隨機(jī)交換到前面。

所以我們看到即使是兩兩交換的排序算法，隨機(jī)分布差別也是比較大。除了每個(gè)位置兩兩都比較一次的這種排序算法外，大多數(shù)排序算法的時(shí)間復(fù)雜度介于 O(n) 到 O(n2) 之間，元素之間的比較次數(shù)通常情況下要遠(yuǎn)小于 n(n-1)/2，也就意味著有一些元素之間根本就沒機(jī)會(huì)相比較（也就沒有了隨機(jī)交換的可能），這些 sort 隨機(jī)排序的算法自然也不能真正隨機(jī)。

我們將上面的代碼改一下，采用快速排序：

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

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

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

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

所有空間復(fù)雜度 O(1) 的排序算法的時(shí)間復(fù)雜度都介于 O(nlogn) 到 O(n2) 之間，因此在不考慮算法結(jié)果錯(cuò)誤的前提下，使用排序來隨機(jī)交換也是慢的。事實(shí)上，隨機(jī)排列數(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 個(gè)元素里隨機(jī)一個(gè)位置，將這個(gè)元素和第 len - i 個(gè)元素進(jìn)行交換，迭代直到 i = len - 1 為止。

我們同樣可以檢驗(yàn)一下這個(gè)算法的隨機(jī)性：

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

隨機(jī)性的數(shù)學(xué)歸納法證明

對 n 個(gè)數(shù)進(jìn)行隨機(jī)：

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

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

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

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

總結(jié)

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

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

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

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

最新評論