C++ sort 排序

在 C++ 中，我们可以使用 <algorithm> 头文件中的 std::sort() 函数对容器元素进行快速排序。它是日常开发中使用频率非常高的通用排序工具，不仅支持升序或降序排列，还能灵活实现局部子区间排序与多条件排序。

std::sort() 的基本用法

std::sort() 用于对指定区间内的元素进行原地排序。在不传入额外比较规则的情况下，它默认使用小于号 < 按照从小到大的升序排列。

语法：

std::sort(first, last);

说明：

std::sort() 接收一对迭代器作为区间参数：

first（必选）：排序范围的起始位置，比如 nums.begin()，包含在排序范围内。
last（必选）：排序范围的结束边界，比如 nums.end()。注意 last 本身不包含在排序范围内，实际排序的是 [first, last) 左闭右开区间。

示例 1：默认升序排序

运行代码

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

int main() {
    std::vector<int> nums = {30, 10, 50, 20, 40};

    // 对整个容器按从小到大排序
    std::sort(nums.begin(), nums.end());

    for (int n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

10 20 30 40 50

分析：

std::sort(nums.begin(), nums.end()); 表示将 nums 从头到尾的所有元素按从小到大重新排列。如果要对 std::string 按字符顺序排列，写法也是完全一样的。

如果换作普通数组 int arr[5]，就像前面学习数组排序时那样，我们直接传入 std::begin(arr) 和 std::end(arr)（或起止地址 arr 与 arr + 5）即可。

注意 std::sort() 会直接修改原容器中的元素顺序，而不是生成一个新的容器。如果我们希望保留原来的顺序，可以先将原容器复制一份，再对副本进行排序。

由于 std::sort() 处理的是我们传入的 [first, last) 区间，对于 vector、array 这类支持随机访问的容器，我们可以通过 begin() + n 调整起止边界，只对容器中间的一部分元素进行排序。下面我们来看一个例子。

示例 2：局部子区间排序

运行代码

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

int main() {
    std::vector<int> nums = {90, 70, 50, 30, 10};

    // 只对下标 1 到下标 3 的元素排序
    std::sort(nums.begin() + 1, nums.begin() + 4);

    for (int n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

90 30 50 70 10

分析：

nums.begin() + 1 指向下标 1 处的 70，nums.begin() + 4 指向下标 4 处的 10。按照左闭右开的规则，真正参与排序的只有下标 1~3 处的 70、50、30，排好后首尾的 90 和 10 保持不变。

自定义排序规则

在实际开发中，除了默认的从小到大排序，我们还经常需要按照从大到小、按绝对值大小，或者按对象中的某个成员来排序。这时，我们可以给 std::sort() 传入第 3 个参数来指定比较规则。

语法：

std::sort(first, last, compare);

说明：

第 3 个参数 compare 可以是普通比较函数，也可以是上一节刚学的 Lambda 表达式。它接收两个待比较的元素 a 和 b，并返回 bool 值：返回 true 表示 a 排在 b 前面；返回 false 表示 a 不排在 b 前面。

1. 使用 Lambda 自定义比较规则

如果我们希望将数字按照从大到小的降序排列，只需要让比较规则在 a > b 时返回 true 即可。

示例 3：使用 Lambda 按降序排列

运行代码

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

int main() {
    std::vector<int> nums = {24, 8, 36, 15};

    // 传入 Lambda 按从大到小排列
    std::sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;
    });

    for (int n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

36 24 15 8

分析：

在这个例子中，我们给 std::sort() 传入了 Lambda 表达式作为第 3 个参数。排序过程中，函数会不断取出两个元素传给 a 和 b，只要 a > b 为真就把 a 排到 b 前面，最终得到 36 24 15 8。

初学的小伙伴如果容易把 < 和 > 写反，只需要记住一个小窍门：直接把 a 看作排在前面的数、b 看作排在后面的数。希望前小后大（升序）就写 a < b，希望前大后小（降序）就写 a > b，不等号方向和最终顺序完全一致。

另外，大家第一次看到代码末尾连在一起的 }); 时也不用觉得奇怪：} 用来结束 Lambda 的函数体，中间的 ) 用来结束 std::sort() 的参数括号，最后的 ; 则是整条语句的结束分号。

对于降序排序来说，下面 3 种方式是等价的。

