关于随机打乱数组的深入研究 (原创)

hack86 楼主

这几天看到网络上在讨论关于随机打乱数组的问题!发现很多朋友的都有自己的方法,但是否真正的随机了呢?这个问题的争议一直很大,我在总结后,以及对Array.sort()内部构造的猜测后发现,还是有很多不是太完美的地方,所以我经过思考还是写了一套关于自己的数组随机打乱的函数,希望与大家分享一下!
文章出处: http://hack86.cn/article.asp?id=67
欢迎访问我的Blog的相关专业板块: http://hack86.cn/default.asp?cateID=9

好了,言归正转,来看看我们的三个函数,分别是:
randomArray(arrLen) 功能为:产生一个完全随机的数组,参数为数组的长度.
randomIndex(arrLen) 功能为:根据参数产生一个数组,从0起到长度-1的所有自然数随机打乱
randomSort(arr) 功能为:随机打乱一个数组中所有值的顺序.

首先是随机数组,这是最简单的一个函数,来看一下代码!
function randomArray(arrLen) {
    var rArr:Array = new Array(arrLen);
    for (var i = 0; i<arrLen; i++) {
        rArr = Math.random();
    }
    return rArr;
}
是不是很简单,我相信不用过多的解释!函数返回的rArr这个数组里的所有数都是放射性随机的,所以将来会很有用的!另外值得说明的就是用Math类产生的随机数,客观上是不可能会有任何重复的,因为概率小的几乎可以完全忽略,即使数组长度为千百万以上!

其次我们来看看,建立随机索引的过程:
function randomIndex(arrLen) {
    var iArr:Array = new Array(arrLen);
    var rArr = randomArray(arrLen);  //建立随机数组,以备使用
    for (var i = 0; i<arrLen; i++) {  //遍历数组,寻找最小的数字
        iArr = i;  //默认被比较的数字为最小数字,并记录索引
        var t = rArr;  //记录该数字在临时变量中
        for (var j = 0; j<arrLen; j++) {  //与所有数字进行比较
            if (rArr[j]<t) {  //如果发现更小的数字,则更新
                iArr = j;
                t = rArr[j];
            }
        }
        delete t;
        rArr[iArr] = 1;  //将最小的数字设置成1.
    }
    return iArr;
}
简单说一下原理吧:随机数组中的所有数字的大小全是不确定的,相互之间也是不确定的!任何一个数字都可能最大,也都可能最小,所以每次都会产生不同的序列,那么他们排序后索引就会被完全打乱,由此也起到了真正的随机效果!值得一提的是其中rArr[iArr]=1;是因为Math.random();不可能出现1,也就是说任何数都比1小,也保证的1是最大的,那么修改它后,第二次比较的时候就会让它失去了比较权,因为上一轮它已经是最小的数了,并且已经被记录过了!相反如果语句if(rArr[j]<t)其中的小于号改成大于号,最后的值应该设置成0,同样可以起到放射性随机的效果,只是结果完全相反而已.

现在打乱了所有的索引,最后要做的就是根据这个完全随机的索引序列,随机打乱数组中所有的值了:
function randomSort(arr) {
    arrLen = arr.length;
    var tArr = new Array(arrLen);  //建立临时数组,存放随机打乱的数组
    var iArr = randomIndex(arrLen);  //建立随机索引
    for (var i = 0; i<arrLen; i++) {
        tArr = arr[iArr]; //根据随机索引完全打乱数组中所有的值
    }
    return tArr;
}
用随机索引函数产生的数组作为预被打乱的数组的新索引,进行赋值,即完成了完全打乱的效果!

就此对于随机打乱数组的研究也进行完了,希望对喜欢的朋友们有些帮助!有空多多支持我的文章,最后也谢谢大家对我的支持!(作者:Hack86 QQ:10578417 源文件下载)

hack86 楼主

想了一整天,还是自己做个沙发吧,希望加精,最好被收录,嘻嘻.谢谢啦~  随便进行答辩

