之前在知乎看到有人在問(wèn) 自己寫(xiě)了一個(gè)冒泡排序算法如何用HTML，CSS,JavaScript展現(xiàn)出來(lái)排序過(guò)程。   感覺(jué)這個(gè)問(wèn)題還挺有意思 。前些時(shí)間就來(lái)寫(xiě)了一個(gè)。這里記錄一下實(shí)現(xiàn)過(guò)程。

基本的思想是把排序每一步的時(shí)候每個(gè)數(shù)據(jù)的值用DOM結(jié)構(gòu)表達(dá)出來(lái)。

問(wèn)題一：如何將JavaScript排序的一步步進(jìn)程展現(xiàn)出來(lái)?

我試過(guò)的幾種思路：

1.讓JavaScript暫停下來(lái)，慢下來(lái)。

JavaScript排序是很快的，要我們?nèi)庋勰芸吹剿膶?shí)現(xiàn)過(guò)程，我首先想到的是讓排序慢下來(lái)。 排序的每一個(gè)循環(huán)都讓它停300ms然后再繼續(xù)進(jìn)行。 怎么樣才能停下來(lái)呢。查了一下JavaScript貌似沒(méi)有sleep()這樣的函數(shù)。暫停做不到，但是可以想辦法讓實(shí)現(xiàn)跟暫停差不多的效果。比如在循環(huán)里做一些無(wú)關(guān)的事情 。

首先嘗試了讓while(true)來(lái)一直執(zhí)行一個(gè)空操作。執(zhí)行一段時(shí)間再回到排序邏輯。代碼大致是這樣：

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

慢是慢下來(lái)了。不過(guò)太耗資源，排序進(jìn)行過(guò)程中dom并不會(huì)有任何改變，直到排序結(jié)束， DOM會(huì)變成排序好之后的樣子。  但是如果設(shè)置斷點(diǎn)一步步執(zhí)行的時(shí)候 又可以看到一步步的排序變化。估計(jì)是因?yàn)檫@個(gè)操作太耗資源導(dǎo)致瀏覽器下達(dá)了一個(gè)DOM操作的命令但是一直騰不出資源來(lái)進(jìn)行DOM操作。所以真正DOM操作的時(shí)候在js代碼執(zhí)行結(jié)束之后。
所以讓JavaScript排序慢來(lái)來(lái)還是沒(méi)有實(shí)現(xiàn)。

另一種讓JavaScript暫停下來(lái)的思路：

寫(xiě)這個(gè)文章的時(shí)候又想到一種方法來(lái)讓JavaScript停下來(lái)。 那就是AJAX的同步請(qǐng)求，以及超時(shí)操作。  也就是在要停下來(lái)的地方放一個(gè)AJAX請(qǐng)求，同步請(qǐng)求， 然后設(shè)置超時(shí)。超時(shí)的時(shí)間就是我們要暫停的時(shí)間。為了避免在到達(dá)超時(shí)請(qǐng)求之前服務(wù) 器就返回了我們的AJAX請(qǐng)求。可以在服務(wù)端運(yùn)行類(lèi)似 sleep()的程序 。從而保證AJAX不會(huì)返回。直接超時(shí)然后返回到我們的循環(huán)。不過(guò)這只是個(gè)設(shè)想。有興趣的可以去嘗試一下。

2.閉包和定時(shí)器。 這種思路不需要讓排序過(guò)程慢下來(lái)。而是使用閉包緩存排序過(guò)程中數(shù)組的變化。然后使用setTimeout來(lái)確定展示每一個(gè)數(shù)組狀態(tài)的順序。在排序循環(huán)中放入類(lèi)似下面的代碼。

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

不過(guò)后來(lái)發(fā)現(xiàn)這樣子寫(xiě)的話代碼量會(huì)比較大，邏輯有修改的話要修改的地方會(huì)有點(diǎn)多。局限性很多，比如要實(shí)現(xiàn)排序動(dòng)畫(huà)加快或減慢操作幾乎是很困難的。所以還要另想辦法。

3.緩存排序中的數(shù)組狀態(tài)。  

