排序 - 交換排序 - 冒泡排序（一）

　　交換排序的基本思想是兩兩比較待排序記錄的關鍵字發現兩個記錄的次序相反時即進行交換直到沒有反序的記錄為止

　　應用交換排序基本思想的主要排序方法有冒泡排序和快速排序

　　冒泡排序

　　排序方法

　　將被排序的記錄數組R[n]垂直排列每個記錄R[i]看作是重量為R[i]key的氣泡根據輕氣泡不能在重氣泡之下的原則從

　　下往上掃描數組R凡掃描到違反本原則的輕氣泡就使其向上飄浮如此反復進行直到最後任何兩個氣泡都是輕者在上重者

　　在下為止

　　()初始

　　R[n]為無序區

　　()第一趟掃描

　　從無序區底部向上依次比較相鄰的兩個氣泡的重量若發現輕者在下重者在上則交換二者的位置即依次比較(R[n]R[n

　　])(R[n]R[n])…(R[]R[]);對於每對氣泡(R[j+]R[j])若R[j+]key

　　R[j]的內容。TW.WINGWIT.cOm

　　第一趟掃描完畢時，"最輕"的氣泡就飄浮到該區間的頂部，即關鍵字最小的記錄被放在最高位置R[1]上。

　　(3)第二趟掃描

　　掃描R[2..n]。掃描完畢時，"次輕"的氣泡飄浮到R[2]的位置上……

　　最後，經過n-1 趟掃描可得到有序區R[1..n]

　　注意：

　　第i趟掃描時，R[1..i-1]和R[i..n]分別為當前的有序區和無序區。掃描仍是從無序區底部向上直至該區頂部。掃描完畢時，該

　　區中最輕氣泡飄浮到頂部位置R[i]上，結果是R[1..i]變為新的有序區。

　　2、冒泡排序過程示例

　　對關鍵字序列為49 38 65 97 76 13 27 49 的文件進行冒泡排序的過程【 參見動畫演示 】

　　3、排序算法

　　(1)分析

　　因為每一趟排序都使有序區增加了一個氣泡，在經過n-1趟排序之後，有序區中就有n-1個氣泡，而無序區中氣泡的重量總是大於

　　等於有序區中氣泡的重量，所以整個冒泡排序過程至多需要進行n-1趟排序。

　　若在某一趟排序中未發現氣泡位置的交換，則說明待排序的無序區中所有氣泡均滿足輕者在上，重者在下的原則，因此，冒泡排

　　序過程可在此趟排序後終止。為此，在下面給出的算法中，引入一個布爾量exchange，在每趟排序開始前，先將其置為FALSE。若排

　　序過程中發生了交換，則將其置為TRUE。各趟排序結束時檢查exchange，若未曾發生過交換則終止算法，不再進行下一趟排序。

　　(2)具體算法

　　void BubbleSort(SeqList R)

　　{ //R(l..n)是待排序的文件，采用自下向上掃描，對R做冒泡排序

　　int i，j;

　　Boolean exchange; //交換標志

　　for(i=1;i

　　exchange=FALSE; //本趟排序開始前，交換標志應為假

　　for(j=n-1;j>=i;j--) //對當前無序區R[i..n]自下向上掃描

　　if(R[j+1].key

　　R[0]=R[j+1]; //R[0]不是哨兵，僅做暫存單元

　　R[j+1]=R[j];

　　R[j]=R[0];

　　exchange=TRUE; //發生了交換，故將交換標志置為真

　　}

　　if(!exchange) //本趟排序未發生交換，提前終止算法

　　return;

　　} //endfor(外循環)

　　} //BubbleSort

From:http://tw.wingwit.com/Article/program/sjjg/201311/23802.html