11、常用排序算法：sort、random_shuffle、merge、reverse

排序和重排，是日常开发里最基础也最频繁的操作之一。STL 给我们提供了四个非常趁手的工具：sort、random_shuffle、merge 和 reverse。说实话，我刚入行那会儿，经常自己手写冒泡排序，后来才发现 STL 的排序又快又稳，何必重复造轮子呢？

今天我们就把这四个算法掰开揉碎了讲清楚。你想想看，掌握了它们，大部分数据整理的需求你都能轻松搞定。

11.1 sort：最常用的排序利器

sort 用的是快速排序的改进版——内省排序。它会在数据量小的时候切到插入排序，递归深度过大时切到堆排序。说白了，就是又快又稳，基本不会出现最坏情况。

我个人习惯，只要需要对容器排序，第一个想到的就是 sort。它默认升序，也支持自定义比较器。

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

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

    // 默认升序
    std::sort(vec.begin(), vec.end());

    for (int v : vec) std::cout << v << " ";
    // 输出: 1 2 3 4 5

    // 降序：用 greater 或 lambda
    std::sort(vec.begin(), vec.end(), std::greater<int>());
    // 或者: [](int a, int b) { return a > b; }

    for (int v : vec) std::cout << v << " ";
    // 输出: 5 4 3 2 1

    return 0;
}
我的小技巧：如果你只需要部分排序，比如只关心前几名，用 std::partial_sort 效率更高。我在做排行榜功能时就用过，数据量大的时候能省不少时间。

11.2 random_shuffle：打乱顺序的妙用

random_shuffle 的作用很简单——把容器里的元素随机打乱。不过要注意，C++17 之后它被标记为弃用了，官方推荐用 std::shuffle 替代。但我还是想提一下它，因为很多老项目里还在用。

我记得有一次做抽奖系统，需要从名单里随机抽取几个人。用 random_shuffle 打乱整个 vector，然后取前几个，简单粗暴，效果很好。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8};

    // 老方式（C++17 前）
    // std::random_shuffle(vec.begin(), vec.end());

    // 推荐方式：使用 shuffle + 随机数引擎
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(vec.begin(), vec.end(), g);

    for (int v : vec) std::cout << v << " ";
    // 每次运行结果不同，比如: 3 7 1 5 8 2 6 4

    return 0;
}
我曾经踩过的坑：用 random_shuffle 时，如果不指定随机数种子，每次运行结果是一样的。因为默认用的是 rand()，而 rand() 的种子是固定的。后来我改用 shuffle + mt19937，才真正做到了「真随机」。

11.3 merge：合并两个有序序列

merge 的作用是把两个已经排好序的序列合并成一个新的有序序列。它不会修改原来的两个序列，而是把结果放到第三个容器里。

我项目中用过一次：两个系统分别导出了按时间排序的日志文件，我需要把它们合并成一个完整的时间线。用 merge 一行代码搞定，比自己写双指针循环省心多了。

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

int main() {
    std::vector<int> v1 = {1, 3, 5, 7};
    std::vector<int> v2 = {2, 4, 6, 8};
    std::vector<int> result(v1.size() + v2.size());

    std::merge(v1.begin(), v1.end(),
               v2.begin(), v2.end(),
               result.begin());

    for (int v : result) std::cout << v << " ";
    // 输出: 1 2 3 4 5 6 7 8

    return 0;
}
注意：两个输入序列必须都是有序的（默认升序）。如果顺序不一致，合并结果会乱掉。另外，目标容器要提前分配好足够的空间，否则会出问题。

11.4 reverse：反转序列

reverse 是最简单的一个——把序列里的元素顺序颠倒过来。它直接修改原容器，不返回新容器。

嗯，这里要注意：reverse 对双向迭代器或随机访问迭代器都有效。所以 list 也能用，但 forward_list 不行。

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

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

    std::reverse(vec.begin(), vec.end());

    for (int v : vec) std::cout << v << " ";
    // 输出: 5 4 3 2 1

    return 0;
}
一个小用法：如果你想反转字符串中的单词顺序，可以先用 reverse 反转整个字符串，再逐个反转每个单词。我在做文本处理时用过这个技巧，效率很高。

11.5 知识体系总览

下面这张图帮你理清这四个算法的核心关系和使用场景：

常用排序算法知识体系 sort random_shuffle merge reverse 内省排序 默认升序，支持自定义比较器 随机访问迭代器 随机打乱元素顺序 C++17 后弃用，改用 shuffle 需要随机数引擎 合并两个有序序列 不修改原序列 目标容器需预分配空间 反转序列顺序 直接修改原容器 双向迭代器即可 使用建议 排序用 sort，打乱用 shuffle，合并用 merge，反转用 reverse 注意迭代器类型要求，避免在 list 上使用 sort（应使用 list::sort）

11.6 综合对比

为了方便你快速查阅，我把这四个算法的核心特性整理成了表格：

算法 头文件 迭代器要求 是否修改原容器 时间复杂度 备注
sort <algorithm> 随机访问迭代器 是 O(n log n) 内省排序，最坏情况 O(n log n)
random_shuffle <algorithm> 随机访问迭代器 是 O(n) C++17 弃用，建议用 shuffle
merge <algorithm> 输入：输入迭代器
输出：输出迭代器		 否 O(n) 两个输入序列必须有序
reverse <algorithm> 双向迭代器 是 O(n) forward_list 不可用
核心要点：
  • 排序首选 sort，不要自己手写排序算法
  • 打乱用 shuffle（C++11 起），别用 random_shuffle
  • 合并前确保两个序列已经排好序
  • 反转操作简单高效，但注意迭代器类型限制

好了，这四个排序相关的算法就讲到这里。实际开发中，它们经常组合使用。比如先 sort 再 reverse 实现降序，或者先 shuffle 再 sort 实现随机排序。多试试，你会发现它们真的很顺手。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →