P4687 串排序（基础）

解题思路

题目要把 n 个国家名按字典序从小到大排序，排好后再逐行输出。什么是字典序？就像查英语词典那样比较字符串：先比较第一个字符，一样再比第二个字符，依此类推。比如 "China" 和 "Japan"，'C' 的 ASCII 码是 67，'J' 的 ASCII 码是 74，67 < 74，所以 "China" 排在 "Japan" 前面。下面分四步来实现。

**第一步，读入国家名。**国家名是字符串，不能像数字那样直接塞进 int 数组。我们用一个结构体把字符串包起来：struct Name { char str[25]; };。因为结构体可以整体复制，所以 sort() 能对结构体数组排序。读入时用 cin >> names[i].str，cin 读到空格或换行就停，正好适合读不含空格的国家名。

**第二步，写比较规则。**C++ 里比较两个字符串，可以用 cstring 头文件提供的 strcmp 函数：strcmp(a, b) 返回值小于 0 时说明 a 比 b 小（应该排在前面），等于 0 说明相等，大于 0 说明 a 更大。我们把它写进自定义函数 cmp，返回 strcmp(a.str, b.str) < 0，这样 sort() 就会按字典序排列。

第三步，排序。sort(names, names + n, cmp) 会把整个数组按 cmp 的规则排好序。比较规则写好后，具体怎么排就交给 sort 完成，我们不用操心。

**第四步，逐行输出。**用一个循环，把排好序的国家名一个一个输出，每个名字后面换行。

举个例子验证：输入 Korea、China、Japan 三个国家名，按字典序排序后是 China、Japan、Korea，逐行输出，和样例一致。

边界情况：n 最大 20，国家名长度不超过 20，所以结构体数组开 25 个，每个字符数组开 str[25] 就足够，不会越界。

参考代码

// 串排序：把n个国家名按字典序从小到大排序，再逐行输出
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct Name {
    char str[25];   // 国家名
};

// 按字典序比较两个国家名，strcmp(a,b)<0 表示 a 排在 b 前面
bool cmp(const Name &a, const Name &b) {
    return strcmp(a.str, b.str) < 0;
}

int main() {
    int n;
    cin >> n;
    Name names[25];              // 存 n 个国家名
    for (int i = 0; i < n; i++) {
        cin >> names[i].str;     // 读入国家名
    }
    sort(names, names + n, cmp); // 按字典序排序
    for (int i = 0; i < n; i++) {
        cout << names[i].str << endl;
    }
    return 0;
}

复杂度分析

排序时间复杂度 O(n log n)，每次比较两个字符串最坏要比较到长度 L=20，所以总时间约为 O(n log n × L)。n 只有 20，完全没问题。空间上用一个 n×L 的二维字符数组存国家名，空间复杂度 O(n×L)。