CSP-J/S冲奖第17天:sort函数

一、什么是 sort 函数？

• 定义：sort 是 C++ 标准库提供的高效排序函数。
• 优势：
• 时间复杂度为 (O(n \log n))，远快于冒泡排序（(O(n^2))）。
• 代码简洁，适合竞赛快速实现排序。

二、基本语法

1. 头文件

#include  // 必须包含此头文件

2. 基本用法

sort(起始地址, 结束地址); // 默认升序排序

• 参数说明：
• 起始地址：要排序的数组或容器的起始位置。
• 结束地址：要排序的数组或容器的结束位置（不包含该位置）。

三、升序与降序排序

1. 升序排序（默认）

int arr[] = {5, 2, 9, 1, 5};
sort(arr, arr + 5); // 排序后：1, 2, 5, 5, 9

2. 降序排序

int arr[] = {5, 2, 9, 1, 5};
sort(arr, arr + 5, greater<int>()); // 排序后：9, 5, 5, 2, 1

• 说明：需要包含 头文件。

四、自定义排序规则

1. 使用比较函数

• 示例：按绝对值大小排序

#include 
#include 
using namespace std;

bool compare(int a, int b) {
    return abs(a) < abs(b); // 按绝对值升序
}

int main() {
    int arr[] = {-5, 3, -2, 4};
    sort(arr, arr + 4, compare);
    // 排序后：-2, 3, 4, -5（绝对值为 2, 3, 4, 5）
    return 0;
}

五、竞赛中的常见用法

1. 对数组排序

int arr[100];
sort(arr, arr + n); // n 是数组元素数量

2. 对部分数组排序

int arr[] = {5, 3, 8, 1, 6};
sort(arr + 1, arr + 4); // 仅排序索引 1 到 3 的元素 → 3, 5, 8, 1, 6

六、注意事项

1. 头文件：
• 必须包含 ，否则会报错。
2. 数组越界：
• 确保 结束地址 不超过数组的实际大小。
3. 自定义规则：
• 比较函数需返回 bool 值，且参数类型与数组元素一致。

七、综合练习

练习 1：排序学生成绩

输入 n 个学生的成绩，按升序输出。

参考代码：

#include 
#include 
using namespace std;

int main() {
    int n;
    cin >> n;
    int scores[n];
    for (int i = 0; i < n; i++) {
        cin >> scores[i];
    }

    sort(scores, scores + n); // 升序排序

    for (int i = 0; i < n; i++) {
        cout << scores[i] << " ";
    }
    cout << endl;

    return 0;
}

练习 2：找出数组中的最大值

输入一个数组，找出最大值（使用 sort 简化代码）。

参考代码：

#include 
#include 
using namespace std;

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n); // 升序排序
    cout << "最大值：" << arr[n - 1] << endl; // 最后一个元素

    return 0;
}

八、总结

1. sort 函数是竞赛中必备的高效排序工具。
2. 默认升序，可通过 greater() 或自定义函数实现降序。
3. 掌握 sort 的基本用法和自定义规则，能显著提升代码效率。