排序与相关算法：从底层原理到实战应用

排序，是编程里最基础也最常用的操作之一。C++ STL 给我们提供了好几种排序算法，各有各的脾气。今天我们就来聊聊这些算法的底层实现、适用场景，最后用排行榜系统把它们串起来。

sort 的底层：IntroSort

很多人以为 std::sort 就是快排。其实不是。它用的是 IntroSort（内省排序）。

为什么不用纯快排？因为快排有弱点——最坏情况会退化到 O(n²)。我早期做项目时就踩过这个坑。数据量一大，排序突然慢得像蜗牛，查了半天才发现是输入数据恰好让快排选到了最差的 pivot。

IntroSort 的思路很简单：

• 先用快排，效率高
• 如果递归深度超过某个阈值（通常是 2×log₂n），就切换到堆排
• 当子数组长度小于 16 时，改用插入排序

说白了，就是「快排为主，堆排兜底，小数据用插入」。三种算法取长补短，保证最坏情况也是 O(n log n)。

stable_sort：稳定排序的代价

std::stable_sort 保证相等元素的相对顺序不变。它底层用的是归并排序。

代价是什么？额外内存。归并排序需要 O(n) 的辅助空间。如果内存不够，它会退化成原地归并，但性能会下降。

我个人习惯是：只有明确需要稳定排序时才用 stable_sort。比如先按姓名排序，再按分数排序，希望同分的人保持姓名顺序——这时候就必须用稳定排序。

partial_sort：只排前几名

有时候我们只需要前几名，比如排行榜的前 10 名。这时候用 partial_sort 就对了。

它的原理是：先用 std::make_heap 建堆，然后不断弹出最大元素放到末尾。说白了就是「堆排的局部版本」。

我曾经在一个游戏服务器里优化排行榜查询。全量排序要 200ms，改成 partial_sort 只排前 100 名，耗时降到 15ms。效果立竿见影。

std::vector<int> scores = {85, 92, 78, 95, 88, 91, 76, 99, 82, 87};
// 只排前 3 名
std::partial_sort(scores.begin(), scores.begin() + 3, scores.end(), std::greater<>());
// scores 前 3 个元素是 99, 95, 92，后面元素顺序未定义

nth_element：找到第 k 大的元素

nth_element 是个被低估的算法。它只做一件事：把第 n 大的元素放到正确位置，左边都比它小，右边都比它大。但两边内部不排序。

底层用的是 IntroSelect，本质是快排的 partition 过程，但只递归处理包含目标的那一半。平均 O(n)，最坏 O(n log n)。

你想想看，如果只需要中位数、或者第 90 百分位数，用 nth_element 比全排序快得多。

partition 与 stable_partition

std::partition 把满足条件的元素移到前面，不满足的移到后面。它用的是双向迭代器，内部实现是类似快排的交换过程。

std::stable_partition 则保证相对顺序不变，代价是需要额外内存。

我常用 partition 来做「快速筛选」。比如从一堆成绩中分出及格和不及格：

std::vector<int> scores = {45, 78, 92, 33, 88, 61, 55, 97};
auto it = std::partition(scores.begin(), scores.end(),
                         [](int s) { return s >= 60; });
// scores 前 5 个是及格分数，后 3 个是不及格

实战：排行榜系统

好了，理论说完了。我们来做一个排行榜系统。需求很简单：

• 有 100 万玩家，每人有分数
• 需要显示前 100 名
• 支持按分数排序，同分按时间排序
• 每 5 分钟更新一次

你会怎么做？全排序？100 万数据全排一次要几百毫秒，5 分钟更新一次倒是可以接受。但如果同时有 100 个请求呢？

我的方案是这样的：

1. 用 partial_sort 取前 100 名，复杂度 O(n log k)，k=100
2. 用 stable_sort 对前 100 名按分数降序、时间升序排序
3. 缓存结果，5 分钟内直接返回

这样每次更新只需要 O(n log 100) ≈ O(n) 的时间，比全排序快了一个数量级。

struct Player {
    int id;
    int score;
    int64_t timestamp;  // 毫秒级时间戳
};

std::vector<Player> players;  // 假设已填充 100 万数据

// 1. 取前 100 名（按分数）
std::partial_sort(players.begin(), players.begin() + 100, players.end(),
    [](const Player& a, const Player& b) {
        return a.score > b.score;
    });

// 2. 对前 100 名稳定排序（同分按时间）
std::stable_sort(players.begin(), players.begin() + 100,
    [](const Player& a, const Player& b) {
        if (a.score != b.score) return a.score > b.score;
        return a.timestamp < b.timestamp;  // 先到先得
    });

// 3. 输出前 10 名
for (int i = 0; i < 10; ++i) {
    std::cout << "Rank " << i+1 << ": ID=" << players[i].id
              << " Score=" << players[i].score << "\n";
}

知识体系总览

下面这张图总结了本章涉及的排序算法及其关系：

这张图把本章涉及的算法分成了三类：完全排序、部分排序、分区算法。每个算法都有它的底层实现和适用场景。你写代码时，先想清楚「我需要什么」，再选合适的工具。

好了，排序这块的内容就聊到这里。记住：没有银弹，只有合适的工具。选对了，性能翻倍；选错了，坑你没商量。

---