JS實(shí)現(xiàn)數(shù)組隨機(jī)排序的三種方法詳解
1.利用數(shù)組方法sort實(shí)現(xiàn)隨機(jī)排序
實(shí)現(xiàn)隨機(jī)排序方法還是很多的,用for循環(huán)是可以寫的,用Lodash等三方j(luò)s方法庫也行。但個人以為使用sort比較方便,但是他又缺點(diǎn),缺點(diǎn)就是不夠那么的隨機(jī),我看過sort運(yùn)行機(jī)制后,發(fā)現(xiàn)他竟然是利用一個比較器兩兩比較出來的。
var arr = [1, 2, 3, 4, 5] arr.sort(function () { return Math.random() - 0.5 }) console.log(arr);
2.洗牌算法實(shí)現(xiàn)隨機(jī)排序
從原始數(shù)組中每次隨機(jī)選中一個元素,然后放入新數(shù)組中,每取出一個元素后,將將它從原數(shù)組中取出(使用splice方法),原數(shù)組長度減一。
舉例:
現(xiàn)在我有紅桃K、黑桃A、小王三張牌,要求打亂順序,你可以從三張牌抽出任意一張,假設(shè)你抽到的是小王,那么我手里三張牌變成兩張牌,你手里變成1張牌,以此類推,實(shí)現(xiàn)隨機(jī)排序。
代碼實(shí)現(xiàn):
function shuffle(array){ let res = [], random; while(array.length>0){ random = Math.floor(Math.random()*array.length); res.push(array[random]); array.splice(random, 1); } return res; } console.log(shuffle([1,2,3,4,5]));
3.洗牌算法深入分析
思路:我有一副牌,隨機(jī)抽取牌,舊的牌數(shù)量相應(yīng)減少!
function shuffle(m) //洗牌 //抽牌法 { //生成m張牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //每次抽出一張牌,需要遍歷整個數(shù)組,所以很耗時。 var arr2 = new Array(); for (var i=m; i>0; i–) { var rnd = Math.floor(Math.random()*i); arr2.push(arr[rnd]); arr.splice(rnd,1); } return arr2; }
但是這樣的話,因?yàn)閿?shù)組如果很大的話,刪除中間的某個元素,會導(dǎo)致后面的數(shù)據(jù)被執(zhí)行,會對性能影響很大。
我們刪除那個元素的目的就是為了不產(chǎn)生空牌。
除了刪除那個元素之外,我們是不是還有其它方式來去除空牌?
只需把最后一張未抽的牌放在那個抽走的位置上就可以了。
順著這個思路我們可以優(yōu)化成這樣:
代碼如下:
function shuffle_pick(m) //洗牌 //抽牌法優(yōu)化牌 { //生成m張牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //每次抽出一張牌,放在另一堆。把最后一張未抽的牌放在空位子上。 var arr2 = new Array(); for (var i=m; i>0;) { var rnd = Math.floor(Math.random()*i); arr2.push(arr[rnd]); arr[rnd] = arr[–i]; } return arr2; }
除了抽牌思路,我們還可以用換牌思路:
“隨機(jī)交換兩個位置,共交換n次,n越大,越接近隨機(jī)”。
順著這個思路,做一點(diǎn)小調(diào)整就可以了:第i張與任意一張牌換位子,換完一輪即可。
代碼如下:
function shuffle_swap(m) //洗牌 //換牌法 { //生成m張牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //第i張與任意一張牌換位子,換完一輪即可 for (var i=0; i<m; i++) { var rnd = Math.floor(Math.random()*(i+1)), temp = arr[rnd]; arr[rnd] = arr[i]; arr[i]=temp; } return arr; }
除了抽牌與換牌的思路,我們還可以用插牌的思路:先有一張牌,第二張牌有兩個位置可隨機(jī)插入(第一張牌前,或后),第三張牌有三個位置可隨機(jī)插入(放在后面,或插在第一位,或插在第二位),依此類推
代碼如下:
function shuffle_insert_1(m) //洗牌 //插牌法 { //每次生成一張最大的牌,插在隨機(jī)的某張牌前。因?yàn)橐跀?shù)組里插入元素,把后面的所有元素向后擠一位,所以很耗時。 var arr = [0]; for (var i=1; i<m; i++) { arr.splice(Math.floor(Math.random()*(i+1)),0,i); } return arr; }
以上的代碼也會有一些問題:就是隨著牌數(shù)的增多,插牌變得越來越困難,因?yàn)椴迮茣?dǎo)致后面的很多牌都往后推一步。
當(dāng)然,我們也可以適當(dāng)?shù)膬?yōu)化一下:先有n-1張牌,第n張牌放在最后,然后與任意一張牌互換位置。
代碼如下:
function shuffle_insert(m) //洗牌 //插牌法優(yōu)化版,可以用數(shù)學(xué)歸納法證明,這種洗牌是均勻的。 { //每次生成一張最大的牌,與隨機(jī)的某張牌換位子 var arr = new Array(m); arr[0] = 0; for (var i=1; i<m; i++) { var rnd = Math.floor(Math.random()*(i+1)); arr[i] = arr[rnd]; arr[rnd] = i; } return arr; }
全部代碼
代碼如下:
<html> <head> <meta http-equiv=”Content-Type” content=”text/html; charset=gb2312″> <title>JK:javascript 洗牌算法 </title> </head> <body> <script type=”text/javascript”> function shuffle_pick_1(m) //洗牌 //抽牌法 { //生成m張牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //每次抽出一張牌,放在另一堆。因?yàn)橐跀?shù)組里抽出元素,把后面的所有元素向前拉一位,所以很耗時。 var arr2 = new Array(); for (var i=m; i>0; i–) { var rnd = Math.floor(Math.random()*i); arr2.push(arr[rnd]); arr.splice(rnd,1); } return arr2; } function shuffle_pick(m) //洗牌 //抽牌法優(yōu)化牌 { //生成m張牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //每次抽出一張牌,放在另一堆。把最后一張未抽的牌放在空位子上。 var arr2 = new Array(); for (var i=m; i>0;) { var rnd = Math.floor(Math.random()*i); arr2.push(arr[rnd]); arr[rnd] = arr[–i]; } return arr2; } function shuffle_swap(m) //洗牌 //換牌法 { //生成m張牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //第i張與任意一張牌換位子,換完一輪即可 for (var i=0; i<m; i++) { var rnd = Math.floor(Math.random()*(i+1)), temp = arr[rnd]; arr[rnd] = arr[i]; arr[i]=temp; } return arr; } function shuffle_insert_1(m) //洗牌 //插牌法 { //每次生成一張最大的牌,插在隨機(jī)的某張牌前。因?yàn)橐跀?shù)組里插入元素,把后面的所有元素向后擠一位,所以很耗時。 var arr = [0]; for (var i=1; i<m; i++) { arr.splice(Math.floor(Math.random()*(i+1)),0,i); } return arr; } function shuffle_insert(m) //洗牌 //插牌法優(yōu)化版,可以用數(shù)學(xué)歸納法證明,這種洗牌是均勻的。 { //每次生成一張最大的牌,與隨機(jī)的某張牌換位子 var arr = new Array(m); arr[0] = 0; for (var i=1; i<m; i++) { var rnd = Math.floor(Math.random()*(i+1)); arr[i] = arr[rnd]; arr[rnd] = i; } return arr; } //alert(shuffle_pick(10)) var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert], funcNames = [“抽牌”, “抽牌優(yōu)化”, “換牌”, “插牌”, “插牌優(yōu)化”] m = 10000, times=[]; for(var i = 0; i < funcs.length; i++){ var d0= new Date(); funcs[i](m); funcNames[i] = (new Date() – d0) + ‘\t' + funcNames[i]; } alert(funcNames.join(‘\n')); </script> </body> </html>
到此這篇關(guān)于JS實(shí)現(xiàn)數(shù)組隨機(jī)排序的方法詳解的文章就介紹到這了,更多相關(guān)JS數(shù)組隨機(jī)排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
JS中的6種打斷點(diǎn)的方式實(shí)例總結(jié)
斷點(diǎn)調(diào)試是啥?難不難? 斷點(diǎn)調(diào)試其實(shí)并不是多么復(fù)雜的一件事,簡單的理解無外呼就是打開瀏覽器,打開sources找到j(luò)s文件,在行號上點(diǎn)一下罷了,下面這篇文章主要給大家介紹了關(guān)于JS中6種打斷點(diǎn)方式的相關(guān)資料,需要的朋友可以參考下2022-04-04JavaScript實(shí)現(xiàn)父子dom同時綁定兩個點(diǎn)擊事件,一個用捕獲,一個用冒泡時執(zhí)行順序的方法
這篇文章主要介紹了JavaScript實(shí)現(xiàn)父子dom同時綁定兩個點(diǎn)擊事件,一個用捕獲,一個用冒泡時執(zhí)行順序的方法,涉及javascript事件的觸發(fā)與執(zhí)行原理及相關(guān)操作技巧,需要的朋友可以參考下2017-03-03使用js實(shí)現(xiàn)將后臺傳入的json數(shù)據(jù)放在前臺顯示
今天小編就為大家分享一篇使用js實(shí)現(xiàn)將后臺傳入的json數(shù)據(jù)放在前臺顯示,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2018-08-08自己封裝的javascript事件隊(duì)列函數(shù)版
這篇文章主要介紹了自己封裝的javascript事件隊(duì)列函數(shù)版,兼容了大部份瀏覽器,需要的朋友可以參考下2014-06-06淺談javascript中的 “ && ” 和 “ || ”
本文主要介紹了Javascript中的 “ && ” 和 “ || ”的相關(guān)知識。具有很好的參考價值,下面跟著小編一起來看下吧2017-02-02使用JS進(jìn)行目錄上傳(相當(dāng)于批量上傳)
腳本使用了WScript.Shell和Scripting.FileSystemObject的組件,所以必須要在IE下面和打開安全選項(xiàng)中運(yùn)行; 另外還用到了Jquery. 代碼只是客戶端代碼, 至于服務(wù)器的接收代碼網(wǎng)上好多了2010-12-12JavaScript Array.flat()函數(shù)用法解析
這篇文章主要介紹了JavaScript Array.flat()函數(shù)用法解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-09-09