C++ STL sort深度解析：自定义排序与蓝桥杯实战

"STL应用——第一天课程sort.pptx" STL，全称为Standard Template Library，是C++编程语言中的一个核心库，它提供了一系列高效、可复用的容器（如vector、list、set等）、算法（如排序、搜索、变换等）以及迭代器。在本课程中，重点讲解了STL中的排序算法sort，它是C++标准库algorithm中的一个功能强大且高效的工具。 1. SORT介绍 sort函数是用于对给定的元素区间进行排序的，其内部实现基于快速排序的变种，具有平均时间复杂度O(n log n)的优秀性能，这使得它在处理大量数据时能保持较高的执行效率。使用sort函数需要包含<algorithm>头文件。 2. sort使用方法 sort函数接收三个参数：起始地址first、结束地址last以及一个可选的比较函数或谓词cmp。默认情况下，sort会按照从小到大的顺序对元素进行排序。例如： ```cpp sort(a, a + n); // 对数组a[0]到a[n-1]进行排序 ``` 如果需要自定义排序规则，可以传递一个比较函数对象作为第三个参数。这个比较函数应当接受两个参数，并返回一个布尔值，表示前一个参数是否应该出现在后一个参数之前。 3. 自定义排序 - (1) 自定义比较函数cmp 自定义函数可以这样编写： ```cpp bool cmp(int a, int b) { return b < a; // 反转默认排序，使元素从大到小排列 } sort(a, a + n, cmp); ``` - (2) 重载比较运算符“<” 如果要对自定义类型（如Student）进行排序，可以重载小于运算符`<`来定义排序规则： ```cpp struct Student { int age; string name; bool operator<(const Student& s2) const { if (age == s2.age) return name < s2.name; // 年龄相同，按姓名排序 else return age > s2.age; // 年龄排序 } }; sort(a, a + n); ``` - (3) 声明比较类 使用比较类的方式同样可以自定义排序规则： ```cpp struct cmp { bool operator()(const Student& s1, const Student& s2) const { if (s1.age == s2.age) return s1.name < s2.name; else return s1.age < s2.age; } }; sort(a, a + n, cmp()); ``` 4. 真题讲解 在实际应用中，例如第八届蓝桥杯竞赛中的日期问题，sort函数可以帮助我们对一组日期进行排序。假设我们有一个日期类Date，包含年、月、日属性，我们可以为Date类重载比较运算符`<`，然后使用sort对日期列表进行排序： ```cpp struct Date { int year, month, day; bool operator<(const Date& d2) const { if (year != d2.year) return year < d2.year; else if (month != d2.month) return month < d2.month; else return day < d2.day; } }; Date dates[]; // 日期数组 sort(dates, dates + n); // 对日期进行排序 ``` 通过这样的方式，STL的sort函数结合自定义排序规则，能够方便地处理各种复杂的排序需求，无论是简单的整数排序，还是复杂的自定义类型排序。熟练掌握STL的sort函数及其自定义排序机制，将极大地提升C++编程的效率和代码质量。