C++ 标准库排序函数 sort() 详解

输出结果为：1 1 3 4 5。

Vector 示例：

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

int main() {
    vector<int> vec = {3, 1, 4, 1, 5};
    sort(vec.begin(), vec.end());
    cout << "排序后的 vector：";
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

效果与数组一致。

3.2 自定义排序规则

当默认升序无法满足需求时，可以通过自定义比较函数实现灵活排序。

降序排序： 定义一个比较函数，逻辑反转即可。

bool compare(int a, int b) {
    return a > b;
}

// 调用
sort(vec.begin(), vec.end(), compare);

使用标准库函数对象： C++ 标准库提供了 greater 和 less 等函数对象，无需手写比较函数。

#include <functional>

// 降序
sort(vec.begin(), vec.end(), greater<int>());
// 升序（等同于默认）
sort(vec.begin(), vec.end(), less<int>());

复杂规则示例： 比如按个位数大小排序，或对结构体成员排序。

struct Student {
    string name;
    int score;
};

bool compareByScore(const Student& a, const Student& b) {
    return a.score > b.score;
}

vector<Student> students = {{"Alice", 85}, {"Bob", 90}};
sort(students.begin(), students.end(), compareByScore);

四、底层实现原理

sort() 之所以高效，是因为它并非依赖单一算法，而是结合了快速排序、插入排序和堆排序三种经典策略（通常称为 IntroSort）。

• 快速排序：平均时间复杂度为 O(n log n)，适合大数据集。但最坏情况下可能退化到 O(n^2)。
• 堆排序：当递归深度超过阈值（通常是 log n）时切换。其时间复杂度稳定在 O(n log n)，避免栈溢出风险。
• 插入排序：当数据量较小（通常小于 16）时启用。虽然最坏复杂度为 O(n^2)，但常数开销低，对小规模数据更划算。

这种动态调整策略确保了在不同数据规模和初始状态下都能保持良好性能。

五、应用场景

5.1 数据处理与分析

在处理销售数据时，可按数量或金额排序找出热门商品。

struct SaleData {
    string productName;
    int quantity;
};

bool compareByQuantity(const SaleData& a, const SaleData& b) {
    return a.quantity > b.quantity;
}

5.2 算法竞赛

在寻找第 K 大元素等问题中，先排序再取值是简洁高效的解法。

int findKthLargest(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end(), greater<int>());
    return nums[k - 1];
}

5.3 实际项目开发

学生成绩管理系统中，按分数生成报表是典型场景。

六、常见错误与注意事项

6.1 比较函数错误

比较函数必须遵循严格弱序关系。如果违反规则（如 a <= b），可能导致未定义行为甚至崩溃。

错误示例：

bool wrongCompare(int a, int b) {
    return a <= b; // 不满足严格弱序
}

正确示例：

bool correctCompare(int a, int b) {
    return a < b; // 满足严格弱序
}

6.2 数据类型不支持

对于没有重载比较运算符的自定义类，直接使用 sort() 会编译报错。此时需重载 < 运算符或传入自定义比较函数。

七、总结

sort() 函数是 C++ 编程中不可或缺的工具，极大地简化了排序操作。掌握其基本用法、自定义规则及底层原理，能帮助开发者在实际项目中更高效地管理和处理数据。