C++排序教學1 - 泡沫排序法 Bubble Sort

前言

這個教學系列會討論各式排序演算法，並用C++來實現各式演算法，在文章最後也會寫出各式演算法的缺陷和優點，若在觀看過程有覺得可以改進的部分也歡迎在底下留言。

泡沫排序法簡述

泡沫排序法（Bubble Sort）是各式演算法中最簡單，也是幾乎最沒效率的一種，但是因概念簡單，適合初學排序演算法的人。

泡沫排序法的想法就比如想像在水中的泡泡，因為密度較低，便會慢慢向上浮出水面，同理，處裡在一排數字上，便是將密度小（數字小的）往前排序，並將密度大（數字大的）往後排序，以此類推，每次都將數字最小的移至前方，最後就能排序完成。

程式碼 (C++)

#include <stdio.h>

void bubble_sort (int *param, int size)
{
    bool not_sorted = true; //stop if already sorted
    for (int min = 0; min < size && not_sorted; min++)
    {
        not_sorted = false;
        for (int max = size; max > min; max--)
        {
            if (param[max - 1] > param[max]) //not what we want
            {
                int temp = param[max - 1];
                param[max - 1] = param[max];
                param[max] = temp;
                not_sorted = true;
            }
        }
    }
}

int main()
{
    int array[10] = {1, 3, 5, 2, 7, 8, 0, 4, 6, 9};
    bubble_sort(array, 10);
    for (int i = 0; i < 9; i++)
        printf("%d, ", array[i]);
    printf("%d", array[9]);
}

輸出：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

優點

容易理解、不須額外使用記憶體

缺點

速度慢，正常情況下為O(n²)，在大量數據下，相較其他演算法，處裡速度太慢。

👉【幫我們一個忙！】👈

👋如果您喜歡這篇文章，請在下方按5個Like！

 ❤您的支持是我們最大的動力！

您只要登入帳號（Facebook、Google），在下方按5個Like，我們就會收到來自LikeCoin基金會的贊助。

您只需要支持我們，完全不會花到錢！