冒泡排序

维基百科，自由的百科全书

冒泡排序（Bubble Sort，台灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。它重複地走訪過要排序的數列，一次比較兩個項目，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要做交換動作，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換的動作慢慢“浮”到數列的頂端。

冒泡排序對 $n$ 個項目需要O( $n 2$ )的比較次數，且可以原地排序。儘管這個演算法是最簡單了解和實作的排序算法之一，但它對於少數元素之外的數列排序是很沒有效率的。

冒泡排序是與插入排序擁有相等的執行時間，但是兩種法在需要的交換動作次數卻很大地不同。在最壞的情况，冒泡排序需要 $O (n 2)$ 交換動作，而插入排序只要最多 $O (n)$ 交換。天真的冒泡排序實作（類似下面）通常會對已經排序好的數列拙劣地執行（ $O (n 2)$ ），而插入排序在這個例子只需要 $O (n)$ 個運算。因此很多現代的演算法教科書避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在內部回圈第一次執行時，使用一個旗標來表示有無需要交換的可能，也有可能把最好的複雜度降低到 $O (n)$ 。在這個情況，在已經排序號的數列就無交換的需要。若在每次走訪數列時，把走訪順序和比較大小反過來，也可以些微地改進效率。有時候稱為往返排序（en:shuttle sort），因為演算法會從數列的一端到另一端之間穿梭往返。

冒泡排序演算法的運作如下：

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
針對所有的元素重複以上的步驟，除了最後一個。
持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

由於它的簡潔，冒泡排序通常被用來對於程式設計入門的學生介紹演算法的概念。

[编辑] 虛擬碼

function bubblesort (A : list[1..n]) {
    var int i, j;
    for i from n downto 1 {
        for j from 1 to i-1 { 
            if (A[j] > A[j+1])
                swap(A[j], A[j+1])
        }
    }
}

[编辑] Pascal碼

Program Bubble_Sort; var

 a:array[1..1000] of longint;
 n,i,j,k,flag:longint;

begin

 readln(n);
 for i:=1 to n do
   read(a[i]);
 i:=1;
 repeat
   flag:=0;
   for j:=n downto i+1 do
     if a[j]<a[j-1] then
     begin
       k:=a[j];
       a[j]:=a[j-1];
       a[j-1]:=k;
                  // Swap A[i] , A[j+1]
       inc(flag);
     end;
   inc(i);
 until (i>=n) or (flag=0);
 writeln('The New Array:');
 for i:=1 to n do
 begin
   write(a[i]:8);
   if i mod 5=0 then writeln;
 end;

End.

要看各種程式語言版本的實際程式碼，請參考Wikisource.

来自“http://zh.wikipedia.org../../../%E5%86%92/%E6%B3%A1/%E6%8E%92/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F.html”

页面分类: 排序算法