排序

排序不是題目，是工具。 · ⏱ 約 25 分鐘

你會學到三件事

1. sort 一行搞定，而它是 O(n log n)
2. begin() / end() 是一段範圍
3. 很多題目排完序之後就變簡單了

開始之前

自己寫排序是好的練習，而比賽時沒有人自己寫。

這一課教的是「用它」，不是「做它」。

一、一行

vector<int> v = {5, 2, 8, 1};
sort(v.begin(), v.end());

v 變成 {1, 2, 5, 8}——原地改，不回傳新的。

二、begin() 和 end() 是一段範圍

v:    5    2    8    1
     ▲                   ▲
   begin()             end()
                    （最後一個的【後面】）

⚠️ end() 指的是「最後一個的下一格」，不是最後一個。

這是「含頭不含尾」的又一次——和 range(n)、i < n 是同一個約定。

好處是：end() - begin() 就是長度，而空的範圍是 begin() == end()。

排一部分也就順理成章：

sort(v.begin(), v.begin() + 3);      // 只排前三個

三、由大到小

sort(v.begin(), v.end(), greater<int>());

第三個參數是比較的規則。greater<int>() 是「大的排前面」。

自己定規則也可以：

sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);       // 依絕對值排
});

那個 [](...){...} 是 lambda——一個當場寫的小函式。

⚠️ 回傳的意思是「a 應該排在 b 前面嗎」，不是「a 比較小嗎」。 兩者常常一樣，而想成前者才不會在複雜規則上出錯。

四、排序讓題目變簡單

很多題目排完就解了一半：

「先排序看看」是競賽裡最值得養成的一個反射。

代價只有 O(n log n)，而它常常把一個 O(n²) 的問題變成 O(n)。

完成的樣子

int main() {
    vector<int> v = {5, 2, 8, 1};
    sort(v.begin(), v.end());
    for (int x : v) cout << x << " ";
    cout << endl;
    return 0;
}

換你了

給一串數字，找出最接近的兩個數的差。

⚠️ 不排序的話要 O(n²) 兩兩比；排序之後只要比相鄰的，O(n log n)。

這一課你做了什麼

• 你用一行排好了一個 vector
• 你知道 end() 指向最後一個的後面
• 你知道「先排序看看」是一個值得養成的反射

如果卡住了