排序后如何保持向量中重复项的顺序?

Question

我有一个结构体向量，每个结构体都有一个数字ID，我用它来对向量项进行排序。我希望对id进行排序，但也要按照排序后它们在原始向量中的顺序出现。让我解释一下……

假设你有一个这样的向量(忽略结构体):

vector<int> items = {
1,
2,
5, // First 5
8,
9,
6,
5, // Second 5
4,
7,
3,
5, // Third 5
10
};

排序后，我希望向量看起来像这样:

vector<int> items = {
1,
2,
3,
4,
5, // First 5
5, // Second 5
5, // Third 5
6,
7,
8,
9,
10
};

记住，这些项实际上是结构体。多个属性可以具有相同的ID，但其他属性的值不同。现在，我不认为这些结构在排序之后有一个可预测的顺序。有没有办法保证这样的产出?我能不能给结构体添加另一个属性来指示它们的原始顺序然后在排序算法中使用它?

Answer 1

你正在寻找的是所谓的"稳定排序"，c++标准库提供它为std::stable_sort;当项目比较相等时，它们以与原始数据集中相同的顺序出现。普通std::sort没有这样的保证(因此可以使用稍微更有效的算法来排序，但不能为相等的元素保持顺序)，但是std::stable_sort需要使用做保证的算法。