排序（Round 1）

-1 检查浏览器渲染数学公式情况

因为笔者发布文章当天，本博客仍然存在 Latex 可能无法渲染的情况，下面是一个 Latex 示范：

$x$

• 如果正常显示为衡水体 x，则代表读者的浏览器已经成功渲染了 Latex
• 如果显示为 带有美元符号的 x 即 $x$（已除去换行符），则代表读者的浏览器没有成功渲染 Latex，读者可能需要刷新重试，如果刷新多次仍然无法渲染，请尝试换一个浏览器/网络环境

0 框架

在本文中，我将重点介绍 排序，感谢 深入浅出程序设计竞赛（基础篇） 提供重要支持，本文有一部分的内容是基于本书修改

排序 是在 OI 算法中重要的一部分，虽然大部分场景下都可以用 sort 解决（限于 bits/stdc++.h），但是掌握具体的内容还是必不可少的，相对于初赛而言

$$ \begin{aligned} &\textbf{排序（Round 1）} \begin{cases} &\text{计数排序}\\ &\text{选择排序、冒泡排序、插入排序}\\ &\text{快速排序}\\ &\text{排序算法的应用}\\ &\text{汇总}\\ \end{cases} \end{aligned} $$

1 计数排序

【题目样本 1.1】P1271【模板】排序

题目描述

https://www.luogu.com.cn/problem/P1271

学校正在选举学生会成员，有 $n(n \leq 999)$ 名候选人，每名候选人编号分别从 $1$ 到 $n$, 现在收集到了 $m(m \leq 200000)$ 张选票，每张选票都写了一个候选人编号

现在想把这些堆积如山的选票按照投票数字从小到大排序。输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字，求出排序后的选票编号。例如，当有 $5$ 个候选人，$10$ 张选票分别是 $2、5、2、2、5、2、2、2、1、2$ 时，需要输出 1222222255

分析

这题本质有很多方法，但是由于是 计数排序，因此：

在投票区放上 $n$ 个投票箱，投票人支持谁就把票投入对应的投票箱中，投票后只须统计每个投票箱有几张选票，直接按照候选人编号取出来就可以完成排序操作

也不需要排序了

参考代码

#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,x,f[100005];
int main(){
    cin>>n>>m;
    for(i=1;i<=m;i++) cin>>x,f[x]++;
    for(i=1;i<=n;i++) for(j=1;j<=f[i];j++) cout<<i<<" ";
}

这里倡导数组从 $1$ 开始存

只需要开一个大小不小于 $n$ 的数组作为票箱，依次读入选票，然后将选票号数加到对应的票箱中，最后按照每个票箱的数量输出候选人编号即可

在这个过程中，甚至不需要存储下每一张选票

在完成输入并计算时，$f[]$ 状态如下

计数排序

这种排序方法被称为 计数排序

读入选票并统计的时间复杂度是 $O(m)$，输出选票的时间复杂度是 $O(m+n)$（第一层循环做 $n$ 次，$f[i]$ 至多为 $m$），空间复杂度是 $O(n)$（因为 $f[]$）

所以计数排序只能用于排序编号范围不是很大的数字，如果需要排序的数字要到 $10^9$，别说运行时间了，内存都无法存得下这么大的范围的数组

此外，如果希望将一些浮点数或者字符串进行排序，就没办法去建造合适的 投票箱，所以就不能使用这种算法了（把下标存成 $\text{浮点数} \times 10^\text{浮点数位数}$ 也是一个不错的选择）

也有改进方法，即 桶排序&基数排序，思路类似，但是复杂

无论是上段和计数，这些排序都是基于分类，并非比较

2 选择排序、冒泡排序、插入排序

【题目样本 2.1】数列排序

题目描述

输入 $n(n \leq 1000)$ 个数字 $a_i(a_i \leq 10^9)$, 将其从小到大排序后输出

分析

设有 $5$ 张纸牌，他们是 $4,1,9,5,1$，打牌时如何排序？

解法 1：选择排序

分析

求最大值：max()

求最小值：min()

求一序列最值：for(int i=1;i<n;i++) ma=max(ma,a[i]);，a[] 为序列，$n$ 为数量，$ma$ 存放最大值

核心思想：打擂台

如何联想到本题？

这里有一张不错的图，来自 深入浅出，因此贴在这

若遇到大小相等的牌，continue

参考代码片段

