详解js数组的完全随机排列算法

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 方法这两个条件都不满足。因此,当我们需要实现类似洗牌的功能的时候,还是应该采用巧妙的经典洗牌算法,它不仅仅具有完全随机性还有很高的效率。

除了收获这样的算法之外,我们还应该认真对待这种动手分析和解决问题的思路,并且捡起我们曾经学过而被大多数人遗忘的数学(比如数学归纳法这种经典的证明方法)。

有任何问题欢迎与作者探讨~

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持我们!

(0)

相关推荐

  • JavaScript实现经典排序算法之选择排序

    表现最稳定的排序算法之一,因为无论什么数据进去都是O(n²)的时间复杂度.....所以用到它的时候,数据规模越小越好.唯一的好处可能就是不占用额外的内存空间. 1)算法原理 先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 2)算法描述和实现 n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果.具体算法描述如下: <1>初始状态:无序区为R[1..n],有序区为

  • JavaScript实现的选择排序算法实例分析

    本文实例讲述了JavaScript实现的选择排序算法.分享给大家供大家参考,具体如下: 简单选择排序是人们最熟悉的比较方式,其算法思想为:从数组的开头开始,将第一个元素和其他元素进行比较.检查完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从第二个位置继续.这个过程会一直进行,当进行到数组的倒数第二个位置时,所有的数据便完成了排序. 代码如下: <!DOCTYPE html> <html> <head> <meta charset="utf-

  • JS实现随机数生成算法示例代码

    1: 复制代码 代码如下: var MT = []; var index = 0; function initialize_generator(seed) { MT[0] = seed; for (var i = 1; i < 624; i++) { MT[i] = 0xffffffff & (0x6c078965 * (MT[i - 1] ^ (MT[i - 1] >> 30)) + i); } } function generate_numbers() { for (var

  • JavaScript随机打乱数组顺序之随机洗牌算法

    假如有一个数组是这样子: var arr1 = ["a", "b", "c", "d"]; 如何随机打乱数组顺序,也即洗牌. 有一个比较广为传播的简单随机算法: function RandomSort (a,b){ return (0.5 - Math.random()); } 实际证明上面这个并不完全随机. 随便一搜网上太多这种东西了,看一下stackoverflow上的一个高分回答,答案出自github上. knuth-s

  • JavaScript实现经典排序算法之冒泡排序

    冒泡排序可谓是最经典的排序算法了,它是基于比较的排序算法,时间复杂度为O(n^2),其优点是实现简单,n较小时性能较好. 1)算法原理        相邻的数据进行两两比较,小数放在前面,大数放在后面,这样一趟下来,最小的数就被排在了第一位,第二趟也是如此,如此类推,直到所有的数据排序完成. 2)算法描述        <1>比较相邻的元素.如果第一个比第二个大,就交换它们两个:        <2>对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会

  • JS实现的随机排序功能算法示例

    本文实例讲述了JS实现的随机排序功能算法.分享给大家供大家参考,具体如下: 使用JS编写一个方法 让数组中的元素每次刷新随机排列 方法一: var arr =[1,2,3,4]; var t; for(var i = 0;i < arr.length; i++){ var rand = parseInt(Math.random()*arr.length); t = arr[rand]; arr[rand] =arr[i]; arr[i] = t; } console.log(arr); 方法二:

  • JavaScript实现经典排序算法之插入排序

    插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂.像排序一手扑克牌,开始时,我们的左手为空并且桌子上的牌面向下.然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置.为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较,拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌. 1)算法原理 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序

  • JS随机洗牌算法之数组随机排序

    推荐阅读:JavaScript学习笔记之数组的增.删.改.查 JavaScript学习笔记之数组求和方法 JavaScript学习笔记之数组随机排序 洗牌算法是一个比较形象的术语,本质上让一个数组内的元素随机排列.举例来说,我们有一个如下图所示的数组,数组长度为 9,数组内元素的值顺次分别是 1~9: 从上面这个数组入手,我们要做的就是打乱数组内元素的顺序: 代码实现 维基百科上的 Fisher–Yates shuffle 词条对洗牌算法做了详细介绍,下面演示的算法也是基于其中的理论编写的: A

  • javascript随机之洗牌算法深入分析

    洗牌算法是我们常见的随机问题,在玩游戏.随机排序时经常会碰到.它可以抽象成这样:得到一个M以内的所有自然数的随机顺序数组. 在百度搜"洗牌算法",第一个结果是<百度文库-洗牌算法>,扫了一下里面的内容,很多内容都容易误导别人走上歧途,包括最后用链表代替数组,也只是一个有限的优化(链表也引入了读取效率的损失). 该文里的第一种方法,可以简单描述成:随机抽牌,放在另一组:再次抽取,抽到空牌则重复抽."抽到空牌则重复抽"这会导致后面抽到空牌的机会越来越大,显然

  • 基于JavaScript实现的插入排序算法分析

    本文实例讲述了基于JavaScript实现的插入排序算法.分享给大家供大家参考,具体如下: 根据排序过程中使用的存储器不同,可以将排序方法分为两大类:内部排序和外部排序. 内部排序是指待排序记录存放在计算机随机存储器中进行的排序过程:外部排序指的是待排序的记录数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程. 下面介绍几种常见的内部排序方式: 插入排序 插入排序是一种最简单的排序方法,它的基本操作是将一个记录插入已排好序的有序表中,从而得到一个新的.记录数加1的有

  • 基于JavaScript实现的快速排序算法分析

    本文实例讲述了基于JavaScript实现的快速排序算法.分享给大家供大家参考,具体如下: 首先要介绍一下冒泡排序,冒泡排序的过程很简单,首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个关键字交换,然后比较第二个和第三个,直到最后一个比较完成.这是第一趟冒泡,其结果使得关键字最大的记录被安置到最后一个位置上了.然后对序列前n-1个元素进行第二次冒泡,将倒数第二个选出.以此类推直到所有被选出,冒泡结束. 通过分析可以得出,冒泡排序的时间复杂度为O(n2). 快速排序是对冒泡

  • 基于JavaScript实现的希尔排序算法分析

    本文实例讲述了基于JavaScript实现的希尔排序算法.分享给大家供大家参考,具体如下: 通过对直接插入排序的分析,可知其时间复杂度为O(n2),但是,如果待排序序列为正序时,其时间复杂度可提高至O(n).希尔排序正是对此进行改进的排序.希尔排序的核心理念与插入排序不同,它会首先比较距离较远的元素,而非相邻元素.通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔. 下图演示了希尔排序中间隔序列是如何运行的: 下面我们通过js来实现希尔排序,代码如下: <!DOCTYPE ht

随机推荐