Skip to content

[資料結構] 氣泡排序法（Bubble Sort）

氣泡排序法（bubble sort）是大部分人所接觸的第一個排序法，因為它真的是最直覺、最好寫的一種排序方法。

氣泡排序法的原理

之所以稱呼為氣泡排序法，是因為假設如果我們要將一組長度為 n 的陣列從小到大排序，我們是依序比較 0 到 n-1 之間的每個數值，只要當前比對的數值比下一個數值更大，我們就將其交換 —— 一直持續這個過程，越小的數值就像在水裡的氣泡一般，漸漸地浮出到了陣列的開頭。

它的運作原理是這樣的，假設我們的陣列為：

4 5 3 1 2 7 6

那麼首先我們會比較 4 跟 5 這兩數值，由於 4 比 5 更小，故不會進行交換。

下一步我們接著比較 5 跟 3，我們會發現 5 比 3 還要更大，所以應該把 5 跟 3 的位置交換，好讓陣列依照遞增的趨勢排序。現在陣列已經變成了：

4 3 5 1 2 7 6

我們會一直重複這個過程，直到第一輪的順序排完。

4 3 1 2 5 6 7

當然，只有一輪的話通常是無法把整個陣列排序完畢的，我們只能保證最大的值會被推到陣列的最後方。

也就是說，我們下一輪排序的目的就會變成把『次大的值』推到陣列的底部數過來第二個位置…… 依此類推，直到陣列排徐完畢為止。

底下是一段範例程式碼，我也會將其印出。

氣泡排序法範例程式碼

複雜度

是複雜度比較穩定的方法，所需要的額外空間只有 O(1)，但是在較長的陣列中可能比較不適合使用時間複雜度這麼高的排序法。

Time ComplexityO(n^2)
Space ComplexityO(1)


C++ 範例程式碼

#include <iostream>
#include <vector>
using namespace std;


void swap(int* n1, int* n2) {
    int temp = *n1;
    *n1 = *n2;
    *n2 = temp;
}


void printArr(int arr[], int size) {
    for (int i=0; i<size; ++i) {
        cout << arr[i] << " ";
    }

    cout << endl;
}


void bubbleSort(int arr[], int size) {
    // Sort
    for (int i=0; i<size-1; ++i) {
        // Check is swaped in this loop
        bool isSwaped = false;

        for (int j=0; j<size-i-1; ++j) {
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
                isSwaped = true;
            }
        }

        // Print progress
        cout << i+1 << ": ";
        printArr(arr, size);

        if (!isSwaped) break;
    }
}


int main() {
    int arr[] = {4, 5, 3, 1, 2, 7, 6};
    int size = sizeof(arr) / sizeof(arr[0]); 
    bubbleSort(arr, size);

    return 0;
}


Output:

1: 4 3 1 2 5 6 7 
2: 3 1 2 4 5 6 7 
3: 1 2 3 4 5 6 7 
4: 1 2 3 4 5 6 7



Python 範例程式碼

# coding: utf-8


def bubbleSort(arr, size):
    for i in range(size-1):
        # Check the swap exist or not
        isSwaped = False

        for j in range(size-i-1):
            if (arr[j] > arr[j+1]):
                arr[j], arr[j+1] = arr[j+1], arr[j]
                isSwaped = True
        
        # Print progress
        print("{}: {}".format(i+1, arr))

        if not isSwaped:
            break


def main():
    # Init
    arr = [4, 5, 3, 1, 2, 7, 6]
    size = len(arr)

    # Sort
    bubbleSort(arr, size)


if __name__ == "__main__":
    main()


Output:

1: [4, 3, 1, 2, 5, 6, 7]
2: [3, 1, 2, 4, 5, 6, 7]
3: [1, 2, 3, 4, 5, 6, 7]
4: [1, 2, 3, 4, 5, 6, 7]


這真的是最直覺的排序方法之一了。

References

Read More

Tags:

Leave a Reply