第三章：排序与结构化比较

排序将分散的数据整理成确定的次序，使相等元素连续、较小元素靠前，或让更应优先处理的对象排在前面。本章先从寻找最小值和维护有序前缀得到基础排序，再讨论如何使用排序解决去重、同分录取和按数位排序。

阅读前需要掌握数组、循环和函数。结构体在首次使用处说明；归并排序的完整实现放在第七章，本章只讨论合并思想。

1. 基础排序思想

1.1 选择排序

若要求把数组从小到大排列，可以先扫描全部元素，找到最小值并放到第一个位置；再在其余元素中找最小值，放到第二个位置。每确定一个位置，待处理范围就缩短一个元素，这就是选择排序。

例如数组为 $4,2,3,1$，第一轮交换首项与最小值后得到 $1,2,3,4$。虽然已经有序，普通选择排序仍会继续检查剩余位置。以下输入存于全局数组 $a[1]$ 至 $a[n]$，每轮的 $k$ 只记录当前最小值的位置。

for (int i = 1; i <= n; ++i)
{
    int k = i;
    for (int j = i + 1; j <= n; ++j)
    {
        if (a[j] < a[k])
        {
            k = j;
        }
    }
    swap(a[i], a[k]);
}

处理完第 $i$ 轮后，前 $i$ 个元素已经是最终结果。

第 $i$ 轮只在 $[i,n]$ 中找最小值，因为前面的位置已经确定，不应再被改动。比较次数为 $(n-1)+(n-2)+\cdots+1$，无论原数组是否已经有序，都需要 $O(n^2)$ 次比较。

用一次交换把最小值送到前面，可能改变相等记录的原先次序。因此这种写法通常不稳定；若题目要求相等时保持输入顺序，需要额外保存编号并明确比较规则。

1.2 插入排序

把当前元素插入前面已经有序的部分。它适合数据规模小或原序列接近有序的情况。

选择排序和普通插入排序的最坏时间都是 $O(n^2)$，适合小规模数据与理解有序状态的维护；不能由此认为所有排序都是平方复杂度。

例如已有序部分为 $[2,5,7]$，新元素为 $4$。从后向前比较，把 $7$、$5$ 各向右挪一格，留下空位放入 $4$，得到 $[2,4,5,7]$。移动时必须先保存新元素，否则它所在位置可能被覆盖。

以下仍使用全局数组 $a$。先用 $x$ 保存待插入值，$j$ 从有序部分末尾向左移动；只有完成搬移后，才把 $x$ 写入留下的空位。

for (int i = 2; i <= n; ++i)
{
    int x = a[i], j = i - 1;
    while (j >= 1 && a[j] > x)
    {
        a[j + 1] = a[j];
        --j;
    }
    a[j + 1] = x;
}

只移动严格大于新元素的值，就能保留相等元素的原顺序。接近有序时移动次数少；逆序时几乎每个元素都要一路移动到最前面，最坏复杂度仍为 $O(n^2)$。

1.3 冒泡排序

选择排序每轮寻找一个最小值；冒泡排序则逐对比较相邻元素，逆序就交换。从左向右完成一轮后，最大值会移到末尾，下一轮只需处理它之前的部分。例如 $3,1,2$ 先交换为 $1,3,2$，再变为 $1,2,3$。

第 $i$ 轮比较到位置 $n-i$，每次只交换严格逆序的相邻元素，可以保留相等记录的原次序。最坏时间为 $O(n^2)$；若某轮没有交换，整个剩余部分已经有序，可以结束。三种基础排序中，选择排序每轮固定最小值，插入排序扩大有序前缀，冒泡排序通过相邻交换固定最大值。

2. 使用 $sort$

例题：明明的随机数。

简易题面：给出若干整数，删除重复值，输出不同数的个数及升序排列。

数据范围：$1\le n\le100$，$1\le a_i\le1000$。

可以先将每个数与已保留的数逐一比较，再给保留结果排序。这个平方做法足以通过原题；为了使相同元素集中到一起，也可以先排序，再连续扫描去重。标准库 $sort$ 完成排序，去重过程见第 5 节。以下 $a[110]$ 为全局 $\texttt{int}$ 数组，输入存于一号下标区间。

sort(a + 1, a + n + 1);

对 $a[1]$ 至 $a[n]$ 排序时，右端写成 $a+n+1$。排序后常见操作：

• 查找相同元素的连续段；
• 双指针统计数对；
• 合并区间；
• 二分边界；
• 按顺序贪心。

$sort$ 接收的是左闭右开的范围：包含起点，不包含终点。因此一号下标数组写 $a+1$ 到 $a+n+1$，零号下标数组则写 $a$ 到 $a+n$。这只是接口范围的约定，与题目中的闭区间 $[l,r]$ 要分清。

排序可以在 $O(n \log n)$ 时间内完成全体元素的顺序整理。但排序会改变输入顺序；若题目研究原序列的连续区间，排序后“相邻”的意义已经改变，不能直接用它替换原序列。

3. 多关键字排序

3.1 结构体记录

例题：NOIP 2007 普及组·奖学金。

简易题面：按总分降序选出前五名；总分相同时语文分高者优先，仍相同时学号小者优先。输出学号与总分。

数据范围：$5\le n\le300$，三科成绩均为 $0$ 至 $100$，学号为输入顺序。

若逐次挑出当前最好的一人，需要反复判断同样的优先关系。把这套判断写成比较函数，再统一排序，就能直接取得前五名。编号和成绩必须随同一个学生一起移动，因此用一个小结构体保存。

以下 $id$ 为学号，$x$ 为语文分，$s$ 为三科总分。总分不超过 $300$，全部使用 $\texttt{int}$；读入时算好总分，不在每次比较时重复相加。

struct Node
{
    int id, x, s;
};
Node a[310];
bool cmp(Node a, Node b)
{
    if (a.s != b.s)
    {
        return a.s > b.s;
    }
    if (a.x != b.x)
    {
        return a.x > b.x;
    }
    return a.id < b.id;
}

调用 $sort(a+1,a+n+1,cmp)$ 后输出前五项。第一关键字相同，才有必要比较第二关键字；不能把三个条件无条件地用逻辑或连接。例如总分更低的学生，不能仅凭语文分高就排到前面。

比较函数表达严格先后关系。同一记录与自己比较应为假，且先后关系必须具有传递性；最后一项不能返回 $\le$ 或 $\ge$。按这组固定关键字逐层比较，就能得到一致的顺序。总时间为 $O(n\log n)$，记录空间为 $O(n)$。

3.2 保留原位置

需要恢复输入顺序时，在记录中保存 $id$。处理完后可以按 $id$ 排序，或把答案写入 $ans[id]$。

排序后数组下标表示“当前排名”，$id$ 表示“原来是谁”，二者不能互换。如果只要输出按原输入顺序排列的答案，可以直接写到 $ans[a[i].id]$，不必把整组记录再排回去。

4. 计数排序与桶

例题：NOIP 2006 普及组·明明的随机数。

简易题面：删除输入中的重复数字，输出不同数的个数及升序结果。

数据范围：$1\le n\le100$，$1\le a_i\le1000$。

排序后去重可用 $O(n\log n)$ 时间完成；本题值域只有 $1$ 至 $1000$，还可以直接按值记出现状态。以下全局 $\texttt{bool }has[1010]$ 初始为假，逐次读入一个数并标记；正式输出时先输出不同值的个数。以下片段只展示标记与有序输出过程。

for (int i = 1; i <= n; ++i)
{
    int x;
    scanf("%d", &x);
    has[x] = true;
}
for (int x = 1; x <= 1000; ++x)
{
    if (has[x])
    {
        printf("%d ", x);
    }
}

每个输入数都会标记自己的位置，重复标记不改变真假值；最后每个已出现的值只输出一次，因此输出恰好是有序去重结果。设值域上界为 $C$，时间为 $O(n+C)$，标记空间为 $O(C)$。

如果需要保留全部重复元素，就把真假标记改成频次 $cnt[x]$，输出时重复相应次数。例如输入 $3,1,3,2$，频次分别为 $1,1,2$，升序输出得到 $1,2,3,3$。是否保存次数取决于计数对象，不能为了节省状态而丢掉答案所需的信息。值域很大时，数组成本也随之增长，应回到排序或离散化。

