部分排序数组，使最后n个元素有序？

Question

有没有一种方法可以对数据数组执行部分排序，使最后的 n 个元素被排序？好的意思是使用标准库，而不是实现自己的排序函数（这就是我现在正在做的事情）。 示例输出（使用 less 比较器）：

2 1 4 || 5 6 8 10

“||” 后面的元素都大于 “||” 前面的元素，但只有位于 “||” 右侧（靠近数组末尾的索引）的元素才能保证已排序。

这基本上是 std::partial_sort 函数的反转，它对左侧（第一个）元素进行排序。

- helloworld922

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 << ' ';

- Benjamin Lindley

---

我认为它需要一个不同的比较器，因此将 std::greater 添加到混合物中。 - Sjoerd

Answer 2

除了使用反向迭代器和std::greater进行比较的partial_sort之外，另一种可能性是使用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();

- Jerry Coffin

---

出于好奇，是否有任何原因或情况，我应该考虑使用这种解决方案而不是使用反向迭代器？ - helloworld922

@helloworld922：我能看到两个优点。第一个是（至少对我来说）它似乎更易读。第二个是在大多数情况下，我们可以期望它更有效率。当N为总大小，M为要排序的大小时，partial_sort的复杂度约为O(N log M)，而这个方法的复杂度约为O(N + M log M)。 - Jerry Coffin

嗯，有趣。如果这样可能更快，他们为什么不内部实现部分排序呢？ - helloworld922

@helloworld922：当然他们可以这样做——我只是引用标准要求他们这样做的内容。 - Jerry Coffin

@BenjaminLindley：你可能是对的：“大多数情况”可能有点夸张了。 - Jerry Coffin

Answer 3

在C++20中使用范围和视图非常简单。

数组示例：

//DATA
int arrayOfInts[8] = { 82,80,81,86,83,85,84,88 };

//SORT LAST 5 ELEMENTS. SO DROP FIRST 3.
std::ranges::sort(std::views::drop(arrayOfInts, 3));

//PRINT ARRAY -- 82  80  81 || 83  84  85  86  88
for (auto i : arrayOfInts)
    std::cout << i << "  ";

向量示例：

//DATA
std::vector<int> vecOfInts = { 82,80,81,86,83,85,84,88 };

//SORT LAST 5 ELEMENTS. SO DROP FIRST 3.
std::ranges::sort(std::views::drop(vecOfInts, 3));

//PRINT VECTOR -- 82  80  81  || 83  84  85  86  88
for (auto i : vecOfInts)
    std::cout << i << "  ";

- Pavan Chandaka

---

问题陈述为：“在结果中，||之后的元素都大于||之前的元素”。现在看看你的示例输出。86在哪里？ - Will Ness

好的，我会更改示例。无论如何，这不是问题，因为从概念上讲，我们正在从视图中删除元素。 - Pavan Chandaka

不，你不应该让它看起来像是正常工作，而实际上它并没有正常工作，就像你原来的例子所展示的那样。 - Will Ness