冒泡排序演算法

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

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

冒泡排序

1、排序方法
    　將被排序的記錄數組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據輕氣泡無法在重氣泡之下的原則，從下往上掃描數組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反覆進行，直到最後任何兩個氣泡都是輕者在上，重者在下為止。
（1）初始
　    R[1..n]為無序區。

（2）第一班掃描
　    從無序區底部向上依序比較鄰近的兩個氣泡的重量，若發現輕者在下、重者在上，則交換二者的位置。即依序比較(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；對於每對氣泡(R[j+1]，R[j])，若R[j+1].key    　第一班掃描完畢時，"最輕"的氣泡就飄浮到該區間的頂部，即關鍵字最小的記錄被放在最高位置R[1]上。

（3）第二次掃描
　    掃描R[2..n]。掃描完畢時，"次輕"的氣泡飄浮到R[2]的位置上…
    　最後，經過n-1 趟掃描可得到有序區R[1..n]
  注意：
　   iii分掃描掃描時，R[1..i-1]和R[i..n]分別為目前的有序區和無序區。掃描仍是從無序區底部向上至該區頂部。掃描完畢時，該區中最輕氣泡飄浮到頂部位置R[i]上，結果是R[1..i]變為新的有序區。

2、冒泡排序過程範例
    　對關鍵字序列為49 38 65 97 76 13 27 49的文件進行冒泡排序的過程

3、排序演算法
（1）分析使每一趟排序的流程🠎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 (j=n-1;j>=i；j--) //對目前無序區R[i..n]自下向上掃描
        if(R[j+1].key          R[0]=R[j+1]； //R[0]不是哨兵，只做暫存單位
          R[j+1
        [j]=R[0]；
          exchange=TRUE； //產生了交換，因此交換標誌置為真
              return；
收到