关于随机打乱数组的深入研究

这几天看到网络上在讨论关于随机打乱数组的问题!发现很多朋友的都有自己的方法,但是否真正的随机了呢?这个问题的争议一直很大,我在总结后,以及对Array.sort()内部构造的猜测后发现,还是有很多不是太完美的地方,所以我经过思考还是写了一套关于自己的数组随机打乱的函数,希望与大家分享一下!

好了,言归正转,来看看我们的三个函数,分别是:

• 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[i] = 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] = i;  //默认被比较的数字为最小数字,并记录索引
        var t = rArr[i];  //记录该数字在临时变量中
        for (var j = 0; j<arrLen; j++) {  //与所有数字进行比较
            if (rArr[j]<t) {  //如果发现更小的数字,则更新
                iArr[i] = j;
                t = rArr[j];
            }
        }
        delete t;
        rArr[iArr[i]] = 1;  //将最小的数字设置成1.
    }
    return iArr;
}

简单说一下原理吧:随机数组中的所有数字的大小全是不确定的,相互之间也是不确定的!任何一个数字都可能最大,也都可能最小,所以每次都会产生不同的序列,那么他们排序后索引就会被完全打乱,由此也起到了真正的随机效果!值得一提的是其中rArr[iArr[i]]=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[i] = arr[iArr[i]]; //根据随机索引完全打乱数组中所有的值
    }
    return tArr;
}

用随机索引函数产生的数组作为预被打乱的数组的新索引,进行赋值,即完成了完全打乱的效果!

就此对于随机打乱数组的研究也进行完了,希望对喜欢的朋友们有些帮助!

/upimg/soft/1_061225153352.rar