1. 引言排序是算法竞赛中最基础也最重要的内容之一。洛谷Luogu作为国内最受欢迎的 OJ 平台提供了大量优质的排序相关题目。本文总结了我在洛谷刷排序题过程中的经验与心得涵盖常见排序算法的应用场景、题目套路与解题技巧希望能帮助初学者少走弯路。2. 排序算法基础回顾在开始刷题之前先快速回顾几种常见排序算法的特点算法平均时间复杂度空间复杂度稳定性适用场景冒泡排序O(n²)O(1)稳定教学演示、小规模数据选择排序O(n²)O(1)不稳定小规模数据插入排序O(n²)O(1)稳定近乎有序的数据归并排序O(n log n)O(n)稳定大规模数据、求逆序对快速排序O(n log n)O(log n)不稳定通用排序堆排序O(n log n)O(1)不稳定需要原地排序在竞赛中我们通常直接使用 C 标准库的qsort()函数但理解底层原理对解决变种题目至关重要。3. 洛谷排序经典题目分类3.1 基础排序题这类题目直接考察排序的基本应用通常只需要调用sort()即可解决。P1059 [NOIP2006 普及组] 明明的随机数题目要求去重后排序。核心思路是用数组储存数据输入时做去重处理再从小到大遍历输出实现排序或者用unique()函数#include stdio.h int main() { int N,i,num; int cnt[1001]{0}; int M0; //M统计数字个数 scanf(%d,N); for(int i0;iN;i){ scanf(%d,num); if(cnt[num]0){ M; } cnt[num]1; //标记已有数字 } printf(%d\n,M); for(int i0;i1000;i){ if(cnt[i]1){ printf(%d ,i); } } return 0; }P1781 宇宙总统比较两个大数字符串形式的大小按票数降序排序。注意不能直接用字符串比较需要先比较长度#include string.h int cmp(const void *x, const void *y) { char *a *(char **)x; char *b *(char **)y; int la strlen(a), lb strlen(b); if (la ! lb) return lb - la; return strcmp(b, a); }3.2 结构体排序当排序对象包含多个字段时需要自定义比较规则。P1068 [NOIP2009 普及组] 分数线划定按分数降序排序同分按报名号升序然后按比例划定分数线。这里需要自定义比较函数typedef struct{ int id; int score; }Student; int cmp(const void*a,const void*b){ Student *s1(Student *)a; Student *s2(Student *)b; if(s1-score ! s2-score){ return s2-score-s1-score; }else{ return s1-id-s2-id; } }P1104 生日按生日从早到晚排序同年月日则后输入的排前面。这类题目考察对比较规则的细致理解。typedef struct{ char name[25]; int y, m,d; int idx; }student; int cmp(const void *a,const void *b){ student *s1 (student *)a; student *s2 (student *)b; if(s1-y ! s2-y) return s1-y - s2-y; else if(s1-m ! s2-m) return s1-m - s2-m; else if(s1-d ! s2-d) return s1-d - s2-d; else return s2-idx - s1-idx; }3.3 排序 贪心排序往往是贪心算法的前置步骤先排序再按某种策略选择。P1223 排队接水按接水时间从小到大排序总等待时间最短。这是经典的贪心 排序问题struct Person { int time, id; }; int cmp(const void *x, const void *y) { struct Person *a (struct Person *)x; struct Person *b (struct Person *)y; return a-time - b-time; }3.4 逆序对P1116 车厢重组题目要求通过相邻交换将车厢按编号从小到大排列求最少交换次数。每次相邻交换会使逆序对数量减少 1因此最少交换次数就是逆序对数量经典解法是归并排序#include cstdio int a[1005]; inline int read() { int x0;char chgetchar(); while(ch0||ch9) chgetchar(); while(ch0ch9) xx*10ch-0,chgetchar(); return x; } int main() { int n read(); for(int i0;in;i) a[i]read(); int ans0; for(int i0;in;i) { for(int ji1;jn;j) { if(a[i]a[j]) ans; } } printf(%d,ans); return 0; }关于快读函数 read() 的解释代码中的read()是一个自定义的快速读入函数用于替代scanf()读取整数。它的核心原理是逐字符读取输入跳过非数字字符再累加得到数值从而减少函数调用开销、提升输入效率。具体拆解如下int x0; char chgetchar();初始化结果变量并用getchar()读取第一个字符。while(ch0||ch9) chgetchar();跳过所有非数字字符如空格、换行、负号前的空白直到遇到数字字符为止。while(ch0ch9) xx*10ch-0, chgetchar();连续读取数字字符每读一位就把当前结果乘以 10 再加上该位数字ch-0把字符转为对应数值直到读到的不是数字为止。return x;返回累加得到的整数。在本题中数据规模较小使用快读并非必需但它能帮助理解竞赛中常见的输入优化技巧。需要注意的是这个read()只处理非负整数不支持负数输入。4. 刷题路线推荐以下是我推荐的洛谷排序题刷题顺序入门P1059、P1068、P1781基础P1104进阶P1116车厢重组综合P1093奖学金建议每道题先独立思考 20-30 分钟再看题解最后自己独立 AC。5. 常见错误与注意事项5.1 比较函数写错最常见的错误是比较函数不满足严格弱序导致排序结果不确定甚至 RE。例如// 错误写法相等时返回 true违反反对称性 bool cmp(int a, int b) { return a b; } // 正确写法 bool cmp(int a, int b) { return a b; }5.2 忘记处理边界情况数组长度为 0 或 1 时所有元素相等时数据范围超过 int 时用 long long5.3 排序后下标错乱排序会打乱原数组的下标关系如果需要保留原下标可以在结构体中记录struct Node { int val, idx; // idx 记录原始下标 };6. 总结排序是算法竞赛的基石洛谷上的排序题从基础到进阶覆盖了各种考察角度。掌握sort()的灵活运用、自定义比较函数、归并排序求逆序对等核心技能就能应对绝大多数排序题目。刷题的关键在于多总结、多归纳把相似题型的套路提炼出来。
