|
hack86的個(gè)人網(wǎng)站：http://as.hack86.cn
這幾天看到網(wǎng)絡(luò)上在討論關(guān)于隨機(jī)打亂數(shù)組的問題!發(fā)現(xiàn)很多朋友的都有自己的方法,但是否真正的隨機(jī)了呢?這個(gè)問題的爭議一直很大,我在總結(jié)后,以及對Array.sort()內(nèi)部構(gòu)造的猜測后發(fā)現(xiàn),還是有很多不是太完美的地方,所以我經(jīng)過思考還是寫了一套關(guān)于自己的數(shù)組隨機(jī)打亂的函數(shù),希望與大家分享一下!
好了,言歸正轉(zhuǎn),來看看我們的三個(gè)函數(shù),分別是:
- randomArray(arrLen) 功能為：產(chǎn)生一個(gè)完全隨機(jī)的數(shù)組,參數(shù)為數(shù)組的長度.
- randomIndex(arrLen) 功能為：根據(jù)參數(shù)產(chǎn)生一個(gè)數(shù)組,從0起到長度-1的所有自然數(shù)隨機(jī)打亂
- randomSort(arr) 功能為：隨機(jī)打亂一個(gè)數(shù)組中所有值的順序.
首先是隨機(jī)數(shù)組,這是最簡單的一個(gè)函數(shù),來看一下代碼!
function randomArray(arrLen) {
var rArr:Array = new Array(arrLen);
for (var i = 0; i<arrLen; i++) {
rArr[i] = Math.random();
}
return rArr;
}
是不是很簡單,我相信不用過多的解釋!函數(shù)返回的rArr這個(gè)數(shù)組里的所有數(shù)都是放射性隨機(jī)的,所以將來會(huì)很有用的!另外值得說明的就是用Math類產(chǎn)生的隨機(jī)數(shù),客觀上是不可能會(huì)有任何重復(fù)的,因?yàn)楦怕市〉膸缀蹩梢酝耆雎?即使數(shù)組長度為千百萬以上!
其次我們來看看,建立隨機(jī)索引的過程：
function randomIndex(arrLen) {
var iArr:Array = new Array(arrLen);
var rArr = randomArray(arrLen); //建立隨機(jī)數(shù)組,以備使用
for (var i = 0; i<arrLen; i++) { //遍歷數(shù)組,尋找最小的數(shù)字
iArr[i] = i; //默認(rèn)被比較的數(shù)字為最小數(shù)字,并記錄索引
var t = rArr[i]; //記錄該數(shù)字在臨時(shí)變量中
for (var j = 0; j<arrLen; j++) { //與所有數(shù)字進(jìn)行比較
if (rArr[j]<t) { //如果發(fā)現(xiàn)更小的數(shù)字,則更新
iArr[i] = j;
t = rArr[j];
}
}
delete t;
rArr[iArr[i]] = 1; //將最小的數(shù)字設(shè)置成1.
}
return iArr;
}
簡單說一下原理吧:隨機(jī)數(shù)組中的所有數(shù)字的大小全是不確定的,相互之間也是不確定的!任何一個(gè)數(shù)字都可能最大,也都可能最小,所以每次都會(huì)產(chǎn)生不同的序列,那么他們排序后索引就會(huì)被完全打亂,由此也起到了真正的隨機(jī)效果!值得一提的是其中rArr[iArr[i]]=1;是因?yàn)镸ath.random();不可能出現(xiàn)1,也就是說任何數(shù)都比1小,也保證的1是最大的,那么修改它后,第二次比較的時(shí)候就會(huì)讓它失去了比較權(quán),因?yàn)樯弦惠喫呀?jīng)是最小的數(shù)了,并且已經(jīng)被記錄過了!相反如果語句if(rArr[j]<t)其中的小于號(hào)改成大于號(hào),最后的值應(yīng)該設(shè)置成0,同樣可以起到放射性隨機(jī)的效果,只是結(jié)果完全相反而已.
現(xiàn)在打亂了所有的索引,最后要做的就是根據(jù)這個(gè)完全隨機(jī)的索引序列,隨機(jī)打亂數(shù)組中所有的值了：
function randomSort(arr) {
arrLen = arr.length;
var tArr = new Array(arrLen); //建立臨時(shí)數(shù)組,存放隨機(jī)打亂的數(shù)組
var iArr = randomIndex(arrLen); //建立隨機(jī)索引
for (var i = 0; i<arrLen; i++) {
tArr[i] = arr[iArr[i]]; //根據(jù)隨機(jī)索引完全打亂數(shù)組中所有的值
}
return tArr;
}
用隨機(jī)索引函數(shù)產(chǎn)生的數(shù)組作為預(yù)被打亂的數(shù)組的新索引,進(jìn)行賦值,即完成了完全打亂的效果!
就此對于隨機(jī)打亂數(shù)組的研究也進(jìn)行完了,希望對喜歡的朋友們有些幫助!
源文件下載
經(jīng)典論壇討論：
http://bbs.blueidea.com/thread-2694977-1-3.html
出處：藍(lán)色理想
責(zé)任編輯：moby
◎進(jìn)入論壇Flash專欄版塊參加討論
|
