JavaScript排序算法動畫演示效果的實現(xiàn)方法
之前在知乎看到有人在問 自己寫了一個冒泡排序算法如何用HTML,CSS,JavaScript展現(xiàn)出來排序過程。 感覺這個問題還挺有意思 。前些時間就來寫了一個。這里記錄一下實現(xiàn)過程。
基本的思想是把排序每一步的時候每個數(shù)據(jù)的值用DOM結(jié)構(gòu)表達出來。
問題一:如何將JavaScript排序的一步步進程展現(xiàn)出來?
我試過的幾種思路:
1.讓JavaScript暫停下來,慢下來。
JavaScript排序是很快的,要我們?nèi)庋勰芸吹剿膶崿F(xiàn)過程,我首先想到的是讓排序慢下來。 排序的每一個循環(huán)都讓它停300ms然后再繼續(xù)進行。 怎么樣才能停下來呢。查了一下JavaScript貌似沒有sleep()這樣的函數(shù)。暫停做不到,但是可以想辦法讓實現(xiàn)跟暫停差不多的效果。比如在循環(huán)里做一些無關(guān)的事情 。
首先嘗試了讓while(true)來一直執(zhí)行一個空操作。執(zhí)行一段時間再回到排序邏輯。代碼大致是這樣:
for (var i = 0; i < 3; i++) { document.writeln(i); //DOM操作 var now = new Date().getTime(); while(new Date().getTime() - now < 3000){} }
慢是慢下來了。不過太耗資源,排序進行過程中dom并不會有任何改變,直到排序結(jié)束, DOM會變成排序好之后的樣子。 但是如果設(shè)置斷點一步步執(zhí)行的時候 又可以看到一步步的排序變化。估計是因為這個操作太耗資源導(dǎo)致瀏覽器下達了一個DOM操作的命令但是一直騰不出資源來進行DOM操作。所以真正DOM操作的時候在js代碼執(zhí)行結(jié)束之后。
所以讓JavaScript排序慢來來還是沒有實現(xiàn)。
另一種讓JavaScript暫停下來的思路:
寫這個文章的時候又想到一種方法來讓JavaScript停下來。 那就是AJAX的同步請求,以及超時操作。 也就是在要停下來的地方放一個AJAX請求,同步請求, 然后設(shè)置超時。超時的時間就是我們要暫停的時間。為了避免在到達超時請求之前服務(wù) 器就返回了我們的AJAX請求??梢栽诜?wù)端運行類似 sleep()的程序 。從而保證AJAX不會返回。直接超時然后返回到我們的循環(huán)。不過這只是個設(shè)想。有興趣的可以去嘗試一下。
2.閉包和定時器。 這種思路不需要讓排序過程慢下來。而是使用閉包緩存排序過程中數(shù)組的變化。然后使用setTimeout來確定展示每一個數(shù)組狀態(tài)的順序。在排序循環(huán)中放入類似下面的代碼。
(function(){ var theArr = arr.slice();//當前數(shù)組狀態(tài)的備份 setTimeout(function(){ bubbleSortDom(theArr);//排序的DOM操作。 },500*timeCount); timeCount++;//定時器的順序。 })();
不過后來發(fā)現(xiàn)這樣子寫的話代碼量會比較大,邏輯有修改的話要修改的地方會有點多。局限性很多,比如要實現(xiàn)排序動畫加快或減慢操作幾乎是很困難的。所以還要另想辦法。
3.緩存排序中的數(shù)組狀態(tài)。
也就是在排序過程中。將數(shù)組的每一輪循環(huán)的狀態(tài)保存到一個數(shù)組。然后再用這個數(shù)組依次將排序狀態(tài)保存下來。 只需要在排序中加入一句就行。
this.pushHis(arr.slice(),i-1,j,k,temp);
這樣就只需要一個setInterval()就可以了。并且可以很方便的實現(xiàn)動畫的加快與減慢。邏輯也比較好理解 。
問題二:如何實現(xiàn)JavaScript排序動畫的加快與減慢。
我們問題一使用的第三種方法。 得到一個保存了每一步排序狀態(tài)的數(shù)組arr。 然后我們可以使用一個setInterval()定時器一步步展現(xiàn)排序狀態(tài)。 如果要加快速度或減慢速度。就clearInterval(),修改定時器的執(zhí)行間隔,重新setInterval(),從前一個定時器執(zhí)行到數(shù)組中的位置開始執(zhí)行。
問題三:對于使用遞歸實現(xiàn)的數(shù)組怎么辦? 不是在原數(shù)組上進行操作的怎么辦?
使用遞歸實現(xiàn)的排序。 可能并沒有在一個數(shù)組上進行操作,只是最后返回一個排序好的數(shù)組出來。那么我們要如何獲得排序中的數(shù)組的完整狀態(tài)呢。
比如快速排序。
最開始不考慮動畫,我的實現(xiàn)是這樣的:
function quickSort(arr){ var len = arr.length,leftArr=[],rightArr=[],tag; if(len<2){ return arr; } tag = arr[0]; for(i=1;i<len;i++){ if(arr[i]<=tag){ leftArr.push(arr[i]) }else{ rightArr.push(arr[i]); } } return quickSort(leftArr).concat(tag,quickSort(rightArr)); }
然后為了考慮動畫,我改寫了它的邏輯,讓它在同一個數(shù)組上進行了實現(xiàn)。 其實是在遞歸的時候傳入了當前的的子數(shù)組在原數(shù)組中的起始位置。從而在原數(shù)組上進行了操作。
用了兩種方法來實現(xiàn)方式。在排序邏輯上略有不同。
第一種是先跟遠處的對比。遇到比自己小的放到自己前面去。循環(huán)序號+1。比自己大的放到當前排序子數(shù)組的最后面去,循環(huán)序號不變。直到排列完成。
這種方法的缺點是即使是一個有序數(shù)組。它也會重新排。
第二種方法是 除了標記位,再設(shè)置一個對比位。 遇到比自己小的,放到前面去,標記位的位置+1,標記位與對比位之間所有的往后面移動一個位置。
遇到比自己大的。標記位不變,對比位+1。
這種方法的缺點是對數(shù)組進行的操作太多。優(yōu)點是對有序數(shù)組不會再排。
方式一:
function quickSort(arr,a,b,qArr){ var len = arr.length,leftArr=[],rightArr=[],tag,i,k,len_l,len_r,lb,ra,temp; if(a == undefined && b == undefined){ a = 0; b= arr.length-1;//初始化起始位置。 } if(qArr == undefined){ qArr = arr.slice(); } if((len == 2 && arr[0] == arr[1])||len<2){ return arr; } tag = qArr[a]; for (i = 1; i < len;) { if(qArr[a+i]<=tag){ leftArr.push(qArr[a+i]); qArr[a+i-1] = qArr[a+i]; qArr[a+i] = tag; k = a+i; i++; }else{ if(leftArr.length+rightArr.length == len-1){ break; } temp = qArr[a+i]; qArr[a+i] = qArr[b-rightArr.length]; qArr[b-rightArr.length] = temp; rightArr.push(temp); k = a+i-1; } this.pushHis(qArr.slice(),a,b,k); } len_l = leftArr.length; len_r = rightArr.length; if(len_l== 0){ lb = a; }else{ lb = a+len_l -1; this.sort(leftArr,a,lb,qArr); } if(len_r == 0){ ra = b; }else{ ra = b + 1 - len_r; this.sort(rightArr,ra,b,qArr) } return qArr }
方式二:
function quickSort2(arr,a,b,qArr){ var len = arr.length,leftArr=[],rightArr=[],tag,i,j,k,temp,len_l,len_r,lb,ra; if(a == undefined && b == undefined){ a = 0; b= arr.length-1;//初始化起始位置。 } if(qArr == undefined){ qArr = arr.slice(); } if(len<2){ return arr; } if(len == 2 && arr[0] == arr[1]){ return arr; } tag = qArr[a]; for (i = 1,k = 0; i < len;) { if(qArr[a+i]>=tag){ rightArr.push(qArr[a+i]); i++; }else{ temp = qArr[a+i]; for(j = a+i;j>a+k;j--){ qArr[j] = qArr[j-1]; // this.pushHis(qArr.slice(),a,b,a+k); } qArr[a+k] = temp; leftArr.push(temp); k++; i++; } this.pushHis(qArr.slice(),a,b,a+k,i-1); } len_l = leftArr.length; len_r = rightArr.length; if(len_l== 0){ lb = a; }else{ lb = a+len_l -1; this.sort(leftArr,a,lb,qArr); } if(len_r == 0){ ra = b; }else{ ra = b + 1 - len_r; this.sort(rightArr,ra,b,qArr) } return qArr; }
具體的不同下面會有動畫演示。
問題四:動畫的流暢。
排序動畫的DOM操作是很多的很快的。這里我做的優(yōu)化只是讓每一個排序步驟只涉及一個DOM操作。 全部由JavaScript拼接好,一次替換。類似下面的代碼。
效果圖:
主要實現(xiàn)了:
冒泡排序JavaScript動畫演示
插入排序JavaScript動畫演示
選擇排序JavaScript動畫演示
快速排序JavaScript動畫演示
歸并排序JavaScript動畫演示
希爾排序JavaScript動畫演示
以上就是小編為大家?guī)淼腏avaScript排序算法動畫演示效果的實現(xiàn)方法全部內(nèi)容了,希望大家多多支持腳本之家~
相關(guān)文章
JS控制圖片翻轉(zhuǎn)示例代碼(兼容firefox,ie,chrome)
本篇文章主要介紹了JS控制圖片翻轉(zhuǎn)示例代碼(兼容firefox,ie,chrome) 需要的朋友可以過來參考下,希望對大家有所幫助2013-12-12CocosCreator骨骼動畫之龍骨DragonBones
這篇文章主要介紹了怎么在CocosCreator中使用骨骼動畫龍骨DragonBones,對骨骼動畫感興趣的同學(xué),可以試一下2021-04-04JavaScript實現(xiàn)多個重疊層點擊切換效果的方法
這篇文章主要介紹了JavaScript實現(xiàn)多個重疊層點擊切換效果的方法,實例分析了javascript實現(xiàn)點擊切換效果的相關(guān)技巧,需要的朋友可以參考下2015-04-04JavaScript利用Canvas實現(xiàn)粒子動畫倒計時
粒子動畫就是頁面上通過發(fā)射許多微小粒子來表示不規(guī)則模糊物體。本文將利用canvas實現(xiàn)酷炫的粒子動畫倒計時,感興趣的小伙伴可以嘗試一下2022-12-12