氣泡排序演算法的理解

Understanding Bubble Sort Algorithm

氣泡排序法的原理是：在一個原本無序多個數字所組成的列表中，從頭開始將相鄰的數字逐一比較大小，如果是要由小至大排序，前面的數字若是大於後面的數字，則兩者須交換位置。如此相鄰繼續逐一比較下去，就可找到最大數字，無論有無發生交換，該數字最終會被排在最末端的位置。接下來，剛剛找到的最大數字以外的其它數字，再進行新一回的相鄰的數字逐一比較大小。一樣前面的數字若是大於後面的數字，則兩者須互相交換位置，如此相鄰逐一比較下去，就可找到次大的數字，且該數字會被排在倒數第二的位置。以此模式繼續多回比較，最後就可將列表中的數字由小至大排序。

如圖一所示，現在列表中有 5 個數字 {48, 24, 17, 20, 31} 要進行排序，若是採用氣泡排序法，因為相鄰的數字都要進行比較，則第一回要比較 4 次。此數目 4 其實就是這 5 個待排序數字的間隔數。

圖一    5 個數字排序，第一回總共要比較 4 次

如圖二所示，這 5 個數字若是要由小至大排序，則相鄰數字在逐一比較 4 次後，就可找到最大值 48 ，且其經多次交換後就會被排至最末的位置。此時，只剩 4 個小於或等於 48 的數字需要進行新一回的比較。 

圖二    第一回比較情形

圖三    第二回剩 4 個數字要排序，總共要比較 3 次

如圖四所示，第二回相鄰數字逐一比較 3 次後，就可找到次大的數字 31。接下來只剩 3 個數字尚未排序。而這剩下的 3 個數字，只須比較 2 次，就可以找到倒數第三大數字，如圖五所示。

圖四    第二回比較情形

圖五    第三回比較情形

最後一回只剩下兩個數字尚未排序，故只需一次比較，就完成整個列表數字的排序，如圖六所示。

圖六    第四回比較情形

下面以一程式示範氣泡排序法：

 C++

#include <iostream>

using namespace std;

int  number[ ] = { 48, 24, 17, 20, 31 };

void bubble_sort(int x[ ]);

int main() {

    cout << "排序前的陣列元素為：";

    for (int i = 0; i < 5; i++)

        cout << number[i] << " ";

    cout << "\n";

    cout << "排序後的陣列元素為：";

    bubble_sort(number);

    for (int i = 0; i < 5; i++)

        cout << number[i] << " ";

    cout << "\n";

    return 0;

}

void bubble_sort(int x[ ])

{

    int i, j, temp;

    for (i = 4; i >= 1; i--) {                           

        for (j = 0; j <= i - 1; j++) {                 

            if (number[j] > number[j + 1]) {  /* 判斷是否交換位置的條件式 */

                temp = number[j + 1];

                number[j + 1] = number[j];

                number[j] = temp;

            }

        }

    }

}

輸出結果

說明

bubble_sort() 函數內的雙層 for 迴圈是此氣泡排序法的重點。外層 for 迴圈決定每一回的比較次數。所以 for (i = 4; i >=1;i--){ ... } ，控制第一回比較 4 次 ( 5 個數字要進行相鄰比較，間隔數即比較數為 4 ) ，第二回 3 次，．．．，第 4 回 1 次。

內迴圈則是用來實際控制相鄰數字的比較並執行可能需要的交換，但由於陣列的索引值是從 0 開始，因此內迴圈須寫成 for (j = 0; j <= i-1; j++) { ... }。

相關文章

• 陣列 (C++)
• [C++] 陣列基礎練習題