C++ 中 std::sort 函数的深度解析

在 C++ 编程中，std::sort 是标准模板库（STL）中的一个强大工具，能够高效地对元素序列进行排序。它定义在 <algorithm> 头文件中，具有多种函数原型以适应不同的使用场景和需求。

std::sort 的基本原型为 template<class RandomIt> void sort(RandomIt first, RandomIt last)，其中 first 和 last 是随机访问迭代器，定义了需要排序的元素范围 [first, last)。它还具有接受比较函数的版本，允许自定义排序规则。

std::sort 的默认排序行为是升序排列，使用 < 运算符比较元素大小。当需要更灵活的排序方式时，可以提供自定义的比较函数。比较函数是一个函数或函数对象，它接受两个参数并返回一个布尔值。如果第一个参数应该排在第二个参数之前，函数返回 true，否则返回 false。比较函数必须满足“严格弱序”关系，即对于任意两个元素 $a$ 和 $b$，若 comp(a, b) 为 true，则 comp(b, a) 必须为 `false$。

比较函数可以是普通函数、Lambda 表达式或函数对象。普通函数定义明确，适合重复使用的场景；Lambda 表达式简洁方便，适合在调用 std::sort 时直接定义临时比较逻辑；函数对象通过重载 () 运算符，提供了一种灵活的比较函数实现方式。

std::sort 的算法实现通常采用 Introsort，这是一种混合排序算法，结合了快速排序、堆排序和插入排序的优点。其平均时间复杂度和最坏情况时间复杂度均为 $O(N\log N)$，其中 $N$ 为 last - first。

在实际应用中，std::sort 提供了高效的排序能力。例如，对整数数组进行升序排序：

#include <iostream>
#include <algorithm>

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

若要实现降序排序，可以使用 Lambda 表达式自定义比较函数：

std::sort(arr, arr + n, [](int a, int b) { return a > b; });

对于更复杂的数据结构，如结构体数组，可以定义比较函数来根据特定成员变量进行排序：

#include <iostream>
#include <algorithm>

struct Person {
    std::string name;
    int age;
};

bool compareByAge(const Person &a, const Person &b) {
    return a.age < b.age; // 按年龄升序排序
}

int main() {
    Person arr[] = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::sort(arr, arr + n, compareByAge);
    for (int i = 0; i < n; ++i)
        std::cout << arr[i].name << " " << arr[i].age << "\n";
    return 0;
}

综上所述，std::sort 是 C++ 中一个功能强大且高效的排序工具，通过灵活运用其比较函数，可以实现各种复杂的排序需求，为程序开发提供了极大的便利。