詳解js數組的完全隨機排列算法

更新時間：2016年12月16日 10:51:09 作者：十年蹤跡的博客

本文主要對常見的完全錯誤的隨機排列算法進行介紹分析，并介紹了經典的隨機排列算法，具有很好的參考價值，需要的朋友一起來看下吧

Array.prototype.sort 方法被許多 JavaScript 程序員誤用來隨機排列數組。最近做的前端星計劃挑戰(zhàn)項目中，一道實現 blackjack 游戲的問題，就發(fā)現很多同學使用了 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 瀏覽器中測試一下，可以得出結果，發(fā)現結果并不隨機分布，各個位置的平均值越往后越大，這意味著這種隨機算法越大的數字出現在越后面的概率越大。

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

首先我們知道排序算法有很多種，而 ECMAScript 并沒有規(guī)定 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 內置的排序算法這么排序，通?？隙ㄊ?strong>不完全隨機的。

經典的隨機排列

所有空間復雜度 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;
}

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

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

隨機性的數學歸納法證明

對 n 個數進行隨機：

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

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

對于 i + 1 個數，按照我們的算法，在第一次循環(huán)時，每個數都有 1/(i+1) 的概率被交換到最末尾，所以每個元素出現在最末一位的概率都是 1/(i+1) 。而每個數也都有 i/(i+1) 的概率不被交換到最末尾，如果不被交換，從第二次循環(huán)開始還原成 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。

總結

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

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

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

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

您可能感興趣的文章: