部分排序:第n个元素保持顺序

Question

任务是对具有重复项的向量进行部分排序，其中中值(第n个元素)位于该向量排序后的位置。所有较小的元素应该在左边，所有较大的元素应该在右边。所有值与中位数相同的元素都必须按原始顺序排列——但只有这些元素，而不是其他元素。

你怎么解决这个问题?

我的初始解决方案:

1. 使用std::nth_element()查找中位数元素
2. 遍历vector，只对与中值相对于索引值相同的元素排序。我该如何有效地做到这一点?

Answer 1

使用partition或stable_partition(以保持原始顺序)

class Predicate{
    int median_value;
    public:
    Predicate(int med) : median_value(med) {}
    bool operator()(int x){
    return x < median_value;
    }
};
int main(){
vector<int> v{ 10, 20, 30, 10, 30};
int median = 20;
cout << "median  = " << median << endl;
stable_partition(v.begin(), v.end(), Predicate(median));
for ( auto i : v)
    cout << i << " ";
}