冒泡排序(Bubble Sort)
最簡單的排序方法是冒泡排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對這個(gè)“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個(gè)序列，并時(shí)刻注意兩個(gè)相鄰的元素的順序是否正確。如果發(fā)現(xiàn)兩個(gè)相鄰元素的順序不對，即“輕”的元素在下面，就交換它們的位置。顯然，處理一遍之后，“最輕”的元素就浮到了最高位置；處理二遍之后，“次輕”的元素就浮到了次高位置。在作第二遍處理時(shí)，由于最高位置上的元素已是“最輕”元素，所以不必檢查。一般地，第i遍處理時(shí)，不必檢查第i高位置以上的元素，因?yàn)榻?jīng)過前面i-1遍的處理，它們已正確地排好序。這個(gè)算法可實(shí)現(xiàn)如下。

procedure Bubble_Sort(var L:List);
var
i,j:position;
begin
1 for i:=First(L) to Last(L)-1 do
2 for j:=First(L) to Last(L)-i do
3 if L[j]>L[j+1] then
4 swap(L[j],L[j+1]); //交換L[j]和L[j+1]
end;

上述算法將較大的元素看作較重的氣泡，每次最大的元素沉到表尾。其中First(L)和Last(L)分別表示線性表L的第一個(gè)元素和最后一個(gè)元素的位置，swap(x,y)交換變量x,y的值。上述算法簡單地將線性表的位置當(dāng)作整數(shù)用for循環(huán)來處理，但實(shí)際上線性表可能用鏈表實(shí)現(xiàn)；而且上述算法將線性表元素的值當(dāng)作其鍵值進(jìn)行處理。不過這些并不影響表達(dá)該算法的基本思想。今后如果不加說明，所有的算法都用這種簡化方式表達(dá)。

容易看出該算法總共進(jìn)行了n(n-1)/2次比較。如果swap過程消耗的時(shí)間不多的話，主要時(shí)間消耗在比較上，因而時(shí)間復(fù)雜性為O(n2)。但是如果元素類型是一個(gè)很大的紀(jì)錄，則Swap過程要消耗大量的時(shí)間，因此有必要分析swap執(zhí)行的次數(shù)。

顯然算法Bubble_Sort在最壞情況下調(diào)用n(n-1)/2次Swap過程。我們假設(shè)輸入序列的分布是等可能的?？紤]互逆的兩個(gè)輸入序列L1=k1,k2,..,kn和L2=kn,kn-1,..,k1。我們知道，如果ki>kj，且ki在表中排在kj前面，則在冒泡法排序時(shí)必定要將kj換到ki前面，即kj向前浮的過程中一定要穿過一次ki，這個(gè)過程要調(diào)用一次Swap。對于任意的兩個(gè)元素ki和kj，不妨設(shè)ki>kj，或者在L1中ki排在kj前面，或者L2在中ki排在kj前面，兩者必居其一。因此對于任意的兩個(gè)元素ki和kj，在對L1和L2排序時(shí)，總共需要將這兩個(gè)元素對調(diào)一次。n個(gè)元素中任取兩個(gè)元素有Cn2 種取法，因此對于兩個(gè)互逆序列進(jìn)行排序，總共要調(diào)用Cn2 =n(n-1)/2次Swap，平均每個(gè)序列要調(diào)用n(n-1)/4次Swap。那么算法Bubble_Sort調(diào)用Swap的平均次數(shù)為n(n-1)/4。

可以對冒泡算法作一些改進(jìn)，如果算法第二行的某次內(nèi)循環(huán)沒有進(jìn)行元素交換，則說明排序工作已經(jīng)完成，可以退出外循環(huán)?？梢杂靡粋€(gè)布爾變量來記錄內(nèi)循環(huán)是否進(jìn)行了記錄交換，如果沒有則終止外循環(huán)。

冒泡法的另一個(gè)改進(jìn)版本是雙向掃描冒泡法（Bi-Directional Bubble Sort）。設(shè)被排序的表中各元素鍵值序列為：

483 67 888 50 255 406 134 592 657 745 683

對該序列進(jìn)行3次掃描后會發(fā)現(xiàn)，第3此掃描中最后一次交換的一對紀(jì)錄是L[4]和L[5]：

50 67 255 134 | 406 483 592 657 683 745 888

顯然，第3次掃描(i=3)結(jié)束后L[5]以后的序列都已經(jīng)排好序了，所以下一次掃描不必到達(dá)Last(L)-i=11-4=7，即第2行的for 循環(huán)j不必到達(dá)7，只要到達(dá)4-1=3就可以了。按照這種思路，可以來回地進(jìn)行掃描，即先從頭掃到尾，再從尾掃到頭。這樣就得到雙向冒泡排序算法：

procedure Bi-Directional_Bubble_Sort(var L:List);
var
low,up,t,i:position;
begin
1 low:=First(L);up:=Last(L);
2 while up>low do
begin
3 t:=low;
4 for i:=low to up-1 do
5 if L[i]>L[i+1] then
begin
6 swap(L[i],L[i+1]);
7 t:=i;
end;
8 up:=t;
9 for i:=up downto low+1 do
10 if L[i]< L[i-1] then
begin
11 swap(L[i],L[i-1]);
12 t:=i;
end;
13 low:=t;
end;
end;

算法利用兩個(gè)變量low和up記錄排序的區(qū)域L[low..up]，用變量t 記錄最近一次交換紀(jì)錄的位置，4-7行從前向后掃描，9-12行從后向前掃描，每次掃描以后利用t所記錄的最后一次交換記錄的位置，并不斷地縮小需要排序的區(qū)間，直到該區(qū)間只剩下一個(gè)元素。

直觀上來看，雙向冒泡法先讓重的氣泡沉到底下，然后讓輕的氣泡浮上來，然后再讓較大氣泡沉下去，讓較輕氣泡浮上來，依次反復(fù)，直到排序結(jié)束。

雙向冒泡排序法的性能分析比較復(fù)雜，目前暫缺，那位朋友知道請告訴我。

冒泡排序法和雙向冒泡排序法是原地置換排序法，也是穩(wěn)定排序法，如果算法Bubble_Sort中第3行的比較條件L[j]>L[j+1]改為L[j]>= L[j+1]，則不再是穩(wěn)定排序法。