| 数组的完全随机排列算法javascript实现 |
Array.prototype.sort 方法被许多 JavaScript 程序员误用来随机排列数组。最近做的前端星计划挑战项目中，一道实现 blackjack 游戏的问题，就发现很多同学使用了 Array.prototype.sort 来洗牌。就连最近一期 JavaScript Weekly上推荐的一篇文章也犯了同样的错误。
2LTW8s http://blog.numino.net/
以下就是常见的完全错误的随机排列算法：
gLh1yS http://blog.numino.net/
function shuffle(arr){
Hl4sMB http://blog.numino.net/
return arr.sort(function(){
VrDfee http://blog.numino.net/
return Math.random() - 0.5;
3ojvJm http://blog.numino.net/
});
J1ciEi http://blog.numino.net/
}
AGXiXA http://blog.numino.net/
以上代码看似巧妙利用了 Array.prototype.sort 实现随机，但是，却有非常严重的问题，甚至是完全错误。
NZhp68 http://blog.numino.net/
证明 Array.prototype.sort 随机算法的错误
1jVz9f http://blog.numino.net/
为了证明这个算法的错误，我们设计一个测试的方法。假定这个排序算法是正确的，那么，将这个算法用于随机数组 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]，如果算法正确，那么每个数字在每一位出现的概率均等。因此，将数组重复洗牌足够多次，然后将每次的结果在每一位相加，最后对每一位的结果取平均值，这个平均值应该约等于 (0 + 9) / 2 = 4.5，测试次数越多次，每一位上的平均值就都应该越接近于 4.5。所以我们简单实现测试代码如下：
83SI9J http://blog.numino.net/
var arr = [0,1,2,3,4,5,6,7,8,9];
zn1JpJ http://blog.numino.net/
var res = [0,0,0,0,0,0,0,0,0,0];
b4bDtZ http://blog.numino.net/
var t = 10000;
tzoP5c http://blog.numino.net/
for(var i = 0; i < t; i++){
6K06m1 http://blog.numino.net/
var sorted = shuffle(arr.slice(0));
kDTWUV http://blog.numino.net/
sorted.forEach(function(o,i){
kabRqK http://blog.numino.net/
res[i] += o;
TqS3TZ http://blog.numino.net/
});
8b5azX http://blog.numino.net/
}
MytC2p http://blog.numino.net/
res = res.map(function(o){
uo0r0e http://blog.numino.net/
return o / t;
xQIsMF http://blog.numino.net/
});
y3yFMU http://blog.numino.net/
console.log(res);
0v1Is7 http://blog.numino.net/
将上面的 shuffle 方法用这段测试代码在 chrome 浏览器中测试一下，可以得出结果，发现结果并不随机分布，各个位置的平均值越往后越大，这意味着这种随机算法越大的数字出现在越后面的概率越大。
FUQ1Tv http://blog.numino.net/
为什么会产生这个结果呢？我们需要了解 Array.prototype.sort 究竟是怎么作用的。
LmqQpO http://blog.numino.net/
首先我们知道排序算法有很多种，而 ECMAScript 并没有规定 Array.prototype.sort 必须使用何种排序算法。在这里，有兴趣的同学不妨看一下 JavaScriptCore 的源码实现：
tZF6pv http://blog.numino.net/
排序不是我们今天讨论的主题，但是不论用何种排序算法，都是需要进行两个数之间的比较和交换，排序算法的效率和两个数之间比较和交换的次数有关系。
4k2434 http://blog.numino.net/
最基础的排序有冒泡排序和插入排序，原版的冒泡或者插入排序都比较了 n(n-1)/2 次，也就是说任意两个位置的元素都进行了一次比较。那么在这种情况下，如果采用前面的 sort 随机算法，由于每次比较都有 50% 的几率交换和不交换，这样的结果是随机均匀的吗？我们可以看一下例子：
G6EV5U http://blog.numino.net/
function bubbleSort(arr, compare){
lgFHGe http://blog.numino.net/
var len = arr.length;
YYz790 http://blog.numino.net/
for(var i = 0; i < len - 1; i++){
qqw6r2 http://blog.numino.net/
for(var j = 0; j < len - 1 - i; j++){
B60bUs http://blog.numino.net/
var k = j + 1;
ODUnHV http://blog.numino.net/
if(compare(arr[j], arr[k]) > 0){
6ob26W http://blog.numino.net/
var tmp = arr[j];
O7xTW0 http://blog.numino.net/
arr[j] = arr[k];
0rRC68 http://blog.numino.net/
arr[k] = tmp;
c9IvjW http://blog.numino.net/
}
jydfa1 http://blog.numino.net/
}
KAlp4m http://blog.numino.net/
}
Q964vl http://blog.numino.net/
return arr;
sEEtMX http://blog.numino.net/
}
Ap39T4 http://blog.numino.net/
function shuffle(arr){
3HedFT http://blog.numino.net/
return bubbleSort(arr, function(){
oT85P3 http://blog.numino.net/
return Math.random() - 0.5;
bi2HnG http://blog.numino.net/
});
3Z6h5F http://blog.numino.net/
}
I7GYqU http://blog.numino.net/
var arr = [0,1,2,3,4,5,6,7,8,9];
oJNAqC http://blog.numino.net/
var res = [0,0,0,0,0,0,0,0,0,0];
2Jocmu http://blog.numino.net/
var t = 10000;
Y3w6cC http://blog.numino.net/
for(var i = 0; i < t; i++){
Too29y http://blog.numino.net/
var sorted = shuffle(arr.slice(0));
J8mUbK http://blog.numino.net/
sorted.forEach(function(o,i){
H7xdQ4 http://blog.numino.net/
res[i] += o;
rTp4v0 http://blog.numino.net/
});
msT7C3 http://blog.numino.net/
}
MwkTe2 http://blog.numino.net/
res = res.map(function(o){
pAA1aD http://blog.numino.net/
return o / t;
4W5Tp8 http://blog.numino.net/
});
Vt9kg2 http://blog.numino.net/
console.log(res);
Njro6H http://blog.numino.net/
上面的代码的随机结果也是不均匀的，测试平均值的结果越往后的越大。（笔者之前没有复制原数组所以错误得出均匀的结论，已更正于 2016-05-10）
lMyW4W http://blog.numino.net/
冒泡排序总是将比较结果较小的元素与它的前一个元素交换，我们可以大约思考一下，这个算法越后面的元素，交换到越前的位置的概率越小（因为每次只有50%几率“冒泡”），原始数组是顺序从小到大排序的，因此测试平均值的结果自然就是越往后的越大（因为越靠后的大数出现在前面的概率越小）。
E72Gq0 http://blog.numino.net/
我们再换一种算法，我们这一次用插入排序：
ZL25jI http://blog.numino.net/
function insertionSort(arr, compare){
xuettM http://blog.numino.net/
var len = arr.length;
DauWa0 http://blog.numino.net/
for(var i = 0; i < len; i++){
P5rcRx http://blog.numino.net/
for(var j = i + 1; j < len; j++){
fZV7U8 http://blog.numino.net/
if(compare(arr[i], arr[j]) > 0){
iSrEC7 http://blog.numino.net/
var tmp = arr[i];
iHi0jB http://blog.numino.net/
arr[i] = arr[j];
uDJl0i http://blog.numino.net/
arr[j] = tmp;
QhNclm http://blog.numino.net/
}
exs4U8 http://blog.numino.net/
}
zNVFbQ http://blog.numino.net/
}
OgLPhc http://blog.numino.net/
return arr;
6AaA31 http://blog.numino.net/
}
zfS7p3 http://blog.numino.net/
function shuffle(arr){
EcjB2b http://blog.numino.net/
return insertionSort(arr, function(){
0zz5WF http://blog.numino.net/
return Math.random() - 0.5;
1h40y3 http://blog.numino.net/
});
4EGsx5 http://blog.numino.net/
}
naV2s4 http://blog.numino.net/
var arr = [0,1,2,3,4,5,6,7,8,9];
IS0dk2 http://blog.numino.net/
var res = [0,0,0,0,0,0,0,0,0,0];
KBEb8g http://blog.numino.net/
var t = 10000;
6eFJ4X http://blog.numino.net/
for(var i = 0; i < t; i++){
dLOO7Q http://blog.numino.net/
var sorted = shuffle(arr.slice(0));
cbU8mu http://blog.numino.net/
sorted.forEach(function(o,i){
PyUl42 http://blog.numino.net/
res[i] += o;
KjSVPp http://blog.numino.net/
});
w5yP2t http://blog.numino.net/
}
ayzo04 http://blog.numino.net/
res = res.map(function(o){
cKVX1k http://blog.numino.net/
return o / t;
G1dGsE http://blog.numino.net/
});
wdH21R http://blog.numino.net/
console.log(res);
L3T8Va http://blog.numino.net/
由于插入排序找后面的大数与前面的数进行交换，这一次的结果和冒泡排序相反，测试平均值的结果自然就是越往后越小。原因也和上面类似，对于插入排序，越往后的数字越容易随机交换到前面。
svPYJg http://blog.numino.net/
所以我们看到即使是两两交换的排序算法，随机分布差别也是比较大。除了每个位置两两都比较一次的这种排序算法外，大多数排序算法的时间复杂度介于 O(n) 到 O(n2) 之间，元素之间的比较次数通常情况下要远小于 n(n-1)/2，也就意味着有一些元素之间根本就没机会相比较（也就没有了随机交换的可能），这些 sort 随机排序的算法自然也不能真正随机。
048cV7 http://blog.numino.net/
我们将上面的代码改一下，采用快速排序：
0q5Gdt http://blog.numino.net/
function quickSort(arr, compare){
w3a8Ca http://blog.numino.net/
arr = arr.slice(0);
7hpCu7 http://blog.numino.net/
if(arr.length <= 1) return arr;
Fhuvf0 http://blog.numino.net/
var mid = arr[0], rest = arr.slice(1);
KYGHFW http://blog.numino.net/
var left = [], right = [];
DmDxDw http://blog.numino.net/
for(var i = 0; i < rest.length; i++){
yVj9y2 http://blog.numino.net/
if(compare(rest[i], mid) > 0){
s61ZnD http://blog.numino.net/
right.push(rest[i]);
Ff1p63 http://blog.numino.net/
}else{
b3i2p7 http://blog.numino.net/
left.push(rest[i]);
29IYj9 http://blog.numino.net/
}
tvmYX7 http://blog.numino.net/
}
YBKa3t http://blog.numino.net/
return quickSort(left, compare).concat([mid])
1z5s2B http://blog.numino.net/
.concat(quickSort(right, compare));
l6h2S3 http://blog.numino.net/
}
XB8r2C http://blog.numino.net/
function shuffle(arr){
64ll4M http://blog.numino.net/
return quickSort(arr, function(){
4jtScw http://blog.numino.net/
return Math.random() - 0.5;
7haFx2 http://blog.numino.net/
});
8JS9qm http://blog.numino.net/
}
i4S060 http://blog.numino.net/
var arr = [0,1,2,3,4,5,6,7,8,9];
v0g2N7 http://blog.numino.net/
var res = [0,0,0,0,0,0,0,0,0,0];
NdAgwI http://blog.numino.net/
var t = 10000;
jlG9Nd http://blog.numino.net/
for(var i = 0; i < t; i++){
jq6433 http://blog.numino.net/
var sorted = shuffle(arr.slice(0));
YS18tf http://blog.numino.net/
sorted.forEach(function(o,i){
i3gs91 http://blog.numino.net/
res[i] += o;
icpJO4 http://blog.numino.net/
});
9spVaV http://blog.numino.net/
}
RCaxKL http://blog.numino.net/
res = res.map(function(o){
p4aPmw http://blog.numino.net/
return o / t;
VWaFS4 http://blog.numino.net/
});
gYVQ0d http://blog.numino.net/
console.log(res);
pN2X8y http://blog.numino.net/
快速排序并没有两两元素进行比较，它的概率分布也不随机。
C5h43N http://blog.numino.net/
所以我们可以得出结论，用 Array.prototype.sort 随机交换的方式来随机排列数组，得到的结果并不一定随机，而是取决于排序算法是如何实现的，用 JavaScript 内置的排序算法这么排序，通常肯定是不完全随机的。
1z190O http://blog.numino.net/
经典的随机排列
8Z4Jev http://blog.numino.net/
所有空间复杂度 O(1) 的排序算法的时间复杂度都介于 O(nlogn) 到 O(n2) 之间，因此在不考虑算法结果错误的前提下，使用排序来随机交换也是慢的。事实上，随机排列数组元素有经典的 O(n) 复杂度的算法：
0tpl8X http://blog.numino.net/
function shuffle(arr){
1Y7rk4 http://blog.numino.net/
var len = arr.length;
QqCxRk http://blog.numino.net/
for(var i = 0; i < len - 1; i++){
ge635M http://blog.numino.net/
var idx = Math.floor(Math.random() * (len - i));
ozGZET http://blog.numino.net/
var temp = arr[idx];
NA0Hj2 http://blog.numino.net/
arr[idx] = arr[len - i - 1];
07R4QV http://blog.numino.net/
arr[len - i -1] = temp;
OcoZpF http://blog.numino.net/
}
T8DjS6 http://blog.numino.net/
return arr;
RzFH4q http://blog.numino.net/
}
QeIzc2 http://blog.numino.net/
在上面的算法里，我们每一次循环从前 len - i 个元素里随机一个位置，将这个元素和第 len - i 个元素进行交换，迭代直到 i = len - 1 为止。
oS7h7c http://blog.numino.net/
我们同样可以检验一下这个算法的随机性：
jkzrq3 http://blog.numino.net/
function shuffle(arr){
Cqs597 http://blog.numino.net/
var len = arr.length;
QXO1Ni http://blog.numino.net/
for(var i = 0; i < len - 1; i++){
8K0CkA http://blog.numino.net/
var idx = Math.floor(Math.random() * (len - i));
pY3pkg http://blog.numino.net/
var temp = arr[idx];
yY3595 http://blog.numino.net/
arr[idx] = arr[len - i - 1];
5smiAB http://blog.numino.net/
arr[len - i -1] = temp;
jz5qlt http://blog.numino.net/
}
JiBB8Z http://blog.numino.net/
return arr;
E45fu3 http://blog.numino.net/
}
q02SVX http://blog.numino.net/
var arr = [0,1,2,3,4,5,6,7,8,9];
0T4cE5 http://blog.numino.net/
var res = [0,0,0,0,0,0,0,0,0,0];
R4BA41 http://blog.numino.net/
var t = 10000;
1gjtlO http://blog.numino.net/
for(var i = 0; i < t; i++){
s0h8wZ http://blog.numino.net/
var sorted = shuffle(arr.slice(0));
7tJN0K http://blog.numino.net/
sorted.forEach(function(o,i){
jy2fC2 http://blog.numino.net/
res[i] += o;
ByELnj http://blog.numino.net/
});
4BG84J http://blog.numino.net/
}
jfZE9r http://blog.numino.net/
res = res.map(function(o){
t8JvrR http://blog.numino.net/
return o / t;
sh1Ehe http://blog.numino.net/
});
QC2mTX http://blog.numino.net/
console.log(res);
qIre91 http://blog.numino.net/
从结果可以看出这个算法的随机结果应该是均匀的。不过我们的测试方法其实有个小小的问题，我们只测试了平均值，实际上平均值接近只是均匀分布的必要而非充分条件，平均值接近不一定就是均匀分布。不过别担心，事实上我们可以简单从数学上证明这个算法的随机性。
PEPvS6 http://blog.numino.net/
随机性的数学归纳法证明
o68TG1 http://blog.numino.net/
对 n 个数进行随机：
3po9Eu http://blog.numino.net/
首先我们考虑 n = 2 的情况，根据算法，显然有 1/2 的概率两个数交换，有 1/2 的概率两个数不交换，因此对 n = 2 的情况，元素出现在每个位置的概率都是 1/2，满足随机性要求。
ejyLy3 http://blog.numino.net/
假设有 i 个数， i >= 2 时，算法随机性符合要求，即每个数出现在 i 个位置上每个位置的概率都是 1/i。
v1aRXa http://blog.numino.net/
对于 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)。
veD2GF http://blog.numino.net/
综合 1. 2. 3. 得出，对于任意 n >= 2，经过这个算法，每个元素出现在 n 个位置任意一个位置的概率都是 1/n。
b1c1MK http://blog.numino.net/
总结
Vj5nwW http://blog.numino.net/
一个优秀的算法要同时满足结果正确和高效率。很不幸使用 Array.prototype.sort 方法这两个条件都不满足。因此，当我们需要实现类似洗牌的功能的时候，还是应该采用巧妙的经典洗牌算法，它不仅仅具有完全随机性还有很高的效率。
VG78cj http://blog.numino.net/
除了收获这样的算法之外，我们还应该认真对待这种动手分析和解决问题的思路，并且捡起我们曾经学过而被大多数人遗忘的数学（比如数学归纳法这种经典的证明方法）。
30z0Di http://blog.numino.net/
有任何问题欢迎与作者探讨~
KSm1JN http://blog.numino.net/
本文转载自：https://www.h5jun.com/post/array-shuffle.html
|
|