符合C++ std::stable_sort复杂度要求的算法及所需额外内存是多少？
2026-9-29
std::stable_sort 相关问题解答
对应O(n log n)复杂度的排序算法类型
- 满足要求的是归并排序类算法，该类算法天然具备排序稳定性，即不会改变相等元素的原有相对顺序，常规非原地实现的时间复杂度恰好为O(n log n)，符合
std::stable_sort的接口约束。 - 当无法拿到足够额外内存时，
std::stable_sort会退化为原地稳定排序实现，时间复杂度升高到题目中提到的O(n (log n)²)。
官方规定的额外内存容量要求
要实现O(n log n)时间复杂度，std::stable_sort需要的额外内存大小为与待排序序列长度相等的存储空间，即空间复杂度为O(n)，其中n为待排序的元素总个数。
主流标准库的通用实现逻辑为：调用
std::stable_sort时先尝试申请大小等于待排序序列总容量的临时缓冲区，申请成功则走归并排序逻辑，申请失败则切换到低空间需求、高时间复杂度的原地稳定排序分支。
内容的提问来源于stack exchange，提问作者Yingfa
相关产品推荐
相关产品推荐
