部分排序数组,以便排序最后n个元素？

Question

有没有办法对数据数组执行局部排序,以便对最后n个元素进行排序？好吧我的意思是使用标准库,而不是实现我自己的排序功能(这就是我现在正在做的事情).示例输出(使用较少的比较器):

2 1 4 || 5 6 8 10

后面||的元素都比元素之前的元素大||,但只保证对元素右侧的元素||(更靠近数组末尾的索引)进行排序.

这基本上是std :: partial_sort函数的反转,它对左(第一)元素进行排序.

Answer 1

std::partial_sort与反向迭代器一起使用.

例如:

int x[20];
std::iota(std::begin(x), std::end(x), 0);
std::random_shuffle(std::begin(x), std::end(x));

std::reverse_iterator<int*> b(std::end(x)),
                            e(std::begin(x));
std::partial_sort(b, b+10, e, std::greater<int>());
for (auto i : x)
    std::cout << i << ' ';

Answer 2

partial_sort使用反向迭代器和std :: greater进行比较的另一种可能性是用于std::nth_element对集合进行分区,然后使用std :: sort来对您关心的分区进行排序:

std::vector<int> data{5, 2, 1, 6, 4, 8, 10}; //  your data, shuffled

std::nth_element(data.begin(), data.begin()+2, data.end());

std::sort(data.begin()+2, data.end();