hack86的个人网站：http://as.hack86.cn
这几天看到网络上在讨论关于随机打乱数组的问题!发现很多朋友的都有自己的方法,但是否真正的随机了呢?这个问题的争议一直很大,我在总结后,以及对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;
}
用随机索引函数产生的数组作为预被打乱的数组的新索引,进行赋值,即完成了完全打乱的效果!
就此对于随机打乱数组的研究也进行完了,希望对喜欢的朋友们有些帮助!
源文件下载
