c++ - 部分排序：具有保留顺序的第 n 个元素

Question

任务是对具有重复 st 的向量进行部分排序，如果向量已排序，则中值（第 n 个元素）位于它的位置。所有较小的元素都应该在左边，所有较大的元素都应该在右边。与中值相同的所有元素都必须按原始顺序排列 - 但只有这些元素不是其余元素。

你会如何解决这个问题？

我最初的解决方案：

1. 使用 std::nth_element() 查找中值元素
2. 遍历向量并仅对与其索引具有相同值的元素进行排序。我将如何有效地做到这一点？

Answer 1

Use partition or stable_partition (to preserve original order).

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