C++ sort排序

C++ 排序相关知识主要围绕 标准库排序函数、排序算法原理、自定义排序规则 和 实战应用 展开，以下是系统梳理：

一、核心排序函数：`std::sort`

1. 函数原型（头文件 `<algorithm>`）

// 默认升序排序
template <class RandomIt>
void sort(RandomIt first, RandomIt last);

// 自定义比较函数排序
template <class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

参数说明：
- first/last：随机访问迭代器（如数组指针、vector::iterator），指定排序范围 [first, last)（左闭右开）。
- comp：二元比较函数/函数对象，定义排序规则（可选，默认 std::less<T> 升序）。

2. 基本用法示例

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

int main() {
    vector<int> nums = {3, 1, 4, 1, 5, 9};
    
    // 1. 默认升序排序
    sort(nums.begin(), nums.end());
    for (int x : nums) cout << x << " "; // 输出：1 1 3 4 5 9
    cout << endl;
    
    // 2. 自定义降序排序（函数指针）
    sort(nums.begin(), nums.end(), greater<int>());
    for (int x : nums) cout << x << " "; // 输出：9 5 4 3 1 1
    cout << endl;
    
    // 3. 自定义结构体排序（lambda 表达式）
    struct Person {
        string name;
        int age;
    };
    vector<Person> people = {{"Alice", 25}, {"Bob", 20}, {"Charlie", 30}};
    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age; // 按年龄升序
    });
    for (auto& p : people) cout << p.name << "(" << p.age << ") "; // 输出：Bob(20) Alice(25) Charlie(30)
    return 0;
}

二、排序算法原理：IntroSort（内省排序）

std::sort 底层采用 IntroSort，结合了三种算法的优势：

快速排序（QuickSort）：处理大部分情况，平均时间复杂度。
堆排序（HeapSort）：当快速排序递归深度超过阈值（通常为）时切换，避免最坏情况。
插入排序（InsertionSort）：当排序区间长度小于阈值（通常为 16）时切换，小数据量下效率更高。

关键特性：

不稳定排序：相等元素的相对顺序可能改变（如需稳定排序，用 std::stable_sort）。
随机访问迭代器要求：仅支持数组、vector、deque 等容器（list 需用 list::sort）。

三、其他常用排序函数

函数	功能说明	稳定性
`std::stable_sort`	稳定排序（相等元素相对顺序不变）	稳定
`std::partial_sort`	对前 k 个元素排序（前 k 个为最小/最大值，后续元素无序）	不稳定
`std::nth_element`	使第 n 个元素处于正确位置（左侧元素≤它，右侧元素≥它），用于找中位数等	不稳定
`std::sort_heap`	将堆（`std::make_heap` 构建）排序为有序序列	不稳定
`list::sort`	链表专属排序（避免移动元素，效率更高）	稳定

示例：`std::stable_sort` 与 `std::partial_sort`

// 稳定排序：相等元素保持原顺序
vector<pair<int, int>> vec = {{2, 1}, {1, 2}, {2, 3}};
stable_sort(vec.begin(), vec.end(), [](auto& a, auto& b) {
    return a.first < b.first; // 按 first 升序，second 保持原顺序
});
// 输出：(1,2) (2,1) (2,3)（second 1 在 3 前，与输入一致）

//  partial_sort：前 3 个元素为最小的 3 个（升序）
vector<int> nums = {5, 3, 1, 4, 2};
partial_sort(nums.begin(), nums.begin() + 3, nums.end());
// 输出：1 2 3 5 4（前 3 个为最小，后续无序）

四、自定义排序规则

1. 函数指针

bool cmp(int a, int b) {
    return a > b; // 降序
}
sort(nums.begin(), nums.end(), cmp);

2. Lambda 表达式（推荐，简洁高效）

sort(nums.begin(), nums.end(), [](int a, int b) {
    return a % 2 < b % 2; // 偶数在前，奇数在后
});

3. 函数对象（结构体重载 `()` 运算符）

struct Cmp {
    bool operator()(int a, int b) const {
        return abs(a) < abs(b); // 按绝对值升序
    }
};
sort(nums.begin(), nums.end(), Cmp());

4. `std::bind` 绑定参数（复杂场景）

#include <functional>
using namespace std::placeholders;

bool cmp(int a, int b, bool ascending) {
    return ascending ? a < b : a > b;
}

// 绑定 ascending=false，实现降序
sort(nums.begin(), nums.end(), bind(cmp, _1, _2, false));

五、实战应用场景

1. 基础数据排序（数组/vector）

int arr[] = {3, 1, 4};
sort(arr, arr + 3); // 数组排序（指针作为迭代器）

2. 结构体/类排序

struct Student {
    string name;
    int score;
};

vector<Student> students = {{"Tom", 85}, {"Jerry", 92}, {"Alice", 85}};
// 按分数降序，分数相同按姓名升序
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    if (a.score != b.score) return a.score > b.score;
    return a.name < b.name;
});

3. 字符串排序（字典序/长度）

vector<string> strs = {"apple", "banana", "cherry", "date"};
// 按长度升序，长度相同按字典序
sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
});

4. 大数据量排序优化

若数据量极大（如级别），优先用 std::sort（IntroSort 效率最优）。
若需稳定排序，用 std::stable_sort（底层为归并排序，空间复杂度）。
若仅需前 k 个元素，用 std::partial_sort 或 std::nth_element（效率高于完整排序）。

六、注意事项

容器选择：
- 需随机访问的容器（数组、vector、deque）可用 std::sort。
- 链表（list）需用 list::sort（避免迭代器失效）。
排序规则有效性：
- 比较函数必须满足 严格弱序（避免自反性、传递性错误，如 a <= b 会导致排序异常）。
- 正确示例：a < b（升序）、a > b（降序）、abs(a) < abs(b)（绝对值升序）。
性能优化：
- 小数据量（<16）无需手动切换算法，std::sort 已优化。
- 避免在比较函数中做复杂计算（如重复调用函数），可提前预处理数据。
稳定性需求：
- 若需保留相等元素的相对顺序（如排序后保持原输入顺序），必须用 std::stable_sort。

总结

C++ 排序的核心是 std::sort，底层为高效的 IntroSort，支持自定义排序规则，适配多种场景。实际开发中，应根据数据量、稳定性需求、容器类型选择合适的排序函数，优先使用标准库实现（效率高、bug 少），避免重复造轮子。