排序与二分算法

定义与作用

排序算法将元素按指定顺序排列，二分算法在有序序列中高效查找。STL 提供了丰富的排序和二分查找功能，覆盖不同场景的性能需求。

#include <algorithm>

std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());              // 全排序 O(n log n)
std::binary_search(v.begin(), v.end(), 5);  // 二分查找 O(log n)

核心原理

排序算法族谱

lower_bound / upper_bound / equal_range

完整示例

示例一：飞翔科技绩效排名

场景说明：大翔用排序算法为飞翔科技年度绩效排名。

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

struct Employee {
    std::string name;
    std::string dept;
    int score;
    double revenue;  // 创收（万元）
};

void printRanking(const std::string& title,
                  const std::vector<Employee>& team) {
    std::cout << title << ":\n";
    int rank = 1;
    for (const auto& e : team)
        std::cout << "  #" << rank++ << " " << e.name << " ("
                  << e.dept << ") 绩效:" << e.score
                  << " 创收:¥" << std::fixed << std::setprecision(1)
                  << e.revenue << "万\n";
}

int main() {
    std::vector<Employee> team = {
        {"大翔", "技术", 98, 1888.8},
        {"白歌", "技术", 95, 1666.6},
        {"小崔", "技术", 92, 1234.5},
        {"黄俪", "技术", 90, 888.8},
        {"李眉", "技术", 88, 666.6},
        {"孔蓝", "产品", 87, 2320.0},
        {"赵鸣", "运营", 85, 1888.8},
        {"高英", "运营", 82, 1666.6},
        {"孙鹤", "产品", 80, 520.0},
        {"杨英", "运营", 78, 1234.5},
        {"朱璐", "运营", 75, 888.8},
        {"林鸥", "设计", 72, 666.6},
    };

    // 1. 全排序：按绩效分数降序
    std::sort(team.begin(), team.end(),
        [](const Employee& a, const Employee& b) {
            return a.score > b.score;  // 降序
        });
    printRanking("=== 绩效排名（全排序）===", team);

    // 2. 稳定排序：按部门排序，同部门内保持原有顺序
    std::stable_sort(team.begin(), team.end(),
        [](const Employee& a, const Employee& b) {
            return a.dept < b.dept;
        });
    std::cout << "\n=== 部门分组（稳定排序）===\n";
    for (const auto& e : team)
        std::cout << "  " << e.dept << " | " << e.name << "\n";

    // 3. 部分排序：Top 3 创收明星
    std::partial_sort(team.begin(), team.begin() + 3, team.end(),
        [](const Employee& a, const Employee& b) {
            return a.revenue > b.revenue;
        });
    std::cout << "\n=== Top 3 创收明星 ===\n";
    for (int i = 0; i < 3; ++i)
        std::cout << "  #" << i + 1 << " " << team[i].name
                  << ": ¥" << team[i].revenue << "万\n";

    // 4. nth_element：中位数创收
    auto mid = team.begin() + team.size() / 2;
    std::nth_element(team.begin(), mid, team.end(),
        [](const Employee& a, const Employee& b) {
            return a.revenue < b.revenue;
        });
    std::cout << "\n创收中位数: ¥" << mid->revenue << "万 ("
              << mid->name << ")\n";

    // 5. 二分查找：查找创收 ¥888.8 万的员工
    std::sort(team.begin(), team.end(),
        [](const Employee& a, const Employee& b) {
            return a.revenue < b.revenue;
        });

    double target = 888.8;
    auto low = std::lower_bound(team.begin(), team.end(), target,
        [](const Employee& e, double val) { return e.revenue < val; });
    auto up  = std::upper_bound(team.begin(), team.end(), target,
        [](double val, const Employee& e) { return val < e.revenue; });

    std::cout << "\n=== 创收 ¥888.8 万的员工 ===\n";
    for (auto it = low; it != up; ++it)
        std::cout << "  " << it->name << ": ¥" << it->revenue << "万\n";

    std::cout << "(共 " << std::distance(low, up) << " 人)\n";
}

预期输出：

