氣泡排序：BubbleSort

基本概念

氣泡排序的基本概念是：依次比較相鄰的兩個數，將大數放在前面，小數放在後面。即首先比較第1個和第2個數，將大數放前，小數放後。然後比較第2個數和第3個數，將大數放前，小數放後，如此繼續，直至比較最後兩個數，將大數放前，小數放後，此時第一趟結束，在最後的數必是所有數中的最小數。重複以上過程，仍從第一對數開始比較（因為可能由於第2個數和第3個數的交換，使得第1個數不再大於第2個數），將大數放前，小數放後，一直比較到最小數前的一對相鄰數，將大數放前，小數放後，第二趟結束，在倒數第二個數中得到一個新的最小數。如此下去，直至最終完成排序。

由於在排序過程中總是大數往前放，小數往後放，相當於氣泡往上升，所以稱作氣泡排序。

用二重迴圈實現，外迴圈變數設為i，內迴圈變數設為j。外迴圈重複9次，內迴圈依次重複9，8，...，1次。每次進行比較的兩個元素都是與內迴圈j有關的，它們可以分別用a[j]和a[j+1]標識，i的值依次為1,2,...,9，對於每一個i,j的值依次為1,2,...10-i。

產生

在許多程式設計中，我們需要將一個數列進行排序，以方便統計，常見的排序方法有氣泡排序，二叉樹排序，選擇排序等等。而氣泡排序一直由於其簡潔的思想方法和比較高的效率而倍受青睞。

排序過程

設想被排序的陣列R［1..N］垂直豎立，將每個資料元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則，從下往上掃描陣列R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反覆進行，直至最後任何兩個氣泡都是輕者在上，重者在下為止。

演算法示例

4913131313131313

3849272727272727

6538493838383838

9765384949494949

7697654949494949

1376976565656565

2727769776767676

4949497697979797

ProcedureBubbleSort(VarR:FileType)//從下往上掃描的起泡排序//

Begin

ForI:=1ToN-1Do//做N-1趟排序//

begin

NoSwap:=True;//置未排序的標誌//

ForJ:=N-1DownTo1Do//從底部往上掃描//

begin

IfR[J+1]<R[J]Then//交換元素//

begin

Temp:=R[J+1];R[J+1:=R[J];R[J]:=Temp;

NoSwap:=False

end;

end;

IfNoSwapThenReturn//本趟排序中未發生交換，則終止演算法//

end

End;//BubbleSort//

該演算法的時間複雜性為O(n2),演算法為穩定的排序方

氣泡排序演算法具體程式碼

#include<iostream.h>

voidBubbleSort(int*pData,intCount)

{

intiTemp;

for(inti=1;i<Count;i++)

{

for(intj=Count-1;j>=i;j--)

{

if(pData[j]<pData[j-1])

{

iTemp=pData[j-1];

pData[j-1]=pData[j];

pData[j]=iTemp;

}

}

}

}

voidmain()

{

intdata[]={10,9,8,7,6,5,4};

BubbleSort(data,7);

for(inti=0;i<7;i++)

cout<<data<<"";

cout<<"\n";

}

氣泡排序Ruby程式碼

defbubble(arr)

(arr.length-1).downto(1)do|j|

a1=arr.dup

j.timesdo|i|

ifarr>arr[i+1]

arr,arr[i+1]=arr[i+1],arr

end

end

breakifa1==arr

end

arr

end

氣泡排序法的改進

比如用氣泡排序將4、5、7、1、2、3這6個數排序。在該列中，第二趟排序結束後，陣列已排好序，但計算機此時並不知道已經反排好序，計算機還需要進行一趟比較，如果這一趟比較，未發生任何資料交換，則知道已排序好，可以不再進行比較了。因而第三趟比較還需要進行，但第四、五趟比較則是不必要的。為此，我們可以考慮程式的最佳化。

為了標誌在比較中是否進行了，設一個布林量flag。在進行每趟比較前將flag置成true。如果在比較中發生了資料交換，則將flag置為false，在一趟比較結束後，再判斷flag，如果它仍為true（表明在該趟比較中未發生一次資料交換）則結束排序，否則進行下一趟比較。

效能分析

若記錄序列的初始狀態為"正序"，則氣泡排序過程只需進行一趟排序，在排序過程中只需進行n-1次比較，且不移動記錄；反之，若記錄序列的初始狀態為"逆序"，則需進行n(n-1)/2次比較和記錄移動。因此氣泡排序總的時間複雜度為O(n*n)。