DIV CSS 佈局教程網

 DIV+CSS佈局教程網 >> 網頁腳本 >> JavaScript入門知識 >> JavaScript基礎知識 >> 冒泡排序算法可視化
冒泡排序算法可視化
編輯:JavaScript基礎知識     

在百度前端技術學院的任務列表那裡看到了有一個任務是要求用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

總結

看起來很酷炫對不對?不過快排的可視化實現不出來讓我感覺很是郁悶啊,看來基礎還是不行還需要繼續努力了。

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