C++ 的 std::sort 函数

下面将详细介绍如何使用 C++ 的 std::sort 函数实现数组或容器元素从小到大和从大到小的排序，同时还会给出不同数据类型（如基本数据类型、自定义数据类型）的排序示例。

对基本数据类型（如 `int`）进行排序

1. 从小到大排序

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    // 定义一个整数向量
    std::vector<int> numbers = {5, 2, 8, 1, 9};

    // 使用 std::sort 进行从小到大排序
    std::sort(numbers.begin(), numbers.end());

    // 输出排序后的结果
    std::cout << "从小到大排序结果: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

代码解释：

std::sort(numbers.begin(), numbers.end()); 这行代码调用了 std::sort 函数，它会对 numbers 向量中从 begin() 到 end() 范围内的元素进行排序。由于没有提供自定义比较函数，默认是按照从小到大的顺序排序。

2. 从大到小排序

#include <iostream>
#include <algorithm>
#include <vector>

// 自定义比较函数，用于从大到小排序
bool compareDesc(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9};

    // 使用 std::sort 并传入自定义比较函数进行从大到小排序
    std::sort(numbers.begin(), numbers.end(), compareDesc);

    std::cout << "从大到小排序结果: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

代码解释：

compareDesc 函数是自定义的比较函数，它接受两个 int 类型的参数 a 和 b，当 a > b 时返回 true(真则不交换），表示 a 应该排在 b 前面，从而实现从大到小的排序。
std::sort(numbers.begin(), numbers.end(), compareDesc); 调用 std::sort 函数时传入了自定义比较函数 compareDesc，使得排序按照从大到小的规则进行。

对自定义数据类型进行排序

1. 自定义类型的定义

假设我们有一个 Student 类，包含学生的姓名和成绩，我们要根据成绩对学生进行排序。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

// 定义 Student 类
class Student {
public:
    std::string name;
    int score;

    Student(const std::string& n, int s) : name(n), score(s) {}
};

2. 从小到大排序

// 自定义比较函数，按成绩从小到大排序
bool compareScoreAsc(const Student& s1, const Student& s2) {
    return s1.score < s2.score;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 70},
        {"Charlie", 90}
    };

    // 按成绩从小到大排序
    std::sort(students.begin(), students.end(), compareScoreAsc);

    std::cout << "按成绩从小到大排序结果:" << std::endl;
    for (const auto& student : students) {
        std::cout << student.name << ": " << student.score << std::endl;
    }

    return 0;
}

代码解释：

compareScoreAsc 函数用于比较两个 Student 对象的成绩，当 s1.score < s2.score 时返回 true，表示 s1 应该排在 s2 前面，实现按成绩从小到大排序。
std::sort(students.begin(), students.end(), compareScoreAsc); 调用 std::sort 函数并传入自定义比较函数 compareScoreAsc 对 students 向量进行排序。

3. 从大到小排序

// 自定义比较函数，按成绩从大到小排序
bool compareScoreDesc(const Student& s1, const Student& s2) {
    return s1.score > s2.score;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 70},
        {"Charlie", 90}
    };

    // 按成绩从大到小排序
    std::sort(students.begin(), students.end(), compareScoreDesc);

    std::cout << "按成绩从大到小排序结果:" << std::endl;
    for (const auto& student : students) {
        std::cout << student.name << ": " << student.score << std::endl;
    }

    return 0;
}

代码解释：

compareScoreDesc 函数用于比较两个 Student 对象的成绩，当 s1.score > s2.score 时返回 true，表示 s1 应该排在 s2 前面，实现按成绩从大到小排序。
std::sort(students.begin(), students.end(), compareScoreDesc); 调用 std::sort 函数并传入自定义比较函数 compareScoreDesc 对 students 向量进行排序。

通过上述示例，你可以清晰地看到如何使用 std::sort 函数对不同数据类型进行从小到大和从大到小的排序。

补充，`stable_sort`

