在百度前端技術學院的任務列表那裡看到了有一個任務是要求用javascript實現可視化的排序算法,感覺很有趣,就稍微研究了一下,本來是想實現冒泡排序算法和快速排序算法的可視化的,可是快速排序在要如何實現可視化這一步上感覺有一點難度,於是就暫時放棄了。
冒泡排序原理
冒泡排序我們應該都不陌生吧?很簡單的兩個for循環就可以實現了,其基本原理是:在一開始的時候,比較第一第二個數,如果如果第一個數比第二個數大的話則交換二者位置,在比較第二個和第三個數,同樣的如果第二個數比第三個數大的話,則交換二者位置,如此重復,所以一趟比較下來就能篩選出最大的一個數並把它排在最後的位置,又因為一個for循環的話只能選出一個最大的數,而我們還需要選出第二大、第三大...到最小的數,所以還需要加一個for循環才能實現我們的目標。用javascript實現就是:
/*冒泡排序*/ function bubbleSort(arr){ if(arr.length<=1){ return arr; }; var temp=0; for(var i=0; i<arr.length; i++){ for(var j=0; j<arr.length-i-1; j++){ if(arr[j]>arr[j+1]){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; }; }; }; return arr; };
可視化原理
接下來就是要用可視化的方式把排序的過程展現出來了。我們可以用這兩種方法去實現它:
1 排序的每一步結束後,我們讓程序暫停一下運行(javascript沒有sleep函數,我們需要自己去實現它),這樣子的話,在我們看來排序的過程就是一步一步的進行的,就不會一瞬間就排序結束了。
2 我們可以通過維護一個數組,把每一次排序之後的數組保存起來,在排序算法結束之後,我們再把保存的每一個數組依次繪制出來。我這裡的實現用的就是這種方法。
var snapshots=[]; //快照集合
var timer=null; //定時
var arr=[50,21,5,89,13,35,69,44,60,15,51,80,55,71]; //排序數組
/*冒泡排序*/ function bubbleSort(arr){ if(arr.length<=1){ return arr; }; var temp=0; for(var i=0; i<arr.length; i++){ for(var j=0; j<arr.length-i-1; j++){ if(arr[j]>arr[j+1]){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; snapshots.push(JSON.parse(JSON.stringify(arr))); //<=記錄下快照 }; }; }; return arr; };
Array.prototype.bubbleSort=function(){
return bubbleSort(this);
}
我們設置一個snapshots數組變量,用於記錄下每一次排序之後數組的快照,等排序結束之後,我們就能得到一組記錄下完整的排序過程的數組的快照了,這個時候我們再按照一定的時間間隔依次把這些快照繪制出來,就能實現出排序過程的可視化了。
/*繪圖*/ function painting(){ var container=document.getElementById("container"); var bars=[].slice.call( document.querySelectorAll(".bar") ); //將所有bar元素的集合轉換為數組對象 for(var i=0;i<arr.length;i++){ if(bars.length!=arr.length){ var bar=document.createElement("div"); bar.className="bar"; container.appendChild(bar); }else{ break; //當bar的數量等於數組的長度時,停止創建bar元素 }; }; var snapshot=snapshots.shift() || []; //取出快照記錄數組中的第一條記錄 console.log(snapshot); if(snapshot.length!=0){ for(var i=0; i<bars.length; i++){ bars[i].innerHTML=snapshot[i]; bars[i].style.height=snapshot[i]*5+"px"; bars[i].style.left=(i+1)*50+"px"; }; }else{ clearInterval(timer); //繪制結束 return; }; }; arr.bubbleSort(); //排序 timer=setInterval(painting,200); //定時繪制
效果圖:
附上演示地址:http://jerellin.github.io/visualization.html
總結
看起來很酷炫對不對?不過快排的可視化實現不出來讓我感覺很是郁悶啊,看來基礎還是不行還需要繼續努力了。