如何在排序std::vector时保留指定元素的原有位置？

你遇到的问题很典型——想要排序vector但让某些特殊元素固定在原位置，之前用std::partition加std::sort的思路之所以不对，是因为partition会直接把所有非-1元素移到前面，把-1挤到末尾，完全改变了它们的原始位置。

其实实现这个需求并不难，核心思路是先分离、排序非特殊元素，再重新填充回原vector的对应位置，具体步骤如下：

1. 从原vector中提取所有非-1的元素，把它们单独排序；
2. 遍历原vector，遇到非-1的位置就用排序后的元素依次替换，遇到-1则跳过保持原样。

下面是完整的代码示例：

#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> test{5, 3, 8, 4, -1, 1, 11, 9, 6};
    
    // 收集所有非-1元素并排序
    std::vector<int> sorted_non_special;
    std::copy_if(test.begin(), test.end(), std::back_inserter(sorted_non_special),
                 [](int n) { return n != -1; });
    std::sort(sorted_non_special.begin(), sorted_non_special.end());
    
    // 将排序后的元素填充回原vector的非-1位置
    auto sorted_it = sorted_non_special.begin();
    for (auto& val : test) {
        if (val != -1) {
            val = *sorted_it++;
        }
    }
    
    // 此时test的内容就是 [1, 3, 4, 5, -1, 6, 8, 9, 11]
    return 0;
}

为什么这个方法可行？ #

• 时间复杂度和普通排序差不多：std::sort的时间是O(k log k)，其中k是非特殊元素的数量，加上遍历原vector的O(n)，整体复杂度是O(n + k log k)，和直接排序整个vector的O(n log n)接近；
• 逻辑清晰，容易维护，不会违反std::sort的严格弱序要求（如果尝试自定义比较器来实现位置保留，很容易因为不符合sort的规则导致未定义行为）。

如果你的特殊元素不是固定的-1，只需要修改copy_if和遍历中的判断条件即可，扩展性很好。

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