排序

排序的定义

排序所起到的作用是把一组“无序”的数据通过一些操作变为“有序”的操作，在算法竞赛中，数据的“有序”可以让我们更快更简单的去达到某些目标。

sort函数

sort排序

sort是C++中提供的一个排序函数,使用时需要导入<algorithm> 头文件；
sort函数的使用方法为sort(begin, end)，其中begin和end分别是需要排序的数组的起始位置和结束位置。
sort函数默认是按照从小到大的顺序进行排序的。如果想自定义排序规则，需要指定第三个参数, cmp（需要自己定义排序规则返回值为bool类型）

整数从小到大排序

sort 函数排序默认左闭右开区间，也就是在给指定区间内的元素进行排序时，包含左边界元素，不包含右边界元素。

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    sort(arr, arr + 6);
    for (int i = 0; i < 6; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

整数从大到小排序

#include <algorithm>
#include <iostream>
using namespace std;   
bool cmp(int a, int b) {
    return a > b; // 返回true表示a在b前面
}
int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    sort(arr, arr + 6, cmp); // 使用自定义的比较函数
    for (int i = 0; i < 6; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

字符串从小到大排序

注意

字符串排序是按照字典序进行的，即先比较第一个字符，如果相同则比较第二个字符，以此类推。
如果字符串长度不同，较短的字符串会排在前面。

#include <algorithm>
#include <iostream>
using namespace std;
int main() {
    string arr[] = {"apple", "orange", "banana", "grape"};
    sort(arr, arr + 4); // 对字符串数组进行排序
    for (int i = 0; i < 4; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

字符串从大到小排序

#include <algorithm>
#include <iostream>
using namespace std;
bool cmp(string a, string b) {
    return a > b; // 返回true表示a在b前面
}
int main() {
    string arr[] = {"apple", "orange", "banana", "grape"};
    sort(arr, arr + 4, cmp); // 使用自定义的比较函数
    for (int i = 0; i < 4; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

习题

1. 区间排序

点我跳转到题目-洛谷-B4041 [GESP202409 四级] 区间排序

#include <bits/stdc++.h>
using namespace std;

int a[110]; // 用于存储最多100个整数

int main()
{
    int n;
    cin >> n; // 输入数组长度

    // 输入n个整数，存入数组a中，从下标1开始存
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    int t;
    cin >> t; // 输入t，表示需要进行t次区间排序操作

    while (t--) {
        int l, r;
        cin >> l >> r; // 输入左右区间 [l, r]
        sort(a + l, a + r + 1); // 将数组a中从下标l到r（包含r）进行升序排序
    }

    // 输出最终数组内容
    for(int i = 1; i <= n; i++)
        cout << a[i] << " ";

    return 0;
}

需背下来

#include <iostream>
#include <algorithm> // 用到了 sort 函数
using namespace std;

int main() {
    // 📌 本程序的作用是对字符串中的字符按字典序排序（升序）

    string s;
    cin >> s; // 输入一个字符串，例如 "dcba"

    // 使用 sort 函数对字符串中的字符从小到大排序
    sort(s.begin(), s.end());

    // 输出排序后的字符串
    cout << s;

    return 0;
}