C++排序详解:sort函数与自定义cmp函数
需积分: 25 150 浏览量
更新于2024-08-24
收藏 310KB PPT 举报
"这篇资源主要介绍了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`排序的基本用法、自定义比较函数的编写,以及桶排序的概念和简单应用。这些知识对于理解和实现各种排序算法具有重要意义。
2020-02-14 上传
2019-08-29 上传
2009-05-09 上传
2011-07-10 上传
2021-11-30 上传
2024-05-19 上传
2023-10-18 上传
点击了解资源详情
点击了解资源详情
涟雪沧
- 粉丝: 19
- 资源: 2万+
最新资源
- AA4MM开源软件:多建模与模拟耦合工具介绍
- Swagger实时生成器的探索与应用
- Swagger UI:Trunkit API 文档生成与交互指南
- 粉红色留言表单网页模板,简洁美观的HTML模板下载
- OWIN中间件集成BioID OAuth 2.0客户端指南
- 响应式黑色博客CSS模板及前端源码介绍
- Eclipse下使用AVR Dragon调试Arduino Uno ATmega328P项目
- UrlPerf-开源:简明性能测试器
- ConEmuPack 190623:Windows下的Linux Terminator式分屏工具
- 安卓系统工具:易语言开发的卸载预装软件工具更新
- Node.js 示例库:概念证明、测试与演示
- Wi-Fi红外发射器:NodeMCU版Alexa控制与实时反馈
- 易语言实现高效大文件字符串替换方法
- MATLAB光学仿真分析:波的干涉现象深入研究
- stdError中间件:简化服务器错误处理的工具
- Ruby环境下的Dynamiq客户端使用指南