c++ - 部分排序 : nth elements having preseved order

Question

任务是对具有重复项 s.t. 的 vector 进行部分排序。如果对 vector 进行排序，则中位数(第 n 个元素)位于应有的位置。所有较小的元素都应该在左边，所有较大的元素在右边。值与中位数相同的所有元素都必须按原始顺序 - 但只有这些元素而不是其余元素。

你会如何解决这个问题？

我最初的解决方案:

1. 使用 std::nth_element() 寻找中值元素
2. 遍历 vector ，只对与中值相同的元素的索引进行排序。我将如何有效地做到这一点？

Answer 1

使用分区或稳定分区(以保留原始顺序)。

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 << " ";
}