for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++)
        if (a[j] < a[i]) {
            int p = a[i];
            a[i] = a[j];
            a[j] = p;
        }
}

解法 2：冒泡排序

分析

如果尝试把最大的一项放在后面，虽然可以倒过来使用选择排序，但是可以试试别的办法

这里有一张图，来自 豆包，它打了一个类似于文章的比方，讲述了 选择排序 与 冒泡排序 的区别，前情提要是 现有扑克牌：9、5，要排成5、9

首先比较第 $1$ 张牌和第 $2$ 张牌，如果后面的牌比前面的牌小，那么就交换位置；然后比较第 $2$ 张牌和第 $3$ 张牌，同样保证第 $3$ 张牌要大于第 $2$ 张牌……依此类推， 直到比较最后一张牌和倒数第二张牌，这样就能保证最后面的一张牌是最大的一张了

继续进行新的一轮，利用上面一样的交换，但是需要注意的是，由于最后一张牌已经是手牌中最大的一张了，所以只需要比较到倒数第二张就行了

这一轮后结束后倒数第二张牌就是第二大的牌（当然，也有可能是并列最大)。经过 $n-1$ 轮排序后，就得到了有序的手牌

下图同样来自 深入浅出，用于理解

参考代码片段

for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++)
        if (a[j] > a[j + 1]) {
            int p = a[j];
            a[j] = a[j + 1];
            a[j + 1] = p;
        }
}

解法 3：插入排序

分析

一种很形象的比喻

你在玩纸牌游戏的时候，从牌堆里面抽牌，抽到一张牌，放到你的手牌里，你是怎么保证手牌内的牌是有序的呢？

如果你能通过 Cloudflare 的人机验证，你应该会看看抓到牌的大小，再看看手牌，定位到合适的位置，插入

上面描述的过程，即 插入排序

1. 把手牌分为有序的和无序的两部分
2. 最开始有序的就只有一张牌，也就是第一张
3. 要把接下来的 无序区 中的一张牌（称为 待插牌 ）插入到 有序区 中，就是从有序区的末尾开始往前比较，如果待插牌比正在比较的牌小，那么就把有序区的正在比较的牌往后面放一格，然后继续往前面进行比较，直到待插牌遇到不大于自己的牌或者成为第一个为止
4. 这时，待插牌就可以填入留出来的缺口中。反复将无序区中的待插牌插入到有序区中，直到所有的牌都在有序区

同样的，这里有一张非常生动的图，供读者查阅

下面这是来自 深入浅出 的 插入排序 实现代码，进行了注释的补充

for(int i = 1; i < n; i++) {
    int now = a[i], j;          // 记录待插入元素，稍候会放进去
    for(j = i - 1; j >= 0; j--) // 一个很经典的模板：元素后移
        if(a[j] > now)
            a[j + 1] = a[j];    // 大于now的元素后移
        else
            break;
    a[j + 1] = now;             // 插入到正确位置
}

选择排序

为了加强读者的记忆，这里重新梳理一遍

解法 1 这种算法被称为 选择排序

从代码中可以看出有两重循环，读者可以自己计算一下已知 $n$ 的情况下一共需要比较的次数

选择排序的算法时间复杂度是 $O(n^2)$；由于只需要一个数组存下这些数字即可，空间复杂度是 $O(n)$

冒泡排序

解法 2 这种算法被称为 冒泡排序，在一轮中，最大的那张牌会一点一点地从左移动到右边，像冒泡泡一样

读者也可以计算一下排序的过程中需要进行几次比较

冒泡排序算法的时间复杂度也是 $O(n^2)$，空间复杂度也是 $O(n)$

冒泡排序相比于选择排序并没有实质性的改进

有一种冒泡排序的改良版叫作希尔排序，不是相邻位置的两个数字比较，而是比较距离更远的两个数字，虽然能略微优化一些复杂度，但依然不实用

猴子排序同样也是一种奇怪的办法

插入排序

这种算法叫作 插入排序

如果序列本来已经从小到大排序，那么每次无序区的待插牌都不会插进有序区中，而是紧贴在有序区后使有序区一直扩大，那么只需要 $n-1$ 次比较就可以完成算法流程

然而，如果序列是从大往小排序，那么每次插入都会将有序区中的所有牌往后面挪动一次，这样速度就非常慢了

