ACM_ICPC竞赛中sort函数的简要介绍

文/焦静颐 崔驭 贾子璇

1 sort函数的介绍及优点

sort函数是STL中用于对给定区间进行排序的函数，所在头文件是#include 。主要原理是快速排序，但又不是简单的快速排序，它还结合了插入排序和堆排序，根据需要排序对象的不同情况，自动选用合适的排序方法。所以虽然理论上sort函数和快速排序的复杂度都是O(n*logn)，但在实际应用中，sort函数比快速排序的效率更高，实用方法简单，因此更加实用。

2 sort函数的使用方法

sort函数有三个参数

（1）要排序数组的起始地址。

（2）要排序数组的结束地址，即最后一个要排序地址的下一个地址。

（3）排序方法，可以是从大到小，也可以自定义，也可以不写，如果不写，默认的排序方式是从小到大排序。

sort函数使用模板是：

sort(start,end,cmp);

对区间[f irst,last)根据cmp的方式进行排序。

3 sort函数的用法举例

3.1 直接使用

整型默认为从小到大排序，字符型根据ASCII码值进行排序。

N为整型常数，f irst为起始地址，last为结束地址。

3.2 自定义排序

3.2.1 自定义比较函数

系统默认为x>y返回true，故程序是从大到小排序。

3.2.2 重载比较运算符

这种方法用于结构体中。

根据成员a的数值由大到小排序，当a的数值相同时，根据成员b的数值由小到大排序。

4 结束语

sort函数在使用上带来极大便利，因为高效率，使用灵活的特点，无论是在日常开发中还是算法竞赛中，sort函数都能发挥很大的作用。本文介绍了sort的使用方法，只要加以练习，就可以将sort函数更好的应用。掌握好sort函数对学生学习其他STL函数也有很大帮助，可以提高学生的编程能力。