回5楼：
Math.random();重复的概率基本是不可能!可能性和DNS或者指纹的重复概率一样!
你可以直接trace(Math.random());看结果! 即使重复,也不会影响到整个数组,因为只取索引,所以即使出现两个重复的,默认前面这个会比较小~这样randomIndex();返回的依然是一个不重复的打乱过的索引序列集合.您可以尝试一下!

回6楼：
如果测试的话,我想是比较难做到的,而且没个数都测试,这样工作量和效率都会很低!我在写randomIndex()这个函数的时候,个人感觉效率已经不太高了!有机会这个函数还需要修改一下的!

回7楼：
t这个变量名,是temp的缩写,至于为什么要用这个变量来临时存放数字,我的想法是这样的:randomIndex中,每个数都要和所有的数字比较一次,也就是说每个数都会从第一个数字开始遍历数组中所有的数字进行比较,如果出现了比自己小的数字,那么t就用来存放小的数字,遍历完后,t中的变量一定是最小的!遍历前的t=rArr的作用是使得取出来的数默认为最小,因为代码中只有出现比自己还小的数字才会对t进行赋值,那么如果没有呢?所以默认自己为最小!
而这位朋友所说的t=rArr[j]的作用,简单解释一下,如果没有,我们假设一个实例,rArr[5]比rArr[3]要小,这时候iArr更新了索引,记录了5,但是如你所说去掉了t=rArr[j],那么最小值并没有更新,但你注意看if语句,是用t和rArr[j]在比较,也就是说索引记录了rArr[5]中的索引5,可是比较还在用t,也就是说用rArr[3]在比较,这样明显就会出现意想不到的错误.
至于你的答案,因为本省就是将索引重新排序,所以不会出现意外的值,但结果并不是我们想要的!

回8楼：
我的程序是比较初级的一个思路,而你的确实效率比较高!推荐! ps:我的QQ 10578417 希望 abc12hjc  朋友能加我一下,谢谢~~

[ 本帖最后由 hack86 于 2007-2-25 18:22 编辑 ]

awflasher

不错：）
鼓励发表感想！

jimohuoshan

现在都这么厉害了啊？进步很神速，加油！

realbobon

Math.random();
这样产生的随机数不会有重复吗？要是重复了怎么办？

wishbecame

我觉得在小循环里监测一下重复，如果重复了就删除重复的，然后数组再多加1后保持数组的长度不变

没动手做 只是这样想了一下

haoxue

想法真的不错,的确,即使万一(真的是万一)Math.random产生了相等数字,也不会影响排序.但有一点我不明白,在 randomIndex中我认为t = rArr[j]一句没什么用处,于是我试着去掉了一下,可是发现如果去掉这一句,则排出的数组出面o在最前和1在最后的机率特别大,而添上这一句就不会出现这种睛况,请问hack86 老弟这一句的作用是什么?

abc12hjc

一个乱序算法，无非涉及到两个问题：随机性和效率
下面就这两个方面用楼主的算法和我自己写的算法做一个对比

1. //----------------------------------------|
   
2. //  hack86.
   
3. 
   
4. function randomArray(arrLen) {
   
5.         var rArr:Array = new Array(arrLen);
   
6.         for (var i = 0; i<arrLen; i++) {
   
7.                 rArr[i] = Math.random();
   
8.         }
   
9.         return rArr;
   
10. }
    
11. function randomIndex(arrLen) {
    
12.         var iArr:Array = new Array(arrLen);
    
13.         var rArr = randomArray(arrLen);
    
14.         for (var i = 0; i<arrLen; i++) {
    
15.                 iArr[i] = i;
    
16.                 var t = rArr[i];
    
17.                 for (var j = 0; j<arrLen; j++) {
    
18.                         if (rArr[j]<t) {
    
19.                                 iArr[i] = j;
    
20.                                 t = rArr[j];
    
21.                         }
    
22.                 }
    
23.                 delete t;
    
24.                 rArr[iArr[i]] = 1;
    
25.         }
    
26.         return iArr;
    
27. }
    
