2021-01-27

C/C++ bubble sort 泡沫排序法

本篇 ShengYu 介紹 C/C++ 中最簡單經典的泡沫排序法 bubble sort，並且由 C/C++ 來實作泡沫排序法 bubble sort。

如果不想自己刻一個排序法可以使用現成 C 提供的 qsort 或 C++ STL 標準函式庫提供的 std::sort。
以下開始介紹泡沫排序的原理，

泡沫排序法 bubble sort 基本原理

泡沫排序法 bubble sort 的原理是將兩個相鄰的數值相比，假如前一個數值比後一個數值大時，就互相對調，實作時就是使用兩層迴圈，針對該陣列掃兩次，最終將能獲得排序好的升序陣列(由小到大)，若要排程降序的陣列(由大到小)，只需將較大的數值往前交換即可，
讓我來舉個簡單的例子吧！假如今天有一串數字陣列 6 4 8 10 2 要使用泡沫排序 bubble sort，

第一次迴圈排序步驟如下，所以第一次迴圈就能把最大的數值 5 給交換到最後了，剩餘要排序的數值還有 4 個，

第二次迴圈排序步驟如下，第二次迴圈，就把第二大的數值 4 給交換到倒數第二個了，剩餘要排序的數值還有 3 個，

1
2
3

4 6 8 2 10
4 6 8 2 10
4 6 2 8 10

第三次迴圈排序步驟如下，第三次迴圈，就把第三大的數值 3 給交換到倒數第三個了，剩餘要排序的數值還有 2 個，

1 2	4 6 2 8 10 4 2 6 8 10

第四次迴圈排序步驟如下，第四次迴圈，就把第三大的數值 2 給交換到倒數第四個了，剩餘要排序的數值還有 1 個，

1	2 4 6 8 10

迴圈結束，排序完成。

C/C++ 實作泡沫排序法 bubble sort

由上述的簡單例子推演可以了解了泡沫排序 bubble sort 基本原理後，接著就開始練習用 C/C++ 來寫程式，那我們來看看 C/C++ 泡沫排序怎麼寫吧！

cpp-bubble-sort.cpp

// g++ cpp-bubble-sort.cpp -o a.out
#include <stdio.h>

void bubble_sort(int array[], int n) {
    for (int i=0; i<n-1; i++) {
        for (int j=0; j<n-i-1; j++) {
            if (array[j] > array[j+1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

int main() {
    int array[] = {6,4,8,10,2};
    printf("排序前 = ");
    for (int i=0; i<5; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    
    bubble_sort(array, 5);

    printf("排序後 = ");
    for (int i=0; i<5; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

C/C++ 程式跑出來的結果如下，經過泡沫排序法 bubble sort 排序後的結果的確是由小排到大。

1 2	排序前 = 6 4 8 10 2 排序後 = 2 4 6 8 10

下一篇介紹 selection sort 選擇排序法

以上就是 C/C++ bubble sort 泡沫排序法介紹，
如果你覺得我的文章寫得不錯、對你有幫助的話記得 Facebook 按讚支持一下！