讲时间复杂度一般会考虑最悲观的情况，所以插入排序的算法复杂度还是 $O(n^2)$，和选择排序、冒泡排序的复杂度一致，它们空间复杂度也是一样的

不过，如果能保证序列 基本有序 , 那么使用插入排序的效率可能会不错

不推荐在 Contest 中使用这些方法，耗时过久

笔者认为，学习这些是为了掌握原理，在第一轮比赛中获得较好的成绩，在历年的 OI 比赛中，有相当一部分的套题涉及了这个内容

3 快速排序

【题目样本 3.1】P1177 快速排序

题目描述

https://www.luogu.com.cn/problem/P1177

输入 $n(n \lt 10^5)$ 个数字 $a_i(a_i \lt 10^9)$，将其从小到大排序后输出

分析

这个数据量就很大了，插入排序、选择排序、冒泡排序都无法完成。这次将介绍在 OI 中最普遍使用的排序算法 快速排序，简称快排，顾名思义

快速排序说起来其实也挺简单的，但是需要读者能够理解递归

void Qsort(int x, int y) {
    if (x >= y) return;          // 终止条件
    // ... 分区操作 ...
    Qsort(x, i);                 // 自己调用自己，排左边
    Qsort(i+2, y);               // 自己调用自己，排右边
}

算法的大致过程是对于一个无序序列，找到一个 哨兵数 ，将序列中所有比哨兵数小的数字都在哨兵数的左边，所有比哨兵数大的数字都在哨兵数的右边；然后分别对哨兵数左边和右边再使用同样的方法找到新的哨兵数，并再次进行分类，直到集合不可分割为止

怎么选择哨兵呢？随便选，可以是第一个，可以是中间那个，也可以在序列中随机选择

选择好哨兵，然后从序列左端开始寻找第一个比哨兵大的数字，从右边选择第一个比哨兵小的数字，然后交换这两个数；接着继续从左边找到比哨兵大的数字，右边比哨兵小的数字并交换……直到将序列分为两组，左边序列都不大于哨兵，右边序列都不小于哨兵，就可以分别对左边和右边进行排序了

下面同样还有一张生动的图，建议配合代码食用

参考代码

有多种办法可以实现，这是一种实现办法，也基于书本内容进行了适当的补充更多的办法请前往 排序的应用 这一章节

void qsort(int a[], int l, int r) { // a[] 传递数组
    int i = l, j = r, flag = a[(l + r) / 2], tmp;  // flag是基准值（哨兵）
    do {
        while (a[i] < flag) i++;   // 左指针右移，跳过比基准小的
        while (a[j] > flag) j--;   // 右指针左移，跳过比基准大的
        if (i <= j) {              // 找到一对需要交换的数
            tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            i++; j--;              // 继续移动指针
        }
    } while (i <= j);              // 两指针未交错就继续
    if (l < j) qsort(a, l, j);     // 递归排左半部分
    if (i < r) qsort(a, i, r);     // 递归排右半部分
}

快速排序

虽然在极端情况下（比如数列已经有序，且每次选择哨兵都会分出长度为 $1$ 的小段），快速排序的时间复杂度是 $O(n^2)$，但是如果随机选择哨兵，则很难出现这种情况

实际上，随机化快速排序的算法复杂度是 $O(n \log n)$，空间复杂度是 $O(n)$，而且不需要额外的辅助空间，所以是一种最为实用的排序算法

快速排序利用了 分治 思想，后面可能会出一篇 排序 这一专题的补充篇，介绍了更多的非基础排序

额外的，二分查找法 也利用了 分治思想，这个方法也可能会在未来单独出一篇专题进行讲解

【题目样本 3.2】 P1923 求第 $k$ 小的数

题目描述

https://www.luogu.com.cn/problem/P1923

输入 $n(n \lt 10^6 \text{ 且 } n \text{ 为奇数})$ 个数字 $a_i(a_i \lt 10^9)$，输出这些数字的第 $k$ 小的数，最小的数是第 $0$ 小

分析

如上 URL 中的 题目描述，如果你是真的要训练 快排，请 不要 使用 nth_element STL，当然我估计你也不知道

虽然可以直接排序，然后取数组中的第 $k$ 个作为答案进行输出，但是直接排序一遍的复杂度是 $O(n \log n)$，不适合这道头目，我们可以借鉴 快排 的 分治思想 把时间复杂度降至 $O(n)$