std::stable_sort 是 C++ 标准库 <algorithm> 头文件中提供的一个排序函数，它的主要功能是对指定范围内的元素进行排序，并且保证相等元素的相对顺序在排序后保持不变，也就是所谓的“稳定排序”。以下将从基本用法、复杂度、与 std::sort 的比较、示例代码等方面详细介绍 std::stable_sort 函数。

基本语法

std::stable_sort 有两种重载形式：

// 第一种形式：使用元素类型的 operator< 进行比较
template< class RandomIt >
void stable_sort( RandomIt first, RandomIt last );

// 第二种形式：使用自定义的比较函数 comp 进行比较
template< class RandomIt, class Compare >
void stable_sort( RandomIt first, RandomIt last, Compare comp );

参数说明： first 和 last：这是随机访问迭代器，分别指向要排序的元素范围的起始位置和结束位置（不包含 last 所指向的元素）。comp：这是一个可选的比较函数，它接受两个参数，返回一个布尔值。如果返回 true，表示第一个参数应该排在第二个参数之前。

复杂度分析

时间复杂度：通常为 $O(N log^2 N)$ ，其中 $N$ 是要排序的元素数量。不过在某些情况下，时间复杂度可以接近 $O(N log N)$ 。
空间复杂度：通常为 $O(N)$ ，这意味着在排序过程中，可能需要额外的与元素数量成正比的内存空间。

与 `std::sort` 的比较

稳定性：std::stable_sort 是稳定排序，即相等元素的相对顺序在排序后保持不变；而 std::sort 是不稳定排序，相等元素的相对顺序可能会改变。
性能：std::sort 平均情况下的时间复杂度为 $O(N log N)$ ，通常比 std::stable_sort 更快，因为它不保证稳定性，实现上可能更高效。如果不需要保证相等元素的相对顺序，使用 std::sort 通常是更好的选择。

示例代码

对基本数据类型排序

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {5, 3, 8, 3, 1, 2};

    // 使用 std::stable_sort 进行排序
    std::stable_sort(numbers.begin(), numbers.end());

    // 输出排序后的结果
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个例子中，std::stable_sort 对 numbers 向量中的元素进行升序排序，由于使用的是默认的比较方式（即 operator<），所以元素会按照从小到大的顺序排列，并且相等的元素（如两个 3）的相对顺序会保持不变。

对自定义类型排序

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

// 自定义类型
struct Person {
    std::string name;
    int age;
};

// 自定义比较函数，按年龄升序排序
bool compareByAge(const Person& p1, const Person& p2) {
    return p1.age < p2.age;
}

int main() {
    std::vector<Person> people = {
        {"Alice", 25},
        {"Bob", 20},
        {"Charlie", 25}
    };

    // 使用 std::stable_sort 并传入自定义比较函数进行排序
    std::stable_sort(people.begin(), people.end(), compareByAge);

    // 输出排序后的结果
    for (const auto& person : people) {
        std::cout << person.name << " (" << person.age << ")" << std::endl;
    }

    return 0;
}

在这个例子中，定义了一个 Person 结构体，包含姓名和年龄两个成员。通过自定义比较函数 compareByAge，使用 std::stable_sort 对 people 向量按照年龄进行升序排序。由于使用的是稳定排序，年龄相同的 Alice 和 Charlie 的相对顺序会保持不变。

注意事项

比较函数 comp 必须满足严格弱序关系，即对于任意的 a、b、c，需要满足： comp(a, a) 必须为 false。如果 comp(a, b) 为 true，则 comp(b, a) 必须为 false。如果 comp(a, b) 为 true 且 comp(b, c) 为 true，则 comp(a, c) 必须为 true。
传递给 std::stable_sort 的迭代器必须是随机访问迭代器，例如 std::vector、std::array 的迭代器，而像 std::list 的迭代器是双向迭代器，不能直接用于 std::stable_sort，但 std::list 有自己的 sort 成员函数可以实现排序。