4.1 排名与同分边界

例题：NOIP 2009 普及组·分数线划定。

简易题面：有 $n$ 名选手参加选拔，计划录取 $m$ 人。面试名额按计划人数的 $150\%$ 计算并向下取整，排名在该位置选手的成绩作为面试分数线。所有成绩不低于分数线的选手都能进入面试。

选手按成绩从高到低排名；成绩相同时，编号较小者在前。请输出分数线和全部进入面试的选手。

数据范围：$5\le n\le5000$；$3\le m\le n$，且 $\lfloor1.5m\rfloor\le n$；$1000\le id_i\le9999$，编号互不相同；$1\le s_i\le100$。

设计划人数为 $p$，先计算名次边界 $k=\lfloor3p/2\rfloor$。题面保证 $1\le k\le n$。记录使用字段 $id,s$，比较函数先按 $s$ 降序，再按 $id$ 升序；以下 $m$ 表示实际面试人数，不能继续把它当成原计划人数。先取第 $k$ 名成绩，再向后纳入全部同分对象。

sort(a + 1, a + n + 1, cmp);
int line = a[k].s;
int m = k;
while (m < n && a[m + 1].s == line)
{
    ++m;
}

排序关键字决定先后顺序，分数线条件决定实际入选范围，两者不能混为一谈。

先按题意算出计划考察的名次数，再取该名次的成绩作为分数线。若排序后成绩为 $95,90,90,90,80$，名次边界是第 2 名，那么实际入选的应是前 4 人。

此处代码使用的记录字段是 $s$，需要按本题另行定义；本题不需要语文成绩字段 $x$。同分人员内部仍可按编号排序，但编号不能改变谁达到分数线。

5. 排序后扫描

例题：NOIP 2006 普及组·明明的随机数。

简易题面：删除重复值，并输出不同数的个数与升序结果。

数据范围：$1\le n\le100$，$1\le a_i\le1000$。

排序常把“任意位置关系”变成“相邻关系”。例如去重：

sort(a + 1, a + n + 1);
int m = 0;
for (int i = 1; i <= n; ++i)
{
    if (i == 1 || a[i] != a[i - 1])
    {
        a[++m] = a[i];
    }
}

排序使同值元素连续，因此只需和前一个元素比较，就能判断是否遇到一个新值。写回位置不会超过读取位置，已经压缩的前缀也不会破坏后面尚未读取的元素。

若既要输出不同数的个数，又要升序输出它们，可以把去重后的前 $m$ 个位置作为结果。去重只缩短有效区间，并不会把数组后面的旧数据自动清空。

6. 按数位排序

例题：CSP-J 2025·拼数。

简易题面：从只含小写字母和数字的字符串中挑出任意数字，每个出现位置至多使用一次，重新排列成尽可能大的整数。

数据范围：字符串长度为 $1$ 至 $10^6$，保证至少含一个非零数字。

枚举选取方式和排列会产生大量重复。由于已有非零数字，保留更多数字就能得到位数更多的正整数，所以应使用全部数字。位数相同时，大小由第一个不同数位决定，因此应把较大的数字放在前面。十种数位可以直接计数，无需比较排序，也无需把结果存进整数类型。

以下 $s$ 保存输入字符串，全局 $\texttt{int }cnt[10]$ 初始全零。

for (char c : s)
{
    if (c >= '0' && c <= '9')
    {
        ++cnt[c - '0'];
    }
}
for (int d = 9; d >= 0; --d)
{
    for (int i = 1; i <= cnt[d]; ++i)
    {
        printf("%d", d);
    }
}

例如 $\texttt{a203b2}$ 的数字按降序组成 $3220$。最高位非零，保留末尾的零仍会增大数值。扫描和输出均为线性时间，频次数组只需常数空间；若保存整条输入，还需与其长度成正比的空间。

7. 作业

巩固练习

• NOIP 2006 普及组·明明的随机数
• NOIP 2007 普及组·奖学金

提高训练

• NOIP 2009 普及组·分数线划定
• CSP-J 2025·拼数
• CSP-J 2020·直播获奖