C++中含-1的整数数组升序排序（忽略负数）的实现方法

有两种简洁的实现方式，都基于C++标准库算法，无需手动写复杂的遍历逻辑：

方法一：自定义比较器配合std::sort #

直接使用std::sort，通过自定义lambda表达式作为比较规则，让所有-1自动排在正数之后，同时正数部分按升序排列：

#include <algorithm>

int main() {
    int x[] = {8,4,1,5,7,-1,-1,-1,-1,-1};
    std::sort(std::begin(x), std::end(x), [](int a, int b) {
        if (a == -1 && b != -1) return false;
        if (b == -1 && a != -1) return true;
        return a < b;
    });
    // 排序后x即为{1,4,5,7,8,-1,-1,-1,-1,-1}
    return 0;
}

方法二：分区后局部排序 #

先通过std::partition把所有非-1的元素移到数组前端，再单独对这部分元素排序，这种方式只需要排序正数部分，效率更高：

#include <algorithm>

int main() {
    int x[] = {8,4,1,5,7,-1,-1,-1,-1,-1};
    // 将非-1元素移到数组前面，返回第一个-1的位置
    auto first_neg = std::partition(std::begin(x), std::end(x), [](int num) {
        return num != -1;
    });
    // 对前面的正数部分升序排序
    std::sort(std::begin(x), first_neg);
    return 0;
}

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