=== 绩效排名（全排序）===
  #1 大翔 (技术) 绩效:98 创收:¥1888.8万
  #2 白歌 (技术) 绩效:95 创收:¥1666.6万
  ...

=== 部门分组（稳定排序）===
  产品 | 孔蓝
  产品 | 孙鹤
  技术 | 大翔
  技术 | 白歌
  ...

创收中位数: ¥XXXX万 (XXX)

=== 创收 ¥888.8 万的员工 ===
  黄俪: ¥888.8万
  朱璐: ¥888.8万
(共 2 人)

逐段分析：

  • sort 底层通常是 introsort（快速排序 + 堆排序混合），O(n log n)
  • stable_sort 保持相等元素的相对顺序，通常用归并排序
  • partial_sort 只保证前 k 个有序，其余无序，适合 Top-K 场景
  • nth_element 只保证第 n 位置正确，前半部分 ≤ 第 n ≤ 后半部分
  • lower_bound / upper_bound 的组合等价于 equal_range

示例二：is_sorted 与 merge 日志合并

场景说明：李眉用合并算法整合多台服务器的有序日志。

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

int main() {
    std::vector<int> serverA{101, 203, 305, 407};
    std::vector<int> serverB{102, 204, 306, 408};
    std::vector<int> serverC{103, 205};
    std::vector<int> merged;

    // 检查输入是否有序
    std::cout << "A 有序: " << std::is_sorted(serverA.begin(), serverA.end()) << "\n";
    std::cout << "B 有序: " << std::is_sorted(serverB.begin(), serverB.end()) << "\n";

    // 合并前预留空间
    merged.reserve(serverA.size() + serverB.size() + serverC.size());

    // 第一步：合并 A 和 B
    std::merge(serverA.begin(), serverA.end(),
               serverB.begin(), serverB.end(),
               std::back_inserter(merged));

    // 第二步：将 C 合并到结果中（inplace_merge 需要临时缓冲区）
    auto mid = merged.size();
    merged.insert(merged.end(), serverC.begin(), serverC.end());
    std::inplace_merge(merged.begin(), merged.begin() + mid, merged.end());

    std::cout << "\n合并后日志ID: ";
    for (int id : merged) std::cout << id << " ";
    std::cout << "\n共 " << merged.size() << " 条\n";
    std::cout << "合并后有序: " << std::is_sorted(merged.begin(), merged.end()) << "\n";
}

预期输出：

A 有序: true
B 有序: true

合并后日志ID: 101 102 103 203 204 205 305 306 407 408 
共 10 条
合并后有序: true

逐段分析：

  • is_sorted（C++11）检查区间是否有序
  • merge 合并两个有序区间，结果保持有序
  • inplace_merge 将两个相邻的有序子区间原地合并
  • reserve 预分配避免多次扩容

易错场景与面试考点

易错场景

1. 二分查找前未排序

std::vector<int> v{3, 1, 4, 1, 5};
// auto it = std::lower_bound(v.begin(), v.end(), 3);  // ❌ 未排序，结果不可预测
std::sort(v.begin(), v.end());  // ✅ 必须先排序
auto it = std::lower_bound(v.begin(), v.end(), 3);

2. 比较器不一致

std::sort(v.begin(), v.end(), std::greater<>());
// std::binary_search(v.begin(), v.end(), x);  // ❌ 比较器不匹配！
std::binary_search(v.begin(), v.end(), x, std::greater<>());  // ✅

3. lower_bound 的比较器参数顺序

// 自定义结构需要传入比较器，注意参数顺序
auto it = std::lower_bound(vec.begin(), vec.end(), target,
    [](const Employee& e, double val) { return e.revenue < val; });
// lower_bound: comp(*it, value) → true 时向右移动

面试考点

考点要点
sort 时间复杂度O(n log n)，introsort 混合策略
stable_sort 场景需要保持相等元素原始相对顺序时
partial_sort 场景Top-K 问题，比全排序高效
nth_elementO(n) 中位数/分位数选择
lower_bound vs upper_bound第一个 ≥ vs 第一个 >
equal_range返回 pair<lower_bound, upper_bound>
sorted 前置条件所有二分算法要求输入有序