排序的概念#
排序，顧名思義就是將一群數字根據規則排列。在排序中我們通常會使用升序來排列，當然也可以不是，但就需要自定義一些排序規則。假設我們有一個陣列，當中的數據是長這樣： {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 這對就不是逆序數對。
那逆序數對跟氣泡排序有什麼關係呢？其實逆序數對就是在氣泡排序的過程中交換的次數！
為什麼逆序數對就是交換次數？
首先我們可以發現，當我們在氣泡排序的過程中，只有當 a[i] 和 a[j] 滿足 i < j 且 a[i] > a[j] 時，我們才會進行交換，也就是說這樣每交換一次就會減少一個數列中的逆序數對。並且 a[i] 和 a[j] 交換時也不會影響到其他的逆序數對。因此逆序數對就是交換次數。
也就是說，我們只要在氣泡排序的程式碼裡面加上計算交換次數的部分，就可以計算出逆序數對了！
#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 的觀念題也常常會出現類似的變化題。
