氣泡排序演算法，C語言氣泡排序演算法詳解

氣泡排序是最簡單的排序方法，理解起來容易。雖然它的計算步驟比較多，不是最快的，但它是最基本的，初學者一定要掌握。

氣泡排序的原理是：從左到右，相鄰元素進行比較。每次比較一輪，就會找到序列中最大的一個或最小的一個。這個數就會從序列的最右邊冒出來。

以從小到大排序為例，第一輪比較後，所有數中最大的那個數就會浮到最右邊；第二輪比較後，所有數中第二大的那個數就會浮到倒數第二個位置……就這樣一輪一輪地比較，最後實現從小到大排序。

比如對下面這個序列進行從小到大排序：

90  21  132  -58  34

第一輪：
1) 90 和 21比，90>21，則它們互換位置：

21  90  132  -58  34

2) 90 和 132 比，90<132，則不用交換位置。
3）132 和 –58 比，132>–58，則它們互換位置：

21  90  -58  132  34

4）132 和 34 比，132>34，則它們互換位置：

21  90  -58  34  132

到此第一輪就比較完了。第一輪的結果是找到了序列中最大的那個數，並浮到了最右邊。

比較時，每輪中第 n 次比較是新序列中第 n 個元素和第 n+1 個元素的比較（假如 n 從 1 開始）。

第二輪：
1) 21 和 90 比，21<90，則不用交換位置。
2) 90 和 –58 比，90>–58，則它們互換位置：

21  -58  90  34  132

3) 90 和 34 比，90>34，則它們互換位置：

21  -58  34  90  132

到此第二輪就比較完了。第二輪的結果是找到了序列中第二大的那個數，並浮到了最右邊第二個位置。

第三輪：
1) 21 和 –58 比，21>–58，則它們互換位置：

-58  21  34  90  132

2) 21 和 34 比，21<34，則不用交換位置。

到此第三輪就比較完了。第三輪的結果是找到了序列中第三大的那個數，並浮到了最右邊第三個位置。

第四輪：
1) –58 和 21 比，–58<21，則不用交換位置。

至此，整個序列排序完畢。從小到大的序列就是“–58 21 34 90 132”。從這個例子中還可以總結出，如果有 n 個資料，那麼只需要比較 n–1 輪。而且除了第一輪之外，每輪都不用全部比較。因為經過前面輪次的比較，已經比較過的輪次已經找到該輪次中最大的數並浮到右邊了，所以右邊的數不用比較也知道是大的。

下面寫一個程式：

# include <stdio.h>
int main(void)
{
    int a[] = {900, 2, 3, -58, 34, 76, 32, 43, 56, -70, 35, -234, 532, 543, 2500};
    int n;  //存放陣列a中元素的個數
    int i;  //比較的輪數
    int j;  //每輪比較的次數
    int buf;  //交換資料時用於存放中間資料
    n = sizeof(a) / sizeof(a[0]);  /*a[0]是int型, 占4位元組, 所以總的位元組數除以4等於元素的個數*/
    for (i=0; i<n-1; ++i)  //比較n-1輪
    {
        for (j=0; j<n-1-i; ++j)  //每輪比較n-1-i次,
        {
            if (a[j] < a[j+1])
            {
                buf = a[j];
                a[j] = a[j+1];
                a[j+1] = buf;
            }
        }
    }
    for (i=0; i<n; ++i)
    {
        printf("%dx20", a[i]);
    }
    printf("n");
    return 0;
}

輸出結果是：
2500 900 543 532 76 56 43 35 34 32 3 2 -58 -70 -234

程式中，為什麼每輪比較的次數是 j<n–1–i，而不是 j<n–1？

因為氣泡排序有一個特點，這個程式是從大到小排序，所以第一輪排序以後，最小的數就會浮到最右面；第二輪排序以後，第二小的數會浮到倒數第二個位置；第三輪排序以後，第三小的數會浮到倒數第三個位置……也就是說，排序多少輪，就有多少個數位已經按排序要求排好了，它們不需要再比較。寫 j<n–1 也可以，只不過程式在執行時多做了許多無用功。