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

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

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

1. 基础排序思想

1.1 选择排序

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

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

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]);
}

处理完第 ii 轮后,前 ii 个元素已经是最终结果。

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

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

1.2 插入排序

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

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

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

以下仍使用全局数组 aa。先用 xx 保存待插入值,jj 从有序部分末尾向左移动;只有完成搬移后,才把 xx 写入留下的空位。

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(n2)O(n^2)。

1.3 冒泡排序

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

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

2. 使用 sortsort

例题:明明的随机数。

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

数据范围:1≤n≤1001\le n\le100,1≤ai≤10001\le a_i\le1000。

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

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

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

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

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

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

3. 多关键字排序

3.1 结构体记录

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

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

数据范围:5≤n≤3005\le n\le300,三科成绩均为 00 至 100100,学号为输入顺序。

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

例如,两名学生总分同为 280280、语文分分别为 95,9095,90,应先选语文分为 9595 的学生;只有语文分也相同时,才比较学号。以下是本题的完整实现,idid 为学号,xx 为语文分,ss 为三科总分。总分不超过 300300,全部使用 int\texttt{int};读入时算好总分,不在每次比较时重复相加。

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int id,x,s;
}a[310];
bool cmp(Node x,Node y){
    if(x.s!=y.s)return x.s>y.s;
    if(x.x!=y.x)return x.x>y.x;
    return x.id<y.id;
}
int main(){
    int n,y,z;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i].x>>y>>z;
        a[i].id=i;
        a[i].s=a[i].x+y+z;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=5;++i)cout<<a[i].id<<' '<<a[i].s<<'\n';
    return 0;
}

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

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

3.2 保留原位置

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

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

4. 计数排序与桶

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

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

数据范围:1≤n≤1001\le n\le100,1≤ai≤10001\le a_i\le1000。

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

for(int i=1;i<=n;++i){
    int x;
    cin>>x;
    has[x]=1;
}
for(int x=1;x<=1000;++x){
    if(has[x])cout<<x<<' ';
}

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

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

4.1 排名与同分边界

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

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

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

数据范围:5≤n≤50005\le n\le5000;3≤m≤n3\le m\le n,且 ⌊1.5m⌋≤n\lfloor1.5m\rfloor\le n;1000≤idi≤99991000\le id_i\le9999,编号互不相同;1≤si≤1001\le s_i\le100。

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

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

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

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

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

5. 排序后扫描

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

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

数据范围:1≤n≤1001\le n\le100,1≤ai≤10001\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];
}

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

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

6. 按数位排序

例题:CSP-J 2025·拼数。

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

数据范围:字符串长度为 11 至 10610^6,保证至少含一个非零数字。

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

以下 ss 保存输入字符串,全局 int cnt[10]\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);
}

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

7. 作业

巩固练习

提高训练

留言

可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。