排序

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

你會學到三件事

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

開始之前

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

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

🟢 先把編輯器打開，跟著下面一起做：跟著做

一、一行

排序只要一行：

1vector<int> v = {5, 2, 8, 1};2sort(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()。

排一部分也就順理成章：

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

三、由大到小

第三個參數決定怎麼比：

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

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

自己定規則也可以：

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

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

積木盤上 lambda 那一顆寫著「臨時函式」， 而 abs 那一顆寫著「取絕對值」。

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

四、排序讓題目變簡單

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

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

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

完成的樣子

1#include <algorithm>2#include <iostream>3#include <vector>4using namespace std;5int main() {6    vector<int> v = {5, 2, 8, 1};7    sort(v.begin(), v.end());8    for (int x : v) cout << x << " ";9    cout << endl;10    return 0;11}

換你了

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

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

🟢 這一題會告訴你差多少：先用 O(n²) 寫一版跑跑看， 再改成先排序——主控台會說「這一趟走了 N 步」，而第二次會說 它是上一次的百分之幾。

🎯 而這一關有一個目標：80 步以內。 ⚠️ 那不是一道門——超過了這一題照樣算你過，它只是告訴你「還有更省的做法」。

⚠️ 那個「步」是直譯器走過一顆積木一次算一步， 不是課本的「基本操作次數」——它比課本細，而兩版的比值仍然說得出真話。

到編輯器做這一題：練習：最接近的兩個數的差

做一個

一串數字 5 1 9 3 7：印出中位數，再印出最大減最小。

🔴 兩個答案排序之後都是一行——而排序之前，兩個都要寫迴圈。 這就是「很多題目排完序就變簡單」的最小例子。

到編輯器做這一題：做一個：中位數與全距

這一課你做了什麼

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

如果卡住了