C++实现稳定std::partial_sort的替代方案与最佳实践

C98到C17的标准库确实没有提供std::stable_partial_sort接口。要实现「仅前N个排序区间内等值元素保留原相对顺序、区间外元素无稳定性要求」的效果，不需要对整个容器做全量稳定排序，以下两种方案都可以满足需求，性能远优于全量std::stable_sort。

方案1：绑定原始索引做partial_sort（推荐，严格保序） #

核心逻辑很简单：排序时给每个元素附加它在原数组中的位置下标，比较时先按业务规则判断大小，业务值相等的情况下比较原始下标，下标更小的元素排前面，天然就能保证等值元素的相对顺序和原数组完全一致。
这个方案的时间复杂度和普通std::partial_sort一致，为O(M log N)（M是容器总元素数，N是需要排序的前区间长度），当N远小于M时性能优势非常明显。
针对你给出的示例，可直接运行的实现代码如下：

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

struct Collection
{
    size_t m_id;
    std::string m_token;
};

struct IdxCompare {
    bool operator()(const std::pair<size_t, const Collection*>& lhs,
                    const std::pair<size_t, const Collection*>& rhs) const {
        if (lhs.second->m_id != rhs.second->m_id) {
            return lhs.second->m_id < rhs.second->m_id;
        }
        // 业务值相等时，原始位置更靠前的元素排在前面，保证稳定性
        return lhs.first < rhs.first;
    }
};

std::ostream& operator<<(std::ostream& os, const Collection& rhs)
{
    os << rhs.m_id << "-" << rhs.m_token;
    return os;
}

int main()
{
    std::vector<Collection> myEmployVec {{4, "ABC"},{1, "AA"}, {5, "A"}, {4, "OTHER"}, {5, "OOO"}, {1, "AA"}, {1, "AB"}};
    const size_t top_n = 3;
    
    for (size_t i = 0; i < myEmployVec.size(); ++i) {
        std::cout << myEmployVec[i] << " ";
    }
    std::cout << "\n";

    // 构造带原始下标的辅助数组，不修改原元素结构
    std::vector<std::pair<size_t, const Collection*>> idx_arr;
    idx_arr.reserve(myEmployVec.size());
    for (size_t i = 0; i < myEmployVec.size(); ++i) {
        idx_arr.push_back(std::make_pair(i, &myEmployVec[i]));
    }

    // 对辅助数组做部分排序
    std::partial_sort(idx_arr.begin(), idx_arr.begin() + top_n, idx_arr.end(), IdxCompare());

    // 仅把排好序的前N个元素写回原容器前N位，剩余位置不处理
    for (size_t i = 0; i < top_n; ++i) {
        if (idx_arr[i].first != i) {
            myEmployVec[i] = *(idx_arr[i].second);
        }
    }

    for (size_t i = 0; i < myEmployVec.size(); ++i) {
        std::cout << myEmployVec[i] << " ";
    }
    std::cout << "\n";

    return 0;
}

运行后前3个元素固定输出1-AA 1-AA 1-AB，完全符合预期。

方案2：nth_element + 局部稳定排序（无额外索引开销） #

如果不想引入额外的索引辅助数组，可以分两步实现：

1. 调用std::nth_element把所有符合前N位排序要求的元素（即按业务规则值最小的N个元素）移动到容器前N区间，这一步不保证元素顺序，时间复杂度O(M)
2. 仅对前N个元素的区间调用std::stable_sort，保证区间内等值元素的相对顺序稳定，这一步时间复杂度O(N log N)
   总时间复杂度为O(M + N log N)，N远小于M时性能同样远优于全量稳定排序。
   核心代码片段如下：

const size_t top_n = 3;
// 第一步：把最小的3个元素移动到前3位
std::nth_element(myEmployVec.begin(), myEmployVec.begin() + top_n, myEmployVec.end(),
    [](const Collection& lhs, const Collection& rhs) {
        return lhs.m_id < rhs.m_id;
    });
// 第二步：仅对前3位做稳定排序
std::stable_sort(myEmployVec.begin(), myEmployVec.begin() + top_n,
    [](const Collection& lhs, const Collection& rhs) {
        return lhs.m_id < rhs.m_id;
    });

注意：std::nth_element会打乱元素原有位置，因此这个方案无法严格保证等值元素和原数组的全局相对顺序，仅能保证前N区间内的等值元素在排序后相对稳定。如果需要严格匹配原数组的元素先后顺序，优先选择方案1。

方案选择参考 #

• 需要严格保留等值元素在原数组中的全局相对顺序，选方案1
• 不需要严格全局保序、希望减少额外内存开销，选方案2
• 非必要不要对整个容器调用std::stable_sort，当容器总元素量很大、需要的top N区间很小时，全量排序会带来数倍甚至数十倍的不必要性能损耗。

你当前用std::partial_sort出现稳定性问题的运行结果参考：

内容的提问来源于stack exchange，提问作者Anton K