大神的世界

假設有n個數要排序該怎麼做呢?

這裡要介紹的排序法叫做「bubble sort」

bubble sort 中文翻作 氣泡排序法

就是想像每個數都是一個氣泡 

比較大顆的放後面(小到大)

或是

比較小顆的放後面(大到小)

方法: 交頭接耳做比較

為什麼是交頭接耳呢?

因為每一個氣泡都喜歡跟下一個氣泡比大小

只跟下一個喔，不然為什麼叫交頭接耳

如果我贏了，那麼我跟你(下一個)交換位置

如果我輸了，那麼不動

這樣排序出來，就會是小到大

時間複雜度

最佳: O(n) 就是已經排好了，全部再視察一遍

最差: O(n^2) 就是我要小到大，你偏偏給我大到小

平均: O(n^2)  有點慢......

穩定性: 穩定

i 代表以排序好的數量

j 代表正在交頭接耳的氣泡   (最好背起來)

如果我大於你，那麼我們交換位置

把 > 改成 < 就變大到小了

程式碼:

#include <iostream>

using namespace std;

int arr[100];

void bubbleSort(int n)
{
    for(int i = 0; i<n-1; i++)   
        for(int j = 0; j<n-i-1; j++)
            if(arr[j] > arr[j+1])
                swap(arr[j], arr[j+1]);
}

int main()
{
    int n;

    while(cin >> n)
    {
        for(int i = 0; i<n; i++)
            cin >> arr[i];

        bubbleSort(n);

        for(int i = 0; i<n; i++)
            cout << arr[i] << " ";
        cout << endl;
    }
    
    return 0;

}