氣泡排序法(Bubble Sort) - 小殘的程式光廊
文章推薦指數： 80 %
氣泡排序法(Bubble Sort) · 比較相鄰的兩個元素，若前面的元素較大就進行交換。
· 重複進行1的動作直到最後面，最後一個元素將會是最大值。
· 重複進行1,2的 ...
小殘的程式光廊
跳到主文
提供一些演算法、資料結構、程式題目的整理與說明，PHP和JavaScript的基本教學和一些程式相關問題與解法。
部落格全站分類：數位生活
相簿
部落格
留言
名片
公告版位
Nov10Sat201221:17
氣泡排序法(BubbleSort)
簡介
氣泡排序法(BubbleSort)是最容易理解和實作的一種排序演算法，也翻譯作冒泡排序法。
由於它很容易學習，所以也是許多演算法課程中第一個學習的排序演算法。
由於他的演算法過程會將最大的數值移動到陣列最後面，而較小的數值則逐漸的往陣列前端移動，就像有許多氣泡慢慢從底部浮出，因此成為氣泡排序法。
他的運作流程如下：
比較相鄰的兩個元素，若前面的元素較大就進行交換。
重複進行1的動作直到最後面，最後一個元素將會是最大值。
重複進行1,2的動作，每次比較到上一輪的最後一個元素。
重複進行以上動作直到沒有元素需要比較。
流程示意圖：
實作上直接使用迭代法迴圈就可以很容易的完成。
另外可以使用額外的旗標(Flag)來判斷這一輪是否有發生交換情形，若都沒有發生交換表示數列已經是排序好的，即可跳出迴圈，因此最佳時間複雜度是有可能達到O(n)。
分析
最佳時間複雜度：O(n)
平均時間複雜度：O(n^2)
最差時間複雜度：O(n^2)
空間複雜度：O(1)
Stablesort：是
虛擬碼
一般版本
functionsort(list)
//重複N次
fori=0tolist.length-1
//比較到上一輪最後一個
forj=0tolist.length-i-1
iflist[j]>list[j+1]
swap(list[j],list[j+1])
endif
endfor
endfor
endfunction
旗標版本
functionsort(list)
//重複N次
fori=0tolist.length-1
varswapped=false
//比較到上一輪最後一個
forj=0tolist.length-i-1
iflist[j]>list[j+1]
swap(list[j],list[j+1])
swapped=true
endif
endfor
if!swapped
break
endif
endfor
endfunction
語法
C#
一般版本
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
namespaceBubbleSort
{
classBubbleSort
{
publicstaticvoidSort(int[]array)
{
for(inti=array.Length-1;i>0;--i)
for(intj=0;jarray[j+1])
Swap(array,j,j+1);
}
privatestaticvoidSwap(int[]array,intindexA,intindexB)
{
inttmp=array[indexA];
array[indexA]=array[indexB];
array[indexB]=tmp;
}
}
}
旗標版本
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
namespaceBubbleSort
{
classFlagBubbleSort
{
publicstaticvoidSort(int[]array)
{
for(inti=array.Length-1;i>0;--i)
{
boolswapped=false;
for(intj=0;jarray[j+1])
{
Swap(array,j,j+1);
swapped=true;
}
if(!swapped)
break;
}
}
privatestaticvoidSwap(int[]array,intindexA,intindexB)
{
inttmp=array[indexA];
array[indexA]=array[indexB];
array[indexB]=tmp;
}
}
}
Java
一般版本
publicclassBubbleSort{
publicstaticvoidSort(int[]array)
{
for(inti=array.length-1;i>0;--i)
for(intj=0;jarray[j+1])
Swap(array,j,j+1);
}
privatestaticvoidSwap(int[]array,intindexA,intindexB)
{
inttmp=array[indexA];
array[indexA]=array[indexB];
array[indexB]=tmp;
}
}
旗標版本
publicclassFlagBubbleSort{
publicstaticvoidSort(int[]array)
{
for(inti=array.length-1;i>0;--i)
{
booleanswapped=false;
for(intj=0;jarray[j+1])
{
Swap(array,j,j+1);
swapped=true;
}
if(!swapped)
break;
}
}
privatestaticvoidSwap(int[]array,intindexA,intindexB)
{
inttmp=array[indexA];
array[indexA]=array[indexB];
array[indexB]=tmp;
}
}
C++
一般版本
BubbleSort.h
#ifndefBUBBLESORT_H
#defineBUBBLESORT_H
#include
延伸文章資訊
- 1泡沫排序法(Bubble Sort) - HackMD
以升序泡沫排序法來說：將相鄰的元素兩兩比對，若左邊的數比右邊的數大，則將兩數交換，若沒有則換下一個元素對比，做完一輪之後序列中最大的數就會被排到最後一個 ...
- 2[C++] 氣泡排序法(Bubble sort)
氣泡排序的意思，wiki 裡面是這麼說明: 又稱為泡沫排序，是一種簡單的排序演算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序 ...
- 3Bubble Sort 泡泡排序法 - Cedric's 學習備忘錄- 痞客邦
泡泡排序法的原理是將一組數字中的第一位與後一位相比較，若後一位數字較大，則位置對調，再將第二位數與第三位數做比較，若後一數字較大， ...
- 4氣泡排序法(Bubble Sort) - 小殘的程式光廊
氣泡排序法(Bubble Sort) · 比較相鄰的兩個元素，若前面的元素較大就進行交換。 · 重複進行1的動作直到最後面，最後一個元素將會是最大值。 · 重複進行1,2的 ...
- 5Java 泡沫排序法 - 翻轉工作室
所謂排序法（Sort）即是將一大堆資料，利用某一關鍵內容由最大到最小，或最小到最大依序排列。吾人可能會認為排序演算法應該不是很重要才對，如果僅排序 100 筆以下 ...
