DIV CSS 佈局教程網

JavaScript 排序算法動畫演示效果的實現思路
編輯:關於JavaScript     

之前在知乎看到有人提問:自己寫了一個冒泡排序算法,如何用 HTML、CSS、JavaScript 把排序過程展現出來?感覺這個問題挺有意思,前陣子就動手寫了一個,這裡記錄一下實現過程。

基本思想是:把排序每一步中每個數據的值,用 DOM 結構表達出來。

問題一:如何把 JavaScript 排序的每一步進程展現出來?

我嘗試過的幾種思路:

1. 讓 JavaScript 慢下來、停下來。

JavaScript 排序很快,要肉眼看清過程,首先想到的就是讓它慢下來,比如每個循環停 300ms 再繼續。但 JavaScript 並沒有 sleep() 這樣的函數,於是換個思路,比如在循環裡做一些無關的事情來達到類似「暫停」的效果。

首先嘗試用 while(true) 一直執行空操作,執行一段時間再回到排序邏輯,代碼大致如下:

 for (var i = 0; i < 3; i++) { document.writeln(i); //DOM操作 var now = new Date().getTime(); while(new Date().getTime() - now < 3000){} }

慢是慢下來了,但太耗資源,而且排序過程中 DOM 並不會有任何改變,直到排序結束才會變成排好序的樣子;可一旦設置斷點單步執行,又能看到一步步的變化。估計是因為這個空循環太佔用資源,浏覽器下達了 DOM 操作命令卻一直騰不出資源執行,導致真正的 DOM 操作被推到了 js 代碼執行結束之後。所以,單純讓排序變慢並沒有真正達到目的。

另一種讓 JavaScript 停下來的思路:

寫這篇文章時又想到一種方法——AJAX 的同步請求加超時操作。也就是在要暫停的地方放一個同步 AJAX 請求並設置超時,超時時間就是我們想暫停的時長。為了避免請求在超時前就返回,可以在服務端運行類似 sleep() 的程序,保證 AJAX 不會提前返回,直接等到超時再回到循環。這只是個設想,感興趣的可以試試。

2. 閉包和定時器。

這種思路不需要讓排序變慢,而是用閉包緩存排序過程中數組的變化,再用 setTimeout 控制每一步的展示順序。在排序循環中放入類似下面的代碼:

 (function(){ var theArr = arr.slice();//當前數組狀態的備份 setTimeout(function(){ bubbleSortDom(theArr);//排序的DOM操作。 },500*timeCount); timeCount++;//定時器的順序。 })(); 

但後來發現這樣寫代碼量偏大,邏輯一旦修改要動的地方也多,局限性大(比如想實現動畫加速或減速幾乎很難),所以還得另尋他法。

3. 緩存排序中的數組狀態。

也就是在排序過程中,把每一輪循環的數組狀態保存到一個數組裡,之後再用這個數組依次重現排序狀態。只需在排序中加入一句:

 this.pushHis(arr.slice(),i-1,j,k,temp);

這樣就只需要一個 setInterval() 即可,而且能很方便地實現動畫的加速與減速,邏輯也更清晰。

問題二:如何實現排序動畫的加速與減速?

用問題一的第三種方法,得到一個保存了每一步狀態的數組 arr,再用一個 setInterval() 逐步展示。若要加減速,只需 clearInterval(),修改定時器的執行間隔,重新 setInterval(),並從上一個定時器執行到的位置接着往下走即可。

問題三:對於用遞歸實現、並非在原數組上操作的排序怎麼辦?

遞歸實現的排序,可能並不是在單個數組上操作,而只是最後返回一個排好序的數組。那要如何拿到排序過程中的完整狀態呢?

比如快速排序。

最開始不考慮動畫時,我的實現是這樣的:

 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)); }

為了配合動畫,我改寫了它的邏輯,讓它在同一個數組上操作——本質是在遞歸時傳入當前子數組在原數組中的起始位置,從而直接在原數組上進行交換。

我用了兩種實現方式,排序邏輯略有不同。

第一種先跟遠處的元素對比:遇到比自己小的就放到前面,循環序號 +1;遇到比自己大的就放到當前子數組的最後面,循環序號不變,直到排列完成。缺點是即使本來就是有序數組,它也會重排一遍。

第二種除了標記位,再設一個對比位:遇到比自己小的放到前面,標記位 +1,並把標記位與對比位之間的元素整體後移一位;遇到比自己大的,標記位不變,對比位 +1。缺點是對數組的操作較多,優點是對有序數組不會重排。

方式一:

 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 操作又多又快,我在這裡做的優化,是讓每一個排序步驟只涉及一次 DOM 操作——全部由 JavaScript 拼接好後一次性替換,類似下面這種做法。

效果圖:

主要實現了:

冒泡排序 JavaScript 動畫演示
插入排序 JavaScript 動畫演示
選擇排序 JavaScript 動畫演示
快速排序 JavaScript 動畫演示
歸並排序 JavaScript 動畫演示
希爾排序 JavaScript 動畫演示

以上就是關於 JavaScript 排序算法動畫演示效果的實現思路,希望大家多多支持。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved