一、學習目標

• 深入掌握 C++ STL sort() 的使用方法、時間複雜度與自訂比較技巧。
• 學會使用 lambda 表達式排序複合資料結構。
• 透過四道實戰題目，練習 缺失數字、雙指針、區間合併、最少刪除數量。
• 理解排序在演算法題中的關鍵角色。

二、C++ STL sort() 完全解析

1. sort()基本用法

sort(nums.begin(), nums.end());

• 預設排序為升序排列。

• 適用於 vector、array、deque 等隨機訪問容器。

• 時間複雜度：

  • 平均：O(NlogN)
  • 最壞：O(NlogN)

• 演算法原理：
  C++ STL sort() 採用 Introsort（混合演算法）
  平均情況下用 QuickSort。
  遇到遞迴過深時改用 HeapSort，避免最壞退化。
  小區間時會切換 InsertionSort 提高效能。

2. 指定排序範圍

sort(nums.begin()+1, nums.end()-1);

僅排序部分資料，例如只排序索引 [1, n-2] 的元素。

3. 自訂排序規則

方法 1：函式比較子

bool cmp(int a, int b) {
    return a > b; // 降序排列，元素會由大到小
}

sort(nums.begin(), nums.end(), cmp);

方法 2：lambda 表達式

sort(nums.begin(), nums.end(),
     [](int a, int b) {
         return a > b; // 降序
     });

lambda 優點：

• 簡潔、直觀
• 適合比較多欄位的結構

4. 排序複合型資料

例如，排序一個區間陣列 vector<pair<int,int>>，
按照「起點升序，若起點相同則依終點升序」：

sort(intervals.begin(), intervals.end(),
     [](const pair<int,int>& a, const pair<int,int>& b) {
         if (a.first == b.first) return a.second < b.second;
         else return a.first < b.first;
     });

三、實戰演練

CSES 1: Missing Number

原題:
https://cses.fi/problemset/task/1083

解法一：排序 + 遍歷

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

int main() {
    int n;
    cin >> n;
    vector<int> nums(n-1);
    for (int i = 0; i < n-1; i++) cin >> nums[i];

    sort(nums.begin(), nums.end());

    for (int i = 0; i < n-1; i++) {
        if (nums[i] != i+1) {
            cout << i+1 << endl;
            return 0;
        }
    }
    cout << n << endl;
    return 0;
}

解法二：數學公式

利用數列和公式：

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

int main() {
    int n;
    cin >> n;
    long long total = 1LL * n * (n+1) / 2;
    long long sum = 0;
    for (int i = 0; i < n-1; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    cout << total-sum << endl;
    return 0;
}

解法三：XOR 位元運算

原理：
如果我們 XOR 所有 1∼n 的數字，再XOR輸入的所有數字，最後結果就是缺少的數。

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

int main() {
    int n;
    cin >> n;
    int x = 0;
    for (int i = 1; i <= n; i++) x ^= i;
    for (int i = 0; i < n-1; i++) {
        int val;
        cin >> val;
        x ^= val;
    }
    cout << x << endl;
    return 0;
}

三種解法總整理:

CSES 2: Apartments

原題:
https://cses.fi/problemset/task/1084
題意:
有 n 個申請者想租房子，每個人有期望房間大小。
有 m 間房子，每間房子有實際大小。
給一個容忍度 k：若房子大小與期望差距 ≤ k，則可匹配。
問最多可以成功匹配多少人。

思路:

• 將申請者與房子大小排序。
• 使用雙指標遍歷兩個陣列。
• 若房子合適 → 匹配成功。
• 若房子太小 → 移動房子指標。
• 若房子太大 → 移動申請者指標。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,k; //申請者、空公寓、申請者理想大小可接受的最大差距
    cin>>n>>m>>k;
    vector<long long> people(n);
    vector<long long> apartment(m);
    for(int i=0;i<n;i++) cin>>people[i];
    for(int i=0;i<m;i++) cin>>apartment[i];
    
    int ans=0,j=0;    //j:指向哪一個apartment
    sort(people.begin(),people.end());
    sort(apartment.begin(),apartment.end());
    for(int i=0;i<n;i++){
        while(j<m and apartment[j]<people[i]-k){
            ++j;
        }
        if (j<m && apartment[j]<=people[i]+k){
            ans++;
            ++j;     // 這間公寓被用掉，指到下一間
        }
    }
    cout<<ans<<endl;
    return 0;
}

Leetcode 1: Merge Intervals

原題:
https://leetcode.com/problems/merge-intervals/description/
題意:
給定一個區間陣列 intervals，將所有重疊的區間合併，並回傳結果。

思路:

• 先依照區間起點升序排序。
• 用一個 result 容器儲存合併結果。
• 遍歷每個區間：
  • 如果當前區間和 result.back() 重疊 → 合併。
  • 否則直接加入 result。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 依照起點升序排序
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> result;
        result.push_back(intervals[0]);

        for (int i = 1; i<intervals.size(); i++) {
            if (intervals[i][0] <= result.back()[1]) {
                // 有重疊 → 更新結束點
                result.back()[1] = max(result.back()[1], intervals[i][1]);
            } else {
                // 沒有重疊 → 直接加入
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};

Leetcode 2: Non-overlapping Intervals

原題:
https://leetcode.com/problems/non-overlapping-intervals/description/

題意:
給定一組區間，找出最少刪除多少區間，使剩下的區間互不重疊。

思路:

• 將區間按照結束時間升序排序。
• 遍歷所有區間，貪心保留 最早結束的區間。
• 若有重疊 → 增加刪除計數。

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(),
        [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1]; // 按照結束時間排序
        });

        int count = 0;
        int prevEnd = intervals[0][1];

        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < prevEnd) {
                // 與前一個區間重疊 → 刪除當前區間
                count++;
            } else {
                // 無重疊 → 更新 prevEnd
                prevEnd = intervals[i][1];
            }
        }
        return count;
    }
};

題目總結: