面试题：C++ 自定义比较函数与 std::sort 稳定性

Question

假设你有一个包含多个 `struct` 对象的 `std::vector`，结构如下：`struct Data { int id; int value; };`。现在你需要使用 `std::sort` 对这个 `vector` 进行排序，先按 `id` 升序排列，如果 `id` 相同则按 `value` 降序排列。请编写一个自定义比较函数，并解释在此情况下 `std::sort` 的排序稳定性如何影响排序结果。如果要求保持稳定性，你会考虑什么替代方案？

Answer 1

自定义比较函数

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

struct Data {
    int id;
    int value;
};

// 自定义比较函数
bool compare(const Data& a, const Data& b) {
    if (a.id != b.id) {
        return a.id < b.id;
    } else {
        return a.value > b.value;
    }
}

std::sort 排序稳定性对结果的影响

1. 排序稳定性定义：排序稳定性是指相等元素在排序前后的相对顺序保持不变。
2. 对本题影响：std::sort 是不稳定排序算法。在本题中，如果两个 Data 对象的 id 相同，不稳定排序可能会改变它们原本在 vector 中的相对顺序，尽管按 value 降序排列，但相同 id 的元素相对顺序可能与初始顺序不同。

保持稳定性的替代方案

1. 使用 std::stable_sort：std::stable_sort 是稳定排序算法。使用它替代 std::sort 并传入相同的自定义比较函数 compare，就可以保证在 id 相同的情况下，value 降序排列时元素的相对顺序与初始顺序一致。

std::vector<Data> dataList;
// 填充 dataList
std::stable_sort(dataList.begin(), dataList.end(), compare);

2. 归并排序：可以自行实现归并排序，归并排序是稳定排序算法。在实现过程中，按照 compare 函数的逻辑进行比较和合并操作，从而实现稳定排序。