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()的灵活运用、自定义比较函数、归并排序求逆序对等核心技能就能应对绝大多数排序题目。刷题的关键在于多总结、多归纳把相似题型的套路提炼出来。
企业数字化 ERP 产品动态
相关推荐
3个实战案例教你用WordPress判断浏览器防挂马 3个实战案例教你用WordPress判断浏览器防挂马 网站被黑挂马不知道怎么办?别慌,我见过太多独立站长因为没做好环境识别,导致恶意脚本在特定浏览器下才执行,Google Search Console… · 2026/9/27 6:54:39
python分支结构复习 python分支结构复习
# 单路分支 if...
if 条件:条件成立时要做的事情# 二路分支 if...else...
if 条件:条件成立要做的事情
else:条件不成立时要做的事情# 多路分支 if...elif...else...
if 条件1:语句1
elif 条件2:语句2
elif 条件n:语句n
else:语句e · 2026/9/27 6:54:39
Chrome EC 系统架构解析 1. EC 是什么:Chromebook 的"隐形管家"EC(Embedded Controller,嵌入式控制器)是 Chrome OS 设备上的一颗独立低功耗微控制器。当主处理器(AP)关机、休眠甚至完全断电时,EC 仍在运行—… · 2026/9/27 6:54:33
MySQL数据库设计与规范 在信息化时代,数据库的设计与使用成为构建任何信息系统的核心环节。如何设计一个高效且规范化的数据库,直接影响系统的可扩展性、数据的完整性与一致性。规范化的数据库设计不仅能提高数据处理效率,还可以避免冗余和不必要的错误。
在这个教程中,将探讨数据库设计的核心原… · 2026/9/27 7:31:09
新手入门网站页面设计代码,3招避开建站公司高价坑 新手入门网站页面设计代码,3招避开建站公司高价坑 找建站公司报价三万五,自己写代码只要花三百块买服务器?别被销售的话术绕晕了。很多新手刚入行,看着那些花里胡哨的Demo,心里直打鼓:这代码到底值不值这个价?其实, 网站页面设计代码… · 2026/9/27 7:31:09
MySQL主键、外键与约束 在数据库设计中,关系型数据库依赖于良好的结构和约束来确保数据的完整性和一致性。主键、外键和各种约束在数据库设计中扮演着至关重要的角色。理解这些概念及其应用是构建可靠数据库的基础。
在本教程中,重点介绍主键、外键和常见的约束类型,如唯一性约束和非空约束,结合… · 2026/9/27 7:31:09
MySQL索引与查询优化 在数据库系统中,索引是一个重要的概念,用于提升查询性能。在处理大规模数据时,如何优化查询以获得更高的性能,是每一位开发者都必须掌握的技能。索引的存在能够加速数据检索的速度,减少系统的资源消耗。然而,索引并非万能,错误的索引使用可能会导致查询性能的下降,甚至… · 2026/9/27 7:31:09
MySQL外连接与子查询 数据库管理和操作是编程过程中至关重要的一环,而在进行复杂数据查询时,外连接和子查询的使用是非常常见且重要的。理解这两者的概念和应用场景,不仅可以提高数据查询的灵活性,还能让查询结果更加精准和有效。
本文将深入探讨 MySQL 中的外连接(LEFT JOIN 和 RIGHT JOIN)… · 2026/9/27 7:31:03
OrchardCore Display Drivers 权威指南:为内容部件、字段与模型构建 Shape 的完整实现方案 CMS后端Web框架 【免费下载链接】OrchardCore Orchard Core is an open-source modular and multi-tenant application framework built with ASP.NET Core, and a content management system (CMS) built on top of that framework. 项目地址: https://gitcode.com… · 2026/9/27 7:30:32
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现 简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01
汕头网站建设制作厂家避坑指南:5大注意事项救急 汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习 简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现 简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01
汕头网站建设制作厂家避坑指南:5大注意事项救急 汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习 简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01