Lesson 0002 · sort 与 string：排序和字符串

① 程序设计基础 — 第 1 课（续）

1. sort：一行代码排好序

sort 在 <algorithm> 头文件里，底层是快排 + 堆排 + 插排的混合，复杂度 O(n log n)。你只需要记住三个用法：

#include <iostream>
#include <vector>
#include <algorithm>      // sort 在这里
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2};

    sort(v.begin(), v.end());         // 升序：1 1 2 3 4 5 9
    sort(v.rbegin(), v.rend());       // 降序：9 5 4 3 2 1 1

    // 只排前 4 个
    sort(v.begin(), v.begin() + 4);   // v[0..3] 排序，其余不动
}

真题模式：排序 + 去重

这是竞赛中的经典组合。比如洛谷 P1059「明明的随机数」—— 输入 N 个数，排序去重后输出。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    sort(a.begin(), a.end());                           // 1. 排好序
    a.erase(unique(a.begin(), a.end()), a.end());       // 2. 去重

    cout << a.size() << endl;
    for (int x : a) cout << x << ' ';
    return 0;
}

2. string：加强版字符 vector

string 本质上就是一个 vector<char>，再加上字符串专属操作。你会用 vector，就会用 string。

示例：反转字符串

string s;
cin >> s;

// 方法 1：手写循环
for (int i = s.size() - 1; i >= 0; i--) {
    cout << s[i];
}

// 方法 2：STL 一键
reverse(s.begin(), s.end());
cout << s;

3. 坑点清单

• 结束位置是「最后一个的下一个」：sort(v.begin(), v.end()) 才对；写成 v.end() - 1 会把最后一个元素漏掉不排。
• 只写 unique 等于没去重：它只把重复的挤到后面，必须接 erase 才真的删掉。
• 去重前一定先排序：unique 只能挤掉相邻的重复元素，乱序的数组挤不干净。
• cin >> s 遇到空格就停：读带空格的一整行必须用 getline(cin, s)。
• find 找不到返回 string::npos：判断要写成 s.find(x) != string::npos，不要拿它当普通下标用。
• substr(i, len) 的第二个参数是长度，不是结束下标；substr(2, 3) 取的是下标 2、3、4 三个字符。

4. 小测

5. 动手练习

卡住时的自查顺序

1. 样例过了吗？先把排序后的数组打印出来，确认 sort 的范围没写错。
2. 去重那两行是不是一起写的？只写 unique 的话，输出的个数还是原来那么多。
3. 字符串题：读的是单词还是整行？带空格就必须换成 getline(cin, s)。
4. 输出格式对齐了吗？个数和数列分两行、数字之间一个空格，都是判题机会较真的地方。

本课小结

• sort 一行排序：三个参数位置，左闭右开，升序降序换个迭代器就行。
• 去重固定两行：sort 先排好，再 erase(unique(...), end())。
• string 是字符版 vector：+ 拼接、size() 数长度、s[i] 取字符。
• find 找不到返回 string::npos，判断时和它比较，不要和下标混用。
• 读入分两种：单词用 cin >> s，整行用 getline。