pascal冒泡

冒泡排序，就像將數據比作泡泡，輕的上浮，重的下沉。在第i次排序中，有n-i次將相鄰的數據比較，若符合條件則交換。每一趟交換都會產生至少一個有序數據。

基本介紹

• 中文名：冒泡排序
• 外文名：bubble sort
• 時間複雜度：O(n^2)
• 空間複雜度：O(n)

思想

對1至n個記錄，在第i趟排序中設定標誌flag:=true，未排序的標誌。從下往上掃描，以j作為內層循環變數，共做n-i次比較。在第j趟比較中，若r[j+1]<r[j]則交換，並至flag為false。在一趟排序結束後，若flag為true，則終止排序。

算法

當數據已經從小到大排好序時，此算法只執行一趟冒泡，做n-1次數據比較，不移動對象，這是最好的情形。

最壞的情形是算法執行n-1趟冒泡，第i趟做n-i次比較，進行n-i次交換。這樣在最壞情形下總的數據比較次數KCN和對象移動次數RMN為：

該排序的穩定性較好。但也可以通過刪減把冒泡程式改成不穩定程式。

該程式內容簡短，時間與功效不如簡單排序的另外兩種——選擇排序和插入排序，適合初學者使用。

代碼

此為從小到大排序的程式。

i，j：循環變數flag：狀態指針n：數據數量r：排序數據（數組）temp：交換變數for i:=1 to n-1 do//最多做n－1趟排序  begin　  flag:=true;//至未排序的標誌　  for j:=n-1 downto i do//從底部向上掃描　    if r[j+1]<r[j] then//交換元素　      begin　        temp:=r[j+1];          r[j+1]:=r[j];          r[j]:=temp;　        flag:=false;　      end;      if flag then break;//本趟排序中未發生交換，則終止  end;