JavaScript冒泡排序算法

算法實現思路

對比第一項和第二項

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

對比第二項和第三項

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

持續直到數據結束

這個過程就是重復數次直到數據完全排序完畢，在每一次循環中，由于每一次的最后一項都是正確的排序，所以排序的項就越來越少。為了更好的理解，我們來進行一個數組對比一下：[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中文網！

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com