C++排序详解：sort函数与自定义cmp函数

"这篇资源主要介绍了C++中的排序方法，包括使用内置的`sort`函数以及自定义比较函数（cmp函数）进行结构体排序。同时，提到了桶排序的概念，并给出了一个简单的应用示例。" 文章详细内容： 一、sort排序 `sort`是C++标准库中的一个函数，它具有O(n*log(n))的时间复杂度，包含在`<algorithm>`头文件中。该函数通常用于对数组或容器进行排序，接受三个参数：要排序的序列的起始和结束指针，以及一个可选的比较函数对象。默认情况下，`sort`按照升序排列元素。 例如，对于整型数组`inta[]={2,7,1,5,0}`，可以使用以下方式对其进行排序： ```cpp #include <algorithm> sort(a, a + 5); // 默认升序排序 ``` 若要进行降序排序，可以提供额外的比较函数，如`greater<int>()`： ```cpp sort(a, a + 5, greater<int>()); // 降序排序 ``` 对于结构体排序，假设我们有一个名为`stu`的结构体，包含学号`xuehao`和成绩`chengji`，可以定义一个自定义比较函数`cmp1`来根据成绩排序： ```cpp typedef struct stu { int xuehao; int chengji; } stu; stu p[20]; bool cmp1(stu a, stu b) { return a.chengji > b.chengji; // 高分在前 } sort(p, p + 20, cmp1); ``` 二、自定义比较函数（cmp函数） 自定义比较函数通常是一个返回布尔值的函数，用来定义排序规则。例如，如果需要按照整数的降序排列，可以定义如下： ```cpp bool cmp2(int a, int b) { return a > b; // 大数在前 } ``` 如果有结构体成员间的复杂排序需求，如根据两个成员的值进行排序，可以定义更复杂的比较函数，如`cmp3`： ```cpp struct node { int x, y; }; node a[10]; bool cmp3(node a, node b) { if (a.x != b.x) return a.x < b.x; else return a.y < b.y; // 当x相等时，按y升序排序 } ``` 三、桶排序 桶排序是一种分布式排序算法，适用于数据范围在一定区间内且分布均匀的情况。例如，若有一组分数（0-10分）需要排序，可以创建一个大小为11的数组`a[11]`，将每个分数对应的桶计数。遍历原始数据，增加相应桶的计数，最后按照桶的顺序输出，完成排序。 ```cpp int a[11] = {0}; // 初始化所有桶计数为0 // 假设有成绩数据 scores[] for (int i : scores) { a[i]++; } // 从0开始，依次输出每个桶中的元素 for (int i = 0; i <= 10; i++) { for (int j = 0; j < a[i]; j++) { printf("%d ", i); } } printf("\n"); ``` 以上就是`sort`排序的基本用法、自定义比较函数的编写，以及桶排序的概念和简单应用。这些知识对于理解和实现各种排序算法具有重要意义。