和快速排序的方法一样，任意取一个哨兵，将序列分为两部分，左边部分的所有数字都不大于右边的数字

• 如果 $k$ 在左边的范围，则递归求解左边的部分
• 如果在右边，则递归求解右边的部分
• 但是也有可能两边都不属于（比如说 $j=4$ 而 $i=6$ , 但刚好 $k=5$)，那么直接就可以给出答案

参考代码

这个代码是 深入浅出 提供的，由 Deepseek V4 Pro 和 笔者 改写而得

int ans = 0, k; // 记录答案，以及求第 k 小
void findkth(int a[], int l, int r) { // 引入数组的地址
    if(l == r) {
        ans = a[l]; // 区间长度为 1 时，记录答案
        return;
    }

    int i = l, j = r, flag = a[(l + r) / 2], tmp;
    do {
        while (a[i] < flag) i++; // 从左找比哨兵大的数
        while (a[j] > flag) j--; // 从右找比哨兵小的数
        if (i <= j) { // 交换
            tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            i++; j--;
        }
    } while (i <= j);

    if (k <= j) findkth(a, l, j); // 第 k 小的数字在左区间
    else if (i <= k) findkth(a, i, r); // 第 k 小的数字在右区间
    else findkth(a, j + 1, i - 1); // 第 k 小的数字既不在左区间，也不在右区间
}

尽管 此参考代码片段（快速选择） 相对于 快排（模板代码）类似，但是每次处理的区间长度期望下都会被减半，复杂度是线性的

快速排序 - 快速选择

这个概念是在书中没有的，是由 Deepseek V4 Pro 提出

它基于 快速排序 的分治思想，但并不是完整的排序算法，而是一种 选择算法 ——专门用来查找数组中第 $k$ 小（或第 $k$ 大）的元素

下面是一张表格，阐释了区别

所以，这种方法叫做 快速选择，也可以理解为"快速排序的简化版"或"基于快排分治的选择算法"

4 排序的应用

这里提供了一些 排序 的拓展用法，在第二轮比赛时可能有用

【题目样本 4.1】P1059 [NOIP 2006 普及组] 明明的随机数

题目描述

https://www.luogu.com.cn/problem/P1059

给出 $N(N \lt 10^2)$ 个 $1 \sim 10^3$ 的数字，输出去重后剩余数字的个数以及去重排序后的序列

解法 1：计数排序

在拿到新的选票时发现投票箱中已经有这个选票了，就扔掉这张选票，保持每个票箱中最多只有一张票

最后将有票的票箱编号输出即可

这里要求先输出不同数字的个数，可以先枚举一遍票箱记录，输出剩余数字的个数，然后再枚举一遍票箱，输出序列

也可以创建一个新的数组，在枚举票箱的时候将有票的编号复制进新的数组中

解法 2：STL

当然也可以直接对这些数据进行排序，然后从小到大每个数字只输出一个

考虑数据规模，可以使用上面提到的所有排序方式

不过，这次介绍排序的 STL， 这样就不需要去亲自实现排序算法了

关于 STL，后面可能会出一个专门的专题，STL = Standard Template Library（标准模板库）

有了这个就不用自己手搓了

排序 STL 1：sort

分析

std::sort 被定义于 algorithm 头文件中，因此，你在使用前需要先导入这个头文件，为了方便笔者，笔者会尽可能地在后文省略较多的不影响理解的内容

sort 的基本用法如下

// 形式1：默认升序排序
sort(起始迭代器, 结束迭代器);

// 形式2：自定义比较规则
sort(起始迭代器, 结束迭代器, 比较函数/仿函数/Lambda); // 比较函数即 cmp 用的较多

一个例子，sort(a,a+n,cmp)，对 $a[]$ 数组从 $a[0]$ 到 $a[n-1]$ 进行排序，cmp 是指自定义排序函数，如果是将数组 $a[]$ 从小到大排序，那么这一项可以省略

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
int const MAXN = 1010;
int a[MAXN], ans[MAXN], n, cnt = 0, tmp = -1;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
    if (a[i] != tmp) ans[cnt++] = a[i]; /* 当前的和上一个不同才复制到新数组 */
    tmp = a[i];
    }
    cout << cnt << endl;
    for (int i = 0; i < cnt; i++) cout << ans[i] << ' ';
    return 0;
}

sort