也就是在排序過(guò)程中。將數(shù)組的每一輪循環(huán)的狀態(tài)保存到一個(gè)數(shù)組。然后再用這個(gè)數(shù)組依次將排序狀態(tài)保存下來(lái)。 只需要在排序中加入一句就行。

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

這樣就只需要一個(gè)setInterval()就可以了。并且可以很方便的實(shí)現(xiàn)動(dòng)畫(huà)的加快與減慢。邏輯也比較好理解 。

問(wèn)題二：如何實(shí)現(xiàn)JavaScript排序動(dòng)畫(huà)的加快與減慢。

我們問(wèn)題一使用的第三種方法。 得到一個(gè)保存了每一步排序狀態(tài)的數(shù)組arr。  然后我們可以使用一個(gè)setInterval()定時(shí)器一步步展現(xiàn)排序狀態(tài)。  如果要加快速度或減慢速度。就clearInterval()，修改定時(shí)器的執(zhí)行間隔，重新setInterval()，從前一個(gè)定時(shí)器執(zhí)行到數(shù)組中的位置開(kāi)始執(zhí)行。

問(wèn)題三：對(duì)于使用遞歸實(shí)現(xiàn)的數(shù)組怎么辦？ 不是在原數(shù)組上進(jìn)行操作的怎么辦？

使用遞歸實(shí)現(xiàn)的排序。 可能并沒(méi)有在一個(gè)數(shù)組上進(jìn)行操作，只是最后返回一個(gè)排序好的數(shù)組出來(lái)。那么我們要如何獲得排序中的數(shù)組的完整狀態(tài)呢。

比如快速排序。

最開(kāi)始不考慮動(dòng)畫(huà)，我的實(shí)現(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));}

然后為了考慮動(dòng)畫(huà)，我改寫(xiě)了它的邏輯，讓它在同一個(gè)數(shù)組上進(jìn)行了實(shí)現(xiàn)。 其實(shí)是在遞歸的時(shí)候傳入了當(dāng)前的的子數(shù)組在原數(shù)組中的起始位置。從而在原數(shù)組上進(jìn)行了操作。

用了兩種方法來(lái)實(shí)現(xiàn)方式。在排序邏輯上略有不同。

第一種是先跟遠(yuǎn)處的對(duì)比。遇到比自己小的放到自己前面去。循環(huán)序號(hào)+1。比自己大的放到當(dāng)前排序子數(shù)組的最后面去，循環(huán)序號(hào)不變。直到排列完成。 
這種方法的缺點(diǎn)是即使是一個(gè)有序數(shù)組。它也會(huì)重新排。

第二種方法是 除了標(biāo)記位，再設(shè)置一個(gè)對(duì)比位。 遇到比自己小的，放到前面去，標(biāo)記位的位置+1，標(biāo)記位與對(duì)比位之間所有的往后面移動(dòng)一個(gè)位置。
遇到比自己大的。標(biāo)記位不變，對(duì)比位+1。
這種方法的缺點(diǎn)是對(duì)數(shù)組進(jìn)行的操作太多。優(yōu)點(diǎn)是對(duì)有序數(shù)組不會(huì)再排。

方式一：

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

具體的不同下面會(huì)有動(dòng)畫(huà)演示。

問(wèn)題四：動(dòng)畫(huà)的流暢。

排序動(dòng)畫(huà)的DOM操作是很多的很快的。這里我做的優(yōu)化只是讓每一個(gè)排序步驟只涉及一個(gè)DOM操作。  全部由JavaScript拼接好，一次替換。類(lèi)似下面的代碼。

效果圖：

主要實(shí)現(xiàn)了：

冒泡排序JavaScript動(dòng)畫(huà)演示
插入排序JavaScript動(dòng)畫(huà)演示
選擇排序JavaScript動(dòng)畫(huà)演示
快速排序JavaScript動(dòng)畫(huà)演示
歸并排序JavaScript動(dòng)畫(huà)演示
希爾排序JavaScript動(dòng)畫(huà)演示

以上就是小編為大家?guī)?lái)的JavaScript排序算法動(dòng)畫(huà)演示效果的實(shí)現(xiàn)方法全部?jī)?nèi)容了，希望大家多多支持武林網(wǎng)~