28. function randomSort(arr) {
    
29.         arrLen = arr.length;
    
30.         var tArr = new Array(arrLen);
    
31.         var iArr = randomIndex(arrLen);
    
32.         for (var i = 0; i<arrLen; i++) {
    
33.                 tArr[i] = arr[iArr[i]];
    
34.         }
    
35.         return tArr;
    
36. }
    
37. 
    
38. //----------------------------------------|
    
39. //  abc12hjc.
    
40. 
    
41. Array.prototype.random = function ($lim:Number):Array
    
42. {
    
43.         var tmp:Array  = this.concat();
    
44.         var len:Number = tmp.length;
    
45.        
    
46.         for (var i = 0; i < (($lim && $lim < (len-1)) ? $lim : (len-1)); i++)
    
47.         {
    
48.                 var n:Number = len - i;
    
49.                 var r:Number = random(n);
    
50. 
    
51.                 var t:Number = tmp[r]; tmp[r] = tmp[n-1]; tmp[n-1] = t;
    
52.         }
    
53.         return tmp.slice(-$lim);
    
54. }
    
55. 
    
56. 
    
57. //----------------------------------------|
    
58. //  init.
    
59. 
    
60. var arr:Array  = [];
    
61. var tmp:Array  = [];
    
62. var cou1:Array = [];
    
63. var cou2:Array = [];
    
64. 
    
65. var n:Number = 20000;
    
66. 
    
67. for (var i = 0; i < 10; i++)
    
68. {
    
69.         arr[i]  = i;
    
70.         cou1[i] = cou2[i] = 0;
    
71. }
    
72. 
    
73. //----------------------------------------|
    
74. //  random test.
    
75. 
    
76. var suffix:Number = random(arr.length);
    
77. 
    
78. for (var i = 0; i < n; i++)
    
79. {
    
80.         var tmp1:Number = randomSort(arr)[suffix];
    
81.         var tmp2:Number = arr.random()[suffix];
    
82.         cou1[tmp1]++;
    
83.         cou2[tmp2]++;
    
84. }
    
85. 
    
86. trace("[random test]")
    
87. trace("hack86   : "+ cou1.sort(16));
    
88. trace("abc12hjc : "+ cou2.sort(16));
    
89. trace("");
    
90. 
    
91. //----------------------------------------|
    
92. //  efficiency test.
    
93. 
    
94. var t:Number = getTimer();
    
95. 
    
96. for (var j = 0; j < n; j++)
    
97. {
    
98.         tmp = randomSort(arr);
    
99. }
    
100. 
     
101. trace("[efficiency test]");
     
102. trace("hack86   : " + (getTimer() - t) + "ms");
     
103. t = getTimer();
     
104. 
     
105. for (var k = 0; k < n; k++)
     
106. {
     
107.         tmp = arr.random();
     
108. }
     
109. 
     
110. trace("abc12hjc : " + (getTimer() - t) + "ms");

复制代码

[ 本帖最后由 abc12hjc 于 2007-2-16 03:47 编辑 ]

abc12hjc

测试环境

AMD A64 3000+
Windows XP SP2
Macromedia Flash Professional 8


测试结果

[random test]
hack86   : 1931,1943,1957,1968,1988,2020,2025,2027,2059,2082
abc12hjc : 1945,1961,1965,1985,1991,1995,2002,2044,2049,2063

[efficiency test]
hack86   : 5369ms
abc12hjc : 1620ms


====================
在随机性测试中， 20000 次循环下两种算法得到的数据均为随机分布。
在效率测试中，20000 次循环下楼主的算法比我慢 3.3 倍。

[ 本帖最后由 abc12hjc 于 2007-2-16 03:11 编辑 ]

nang

来个简单的
var a_array:Array = String("sadfhjkwerioshvxcvnflgjhasafhjhvcsd").split("");
var b_array:Array = [];
for (k=0; k<a_array.length; k++) {
        m = random(a_array.length);
        b_array[k] = a_array[m];
        a_array.splice(m, 0);
}
trace(b_array);