JavaScript冒泡排序演算法

via冒泡排序由於比較簡單和容易理解，往往會成為人們首先想到的排序演算法。最基本的想法就是在一次裡面比較兩個數字，並確保他們在移動到其他項目之前有一個正確的順序。在每一關結束，有價值的「排序」到正確的位置，最終只留下其他項目排序。原文來自：http://caibaojian.com/javascript-bubble-sort.html

演算法實作想法

比較第一項和第二項

如果第一項應該在第二項的後面，交換他們

對比第二項和第三項

如果第二項應該在第三項之後，交換他們

持續直到數據結束

這個過程就是重複數次直到數據完全排序完畢，在每一次循環中，由於每一次的最後一項都是正確的排序，所以排序的項就越來越少。為了更好的理解，我們來進行一個陣列對比一下：[3, 2, 4, 5, 1].

例子對比過程

首先是正排序，對比第一項和第二項，由於2比3小，所以3排到後面，結果是[2,3,4,5,1].

第二項和第三項，順序是正確的，無須交換；第三項和第四項也是正確的，無須交換，第四項和第五項交換，結果為[2,3,4,1,5].

再次循環第一項和第二項，依次到第三項和第四項交換，為[2,3,1,4,5]

第三次循環，第二和第三交換為[2,1,3,4,5]

第四次循環，第一和第二交換要為[1,2,3,4,5]

實現冒泡排序的第一步就是創建一個方法來交換數組裡面的兩項，這個方法在很多低效率的排序中是比較常見的。一個簡單的javascript實作程式碼為：

function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

via如上所述，這個排序演算法因為需要多次的排序，效率是比較低的。假設一個陣列有n個項，那麼則需要2的n次方來計算，讓我們來看看這個原文來自：http://caibaojian.com/javascript-bubble-sort.html

正向冒泡演算法

function bubbleSort(items){

    var len = items.length,
        i, j, stop;

    for (i=0; i < len; i++){
        for (j=0, stop=len-i; j < stop; j++){
            if (items[j] > items[j+1]){
                swap(items, j, j+1);
            }
        }
    }

    return items;
}

via外面的循環是控制了循環週期數，裡面的循環則是項與項之間的排序比較。

反向冒泡排序

function bubbleSort(items){
    var len = items.length,
        i, j;

    for (i=len-1; i >= 0; i--){
        for (j=len-i; j >= 0; j--){
            if (items[j] < items[j-1]){
                swap(items, j, j-1);
            }
        }
    }

    return items;
}

via上面兩個程式碼的結果是一樣的，都是從小到大排序，只是循環的順序略有不同，都是正序冒泡。

反序冒泡排序

其實就是判斷大小改變，第一項小於第二項時，交換位置，依次類推。

function bubbleSort2(items){
var len = items.length,
i,j,stop;
for(i=0;i<len; i++){
for(j=0,stop=len-i;j<stop;j++){
if(items[j]<items[j+1]){
swap(items,j,j+1);
}
}
}
return items;
}

總結

via再次說明一下，冒泡排序可能並不適用於你的實際工作中哦，它只是一個簡單的工具幫助我們了解算法並且為進一步獲取更多的知識打下基礎。而我們用得最多的可能是內建的Array.prototype.sort() 原型方法，這是由於它具有更高效率。

更多JavaScript冒泡排序演算法相關文章請關注PHP中文網！