@Dmaxiya
2026-01-20T16:11:19.000000Z
字数 2026
阅读 126
Hello_World
比赛链接：寒假第一次培训 排序
排序是每位同学都接触过一些的算法。c语言课内我们学过冒泡排序、选择排序、插入排序，数据结构课内学过快速排序、归并排序（估计早就忘了吧。。）。是不是觉得排序算法很多呢？事实上，常用的排序算法甚至还不止这几种（如堆排序、基数排序等等）。
啊，好多啊，都没怎么听过，学不会啊，怎么办！
别慌，面对竞赛入门，我们首先需要学会的仅仅是如何在比赛中以最快的方式实现排序功能（以后再去深入了解上面提到的各类排序算法实现）。其实c++在头文件里，早已帮你实现好了一个排序函数std::sort()。
本节除第一题外所有练习，请使用std::sort()函数完成。
本章练习重点不在于算法原理（各种排序算法如何实现，如何根据实际场景选择使用哪种排序），而在于编程应用（如何在各种情况下使用sort()函数）。
1、学习使用std::sort()函数的基本用法。基本框架如下：
// 写一下其他你需要的头文件，如stdio.h#include<algorithm> // sort()等很多常用基础算法函数的头文件，请背下这个英文单词，这个头文件很常用using namespace std; // 如果写了这句，代码里用sort()时可以去掉前面的"std::"// 上面这行是c++语法，如果你想理解他的含义，可以随机抽一个答疑同学让他给你发一段语音。// 没学过c++不会影响本节练习，除了我给出的框架，其他部分你按c语言语法写就行。对上面头文件、c++概念有任何问题，直接抽个答疑同学问下，弄清楚再写题int main(){//......sort(xx,xx,...); // 具体怎么用？看资料吧！//......return 0;}
2、学习自定义std::sort()的排序规则，从而对结构体、特殊规则做排序。
基础部分为必须掌握的。提高部分可以为你打下更牢固的算法基础。（务必保证基础部分掌握，若无余力可跳过提高部分。学习基础部分足够解决训练题）
【基础】学习函数sort()的基本用法，如给定一个数组，如何使用sort()函数对数组做排序。学完可做练习题1。
【基础】复习结构体的基本用法，了解就行，不需要对着教材重新一页一页看一遍。
【基础】学习如何自定义比较函数，并结合sort()函数，实现按照你所制定的规则对数组或结构体数组做排序。学完你就有能力做本节所有题了。
【提高】学会如何分析带有sort()函数的代码的时间复杂度。
【提高】如果你没学过c++且对c++理论有兴趣，可学习一下什么叫“重载”。在你自定义比较函数时，其实就是一次重载。
【提高】如果你学过c++且对c++实战有兴趣，可以尝试练习用string、vector、pair等stl容器结合sort()。
【提高】学习如何使用lambda函数作为自定义比较函数。这种高阶用法会让你的代码看起来更简洁。
【提高】学习常见的7～10种排序算法的原理，了解他们的区别和适用场景。如果你真的很感兴趣，推荐你学习后在本地尝试手写实现这些常见排序算法（寒假就不必了，相信大多数同学没这精力。。）。我在面腾讯实习的时候，遇到两次让我手写某种特定的排序算法的具体实现（虽然这种题让人有点无语。。）。
【提高】了解sort()函数底层实现原理，它和那几种常见排序算法，有什么关系？
鼓励大家根据上述提纲，自行在网上搜索资料（视频/博客）学习。举个例子，比如你想学习sort()函数，你可以在百度或b站直接搜索“std::sort()用法”，看几篇博客学习基础用法和代码样例。
这里提供一篇lx同学（电信16级，曾任社团核心组，现保送华科读博）写的总结参考，可以在你做过几题后再复习一下：sort知识点总结
学习资料：
cmp()函数：cmp是compare的缩写，自定义sort()比较规则时，通过自定义一个cmp()函数，把规则传给sort()。cmp只是一个习惯叫法，本质还是自定义函数，你写代码的时候把它改名为pmc，cpm，都可以正常运行。
sort在比赛中有三种运用可能，一是以简单题形式出现，二是在别的算法题里使用sort帮忙处理数据，三是一些很难的算法题，快速写个sort，不讲武德，搞偷袭，骗过几个测试点骗点分。
本节选的蓝桥杯原题，都属于比赛中不能丢分的题。斟酌一下再提交，争取做到提交后一次100%通过！（比赛中无法看到题目得分，你斟酌后决定提交的代码，就是你最后的分数）
本节第一题和主题无关，不需要用sort()