这里，sort 的时间复杂度是 $O(n \log n)$

如果要对数组 $a[1]$ 到 $a[n]$ 排序，就要用 sort(a+1, a+n+1)

那么，如果要求从大到小排序，只需要定义一个名字是 cmp 的自定义比较函数即可，这个函数的输入是两个元素，如果第一个在第二个之前，则返回 true, 否则返回 false。代码如下：

bool cmp(int q,int h){ // q 前 h 后
    return q>h;
}

排序 STL 2：unique

分析

std::unqiue 同样被定义于 algorithm 头文件中

unique(a,a+n)：对 $a[]$ 数组从 $a[0]$ 到 $a[n-1]$ 进行去重，要求 $a[]$ 数组已经有序，返回去重后最后一个元素对应的指针

如果使用 unique, 就可以不用 ans 新数组了，可以直接获得去重后的数组和最终元素个数

参考代码

sort(a,a+n);
cnt=unique(a,a+n)-a; // 剩下的数总数
cout<<cnt<<"\n";
for(int i=0;i<cnt;i++) cout<<a[i]<<" ";

【题目样本 4.2】P1093 [NOIP 2007 普及组] 奖学金

题目描述

https://www.luogu.com.cn/problem/P1093

有 $n$（$n \le 300$）名学生的语文、数学、英语成绩，这些学生的学号依次是从 $1$ 到 $n$。需要对这些学生进行排序。如果总分相同，则语文分数高者名次靠前；如果语文成绩还相同，学号小者靠前。输出排名前 $5$ 的学生学号和总分

解法 1：STL

分析

定义一个 struct 结构体，命名为 student 存储学生各项信息，使用 sort 附带 cmp 比较函数进行排序，最后输出排序结果，下面是排序优先级

1. 总分，高者优先
2. 语文，高者优先
3. 学好，小者优先

参考代码

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

int const MAXN = 310;
int n;

struct student {
    int id, chinese, total;
} a[MAXN];

int cmp(student a, student b) {
    if (a.total != b.total) return a.total > b.total;      // 总分先定胜负
    if (a.chinese != b.chinese) return a.chinese > b.chinese; // 然后比语文
    return a.id < b.id;                                    // 最后比学号
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int math, english;
        cin >> a[i].chinese >> math >> english;
        a[i].total = a[i].chinese + math + english;
        a[i].id = i + 1;
    }

    sort(a, a + n, cmp);

    for (int i = 0; i < 5; i++) {
        cout << a[i].id << " " << a[i].total << endl;
    }

    return 0;
}

解法 2：选择排序

分析

时间复杂度 $O(kn)$，此题 $k=5$，即 $O(n)$

解法 3：插入排序

分析

维护排名前 $5$ 数组作为比较对象（手牌）

时间复杂度 $O(n)$，运行效率不高

【题目样本 4.3】P1781 宇宙总统

题目描述

https://www.luogu.com.cn/problem/P1781

共有 ( n )（( n \le 20 )）个非凡拔尖的人竞选总统，现在票数已经统计完毕，请算出谁能够当上总统。第一行输出候选人编号，第二行输出选票数量。票数可能很大，最大会有 100 位

解法 1：计数排序

分析

由于本题只需要求出最大的那一个数字，所以用“打擂台”法

但是数字很大，没办法直接存下来（long long 也存不下）

但是需要高精度，不考虑单开一个话题

解法 2：结构体

分析

存进字符串。不过不能直接对这些字符串进行大小比较，因为字符串比较是比较字典序（第一位小的在前面，如果相同则比较第二位，以此类推），例如 $10000$ 小于 $1200$ 小于 $200$

得手搓 cmp

参考代码

struct node {
    string x;    // 票数
    int num;     // 候选人编号
} s[MAXN];

bool cmp(node a, node b) {
    if (a.x.length() != b.x.length()) {
        return a.x.length() > b.x.length(); // a 比 b 位数多时 a 在前面
    }
    return a.x > b.x; // 位数相同，但 a 字典序排列比 b 大
}

5 汇总

练习

笔者为读者提供了一些洛谷上没有的题目，供练习

• 计数排序
• 选择排序
• 冒泡排序
• 插入排序
• 快速排序

C++ 常用排序算法一览表

额外的，这里有一张特别大的表格，供读者查阅

C++ STL 中的排序一览表

同时，这里还有一张关于 STL 的表