氣泡排序

排序的概念

排序，顧名思義就是將一群數字根據規則排列。在排序中我們通常會使用升序來排列，當然也可以不是，但就需要自定義一些排序規則。假設我們有一個陣列，當中的數據是長這樣： {5, 3, 6, 1, 2} 。現在我們想要將它做升序排列，我們會期待排序後的結果是 {1, 2, 3, 5, 6}。

泡沫排序

在許多排序方法中，較廣為人知且較容易學習的是「泡沫排序法（Bubble Sort）」。排序過程中，泡沫排序法會重複地比較相鄰的兩個數字，若前面的數字比後面的數字大，則交換這兩個數字的位置，直到整個陣列排序完成。更具體一點的說，泡沫排序法的流程如下：

• 整個排序過程分成 n-1 輪，每一輪都會將最大的數字排到最後面。
• 每一輪排序過程中，都會從陣列的第一個數字開始，比較相鄰的兩個數字，若前面的數字比後面的數字大，則交換這兩個數字的位置，直到整個陣列排序完成。

#include <bits/stdc++.h>
using namespace std;

vector<int> v = {5, 3, 6, 1, 2};

int main() {
    // 重複 n-1 輪
    for (int i = v.size() - 1; i > 0; i--) {
        // 每一輪都會掃過 0 到 i 的數字
        for (int j = 0; j < i; j++) {
            // 比較相鄰兩個數字，如果前面的數字比後面的數字大，則交換位置
            if (v[j] > v[j+1]) {
                swap(v[j], v[j+1]);
            }
        }
    }

    // 輸出排序後的結果
    for (auto i : v) {
        cout << i << " ";
    }
}

淺談逆序數對

氣泡排序法的一個重要應用是計算逆序數對。先以升序排列為例，逆序數對是指在一個數列中，若兩個數字 a[i] 和 a[j] 滿足 i < j 且 a[i] > a[j]，則這兩個數字就構成一個逆序數對。

看看下面這張圖的例子，在這個數列中，標記起來的 3 和 1 就是逆序數對。

這個 3 和 2 也是逆序數對。

而 3 和 4 這對就不是逆序數對。

那逆序數對跟氣泡排序有什麼關係呢？其實逆序數對就是在氣泡排序的過程中交換的次數！

也就是說，我們只要在氣泡排序的程式碼裡面加上計算交換次數的部分，就可以計算出逆序數對了！

#include <bits/stdc++.h>
using namespace std;

vector<int> v = {5, 3, 6, 1, 2};

int main() {
    int ans = 0; // 逆序數對的數量

    for (int i = v.size() - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (v[j] > v[j+1]) {
                ans++; // 每交換一次就增加一個逆序數對
                swap(v[j], v[j+1]);
            }
        }
    }

    for (auto i : v) {
        cout << i << " ";
    }

    cout << endl << ans << endl; // 輸出逆序數對的數量
}

雖然氣泡排序相較其他演算法很慢，逆序數對也聽起來很沒用，不過這些將會成為以後一些重要演算法的基礎，且 APCS 的觀念題也常常會出現類似的變化題。