JavaScript排序算法動畫演示效果的實現方法

2019-11-20 08:43:42

字體：大中小

來源：轉載

供稿：網友

之前在知乎看到有人在問自己寫了一個冒泡排序算法如何用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操作的命令但是一直騰不出資源來進行DOM操作。所以真正DOM操作的時候在js代碼執行結束之后。
所以讓JavaScript排序慢來來還是沒有實現。

另一種讓JavaScript暫停下來的思路：

寫這個文章的時候又想到一種方法來讓JavaScript停下來。那就是AJAX的同步請求，以及超時操作。也就是在要停下來的地方放一個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()就可以了。并且可以很方便的實現動畫的加快與減慢。邏輯也比較好理解。

問題二：如何實現JavaScript排序動畫的加快與減慢。

我們問題一使用的第三種方法。得到一個保存了每一步排序狀態的數組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拼接好，一次替換。類似下面的代碼。

效果圖：