【例5.18】串排序

GitHub跳转原题关系图返回列表

读入若干个字符串,按字典序对它们进行排序并逐行输出。

OJ: roj

题目 ID: 5050

难度:入门

标签:字符串排序

创建: 2026-10-09 00:13

更新: 2026-10-09 00:13

形式化题目

给定一个整数 nn(1≤n≤201 \le n \le 20)和 nn 个字符串 s1,s2,…,sns_1, s_2, \dots, s_n,每个字符串的长度不超过 2020,且只包含大小写英文字母。要求将这 nn 个字符串按照字典序从小到大进行排序,并逐行输出结果。

正解

思路

本题是一道基础的字符串排序题。由于题意要求“按字母的顺序输出”,实际上即按照标准的 ASCII 字典序排列。在 C++ 和 Python 中,字符串的比较默认即为字典序比较(按照字符的 ASCII 码值逐位比较,大写字母的 ASCII 码值小于小写字母,较短的前缀字符串小于较长的字符串)。

  1. 读取:读入整数 nn。随后循环读入 nn 个字符串。实际数据实测国名不包含任何空格与制表符,最大长度刚好顶格 20 个字符。因此,直接使用普通的字符串输入(如 C++ 的 cin >> 或 Python 的 .split())即可安全读入。
  2. 排序:将这 nn 个字符串通过标准库函数(如 C++ 的 std::sort 或 Python 的 sorted())进行升序排序。
  3. 输出:依次按行输出排序后的字符串,且每行末尾保留一个换行符,没有额外多余空格。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-09 00:06
# update_at: 2026-10-09 00:06

import sys


def solve() -> None:
    """读入 n 与国家名,按字典序(逐字符编码值,区分大小写)升序逐行输出。"""
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    names = [next(data).decode() for _ in range(n)]  # 国名不含空格,按空白切分即可
    # Python 的 str < 按码点逐位比较,与 C++ std::string 在纯 ASCII 数据上完全一致
    print('\n'.join(sorted(names)))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 00:06
 * update_at: 2026-10-09 00:06
 */
// main.cpp:读入 n 个国家名(n ≤ 20,名字长度 ≤ 20),按字典序升序逐行输出。
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

const int MAXN = 25; // 题面 n ≤ 20,留出余量

string name[MAXN]; // name[1..n] 存国家名,下标从 1 开始与题面一致

// 读入国名、按字典序排序后逐行输出。
// std::string 的 < 是逐字符比较编码值(ASCII),即题面要求的"字母顺序",
// 与数据实测的区分大小写纯字典序一致;也天然支持"短前缀排在前面"。
void solve() {
    ll n;
    cin >> n;
    for (ll i = 1; i <= n; ++i) {
        cin >> name[i]; // 国名不含空格,直接按空白分隔读入即可
    }
    sort(name + 1, name + n + 1);
    for (ll i = 1; i <= n; ++i) {
        cout << name[i] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度

  • 时间复杂度:共有 nn 个字符串,排序过程通常进行 O(nlog⁡n)O(n \log n) 次字符串比较,每次比较最多需要 O(L)O(L) 的时间(LL 为字符串最大长度,此处 L≤20L \le 20)。因此总的时间复杂度为 O(nlog⁡n⋅L)O(n \log n \cdot L)。由于 n≤20n \le 20,时间常数极小,可以视为 O(1)O(1) 级别。
  • 空间复杂度:需要存储 nn 个长度不超过 LL 的字符串,因此空间复杂度为 O(n⋅L)O(n \cdot L),同样可以视为 O(1)O(1)。

总结

  • 排序序 = ASCII 字典序(区分大小写):
    • 题目中所说的“按字母的顺序”指的是逐字符比较 ASCII 码值,即 'Z'(90) < 'a'(97)。测试数据中有 3 个点(测试点 4、7、9)对该规则有判别力。
    • V1 反事实(忽略大小写的错误做法):若改为全转小写后比较(tolower key),会导致在有判别力的测试点发生多处错位,例如:
      • p4 第 1 项:应为 FHy,实得 aZh;
      • p7 第 1 项:应为 HWhBEBEsqrcWV,实得 ekQTTvbnRh;
      • p9 第 4 项:应为 ILSOQJmLcrOyVyNFTrLm,实得 fxKNjYoSKZXFbHSnXCIg。
    • 另外 7 个测试点无判别力(全相同、无重复字母、或全小写)。
  • 前缀关系:字典序天然支持前缀比较。测试点 p10 验证了这点,其输出严格按照短到长(a, aa, aaa…)排列。
  • 重复名与稳定性:测试点 p2、p6、p10 中存在完全相同的国名。排序后同值相邻即可。由于相等的元素完全不可区分,排序算法的稳定性无关紧要(C++ 的不稳定 std::sort 和 Python 的稳定 sorted() 均无影响)。
  • 算法选择:题面只规定了任务要求(“串排序”只是内容名与章节名),未硬性指明使用某特定排序算法。完全可以使用内置的库排序。附注:教学语境上也可利用本题练习自写冒泡排序或选择排序配合字符串比较。
  • 验证强度摘要:
    • 用异源自写冒泡算法与标准排序相比,308 组数据中完全没有分歧。
    • V1 承重验证:如果删去核心的排序语句,共有 6 个点会失败,证明排序逻辑真正发挥了作用(其余 4 个输入近乎有序的点不能用来验证排序本身)。
    • V2 纯净验证:代码内数值字面量仅有 {0, 1, 25},国名无一硬编码。
  • 格式细节:全部 10 个测试点的格式极为规整:每行一个名字、末尾仅带单换行 \n、无行尾空格。整体字节数精准等于 ∑(名字长+1)\sum(\text{名字长}+1)。
  • 跨语言的一致性:五项可能跨语言引发差异的细节全无风险。数据全部由纯 ASCII 字符组成,因此 C++ std::string 与 Python str 的 < 比较逻辑完全等价。