// 方式 1（推荐）
std::sort(nums.begin(), nums.end(), [](int a, int b) {
    return a > b;
});

// 方式 2
bool descending(int a, int b) {
    return a > b;
}
std::sort(nums.begin(), nums.end(), descending);

// 方式 3
std::sort(nums.begin(), nums.end(), std::greater<int>());

其中，方式 1 直接使用 Lambda 表达式，方式 2 单独定义了普通比较函数，方式 3 则使用了 <functional> 头文件中的 std::greater<int>()。在实际开发中我们更推荐使用方式 1，不仅不用额外记类名，还能随时改成更复杂的条件。

在编写自定义比较规则时，有一条硬性规定需要小伙伴们特别注意：比较符号必须使用严格的 < 或 >，千万不要写成 <= 或 >=。

// 正确方式
return a > b;

// 错误方式
return a >= b;

为什么不能带等号呢？因为比较规则回答的是 “a 是否必须严格排在 b 前面”。假如容器里有两个 20，写成 a >= b 时正着比和反着比都会返回 true，相当于要求两个 20 互相排在对方前面，这会导致内部逻辑矛盾甚至引发程序崩溃。

2. 按结构体成员与多条件排序

在实际项目中，vector 里存放的通常不是简单的整数，而是表示学生或订单信息的结构体与类对象。由于结构体包含多个成员，std::sort() 不知道应该拿哪个成员来比大小，此时我们就必须传入自定义比较规则。

示例 4：结构体多条件排序

运行代码

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

struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {"Tony", 90},
        {"Jack", 85},
        {"Lucy", 90},
        {"Tom", 95}
    };

    // 按成绩降序，同分按姓名升序
    std::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;
        });

    for (const Student& s : students) {
        std::cout << s.name << "：" << s.score << '\n';
    }
    return 0;
}

运行结果如下。

Tom：95
Lucy：90
Tony：90
Jack：85

分析：

在这个例子中，Lambda 的参数列表使用了常量引用 const Student&，既能省去复制整个结构体对象的开销，又能防止在比较过程中误改数据。

当两个学生的成绩不同时，a.score != b.score 成立，程序直接按成绩从高到低排。遇到 "Tony" 和 "Lucy" 同为 90 分时，则继续执行 return a.name < b.name;，按姓名字母顺序把 "Lucy" 排在前面。

提示如果两个元素的排序字段相等且没有指定第 2 个排序条件，std::sort() 并不保证它们维持原来的先后顺序。如果我们希望相等元素严格保留原有的相对顺序，可以将函数名替换为用法相同的 std::stable_sort()。

不同容器的排序方法

为了保证较高的排序效率，std::sort() 内部需要频繁跨越多个位置去比较和交换元素，因此它要求传入的迭代器必须支持 it + n 随机访问操作。

也就是说，并不是所有带 begin() 和 end() 的容器都能直接交给 std::sort() 处理。常见容器的排序支持情况如下：

vector、array、deque：它们的迭代器都支持随机访问，我们可以直接使用 std::sort() 进行排序。
list：底层是双向链表，迭代器只支持 ++ 和 -- 一步步移动，不支持 it + n 跨步跳转，直接传给 std::sort() 会编译报错。
set、map 等关联容器：set 和 map 在插入元素时就会自动按规则排好序，本身不需要排序。而 unordered_set 和 unordered_map 属于无序哈希容器，同样不能使用 std::sort()。

如果数据存放在 list 双向链表中，我们又需要对它进行排序，应该怎么办呢？其实很简单，std::list 容器自己专门提供了一个 sort() 成员函数，直接调用 nums.sort() 即可。请看下面例子。

示例 5：使用 list.sort() 排序

运行代码

#include <iostream>
#include <list>

int main() {
    std::list<int> nums = {30, 10, 40, 20};

    nums.sort();    // 调用 list 自身的排序方法

    for (int n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

10 20 30 40

分析：

nums.sort(); 是 std::list 针对双向链表实现的专属排序方法，默认按升序排列。如果要按降序排列，我们同样可以在括号里传入 Lambda，比如 nums.sort([](int a, int b) { return a > b; });。

平时写代码时，小伙伴们只需要记住一条简单规则：如果是 vector、array、deque，使用 std::sort()；如果是 list，则直接调用它自带的 sort() 成员函数。