performance - 阵列管理的时间复杂度（算法）

Question

我正在开发一个程序，该程序接收一堆（y）整数，然后需要按顺序返回 x 个最高整数。这段代码需要尽可能快，但目前我认为我没有最好的算法。

到目前为止，我的方法/算法是创建一个已经输入的整数的排序列表（从高到低），然后处理每个输入的项目。对于前 x 个项目，我维护一个排序的整数数组，当每个新项目进来时，我都会使用二进制排序确定它应该放在哪里。（我也在考虑只接收前 x 个项目，然后快速排序它们，但我不知道这是否更快）在前 x 个项目被排序后，我首先查看其余项目是否有资格进入已经排序的最高整数列表（通过查看新整数是否大于列表末尾的整数），如果是，则通过二进制搜索将其添加到排序列表中并删除末尾的整数列表。

我想知道是否有人对如何使这更快，或者可能是比这更快的全新方法有任何建议。谢谢。

Answer 1

这是部分排序：

最快的实现是快速排序，您只在包含底部/顶部k元素的范围上递归。

在 C++ 中，您可以使用std::partial_sort

Answer 2

这称为top-N 排序。这是一个非常简单有效的方案。不需要花哨的数据结构。

1. 保留最高 x 元素的列表（开始为空）
2. 将您的输入拆分为x * 10项目块
3. 对于每个块，将到目前为止 x 最高项目的记忆列表添加到它并对其进行排序（例如快速排序）
4. 保留 x 最高的项目。它们形成了新的记忆列表
5. 转到 3 直到处理完所有块
6. 记住的列表现在是您的最终结果

这是O(N)项目的数量，只需要正常的快速排序作为原语。

Answer 3

如果使用堆排序树数据结构来存储整数，则插入新整数不超过 lg N 次比较，删除最大值不超过 2 lg N 次比较。因此，插入y项目只需要y lg N比较，删除顶部x项目只需要2x lg N比较。Wikipedia条目引用了一系列实现。

Answer 4

您似乎不需要按排序顺序排列的前 N ​​个项目。因此，您可以在线性时间内解决这个问题。

使用线性时间选择查找第 N 个最大的数组元素。返回它和所有比它大的数组元素。