1

假设我有一组排序的双打。

{ 0.124, 4.567, 12.3 }

代码的另一部分创建了一个正的非零双精度，并且需要在保持排序的同时插入到该集合中。例如，如果创建的 double 是7.56，则最终结果是，

{ 0.124, 4.567, 7.56, 12.3 }

在我的代码中，这个“创建双精度并在排序集中插入”过程会重复很多次。可能 500k 到 100 万次。我不知道总共会创建多少双打，但我知道上限。

试图

我天真的第一种方法是创建一个长度 = 上限的数组并用零填充它，然后将初始的双精度集添加到其中（“添加”=用双精度值替换 0 值条目）。每当创建一个 double 时，我将它添加到数组中并进行插入排序，我读到这对于排序有序数组很有用。

问题

我感觉运行 500k 到 100 万个插入插槽将是一个严重的性能问题。（或者我错了吗？）在 C 中是否有更有效的数据结构和/或算法来执行此操作？

编辑：

我想保持集合排序的原因是因为在每次“创建双精度并在排序集合中插入”过程之后，我需要能够查找该集合中的最小元素（并可能通过将其替换为 0 来删除它）。我认为最好的方法是保持集合排序。

但如果不是这样，也许还有其他选择？

4

2 回答 2

6

由于您要做的就是在每次迭代中提取最小元素，因此请改用最小堆。您可以将它们实现为具有 O(1)插入、O(1)查找最小值和 O(1)减少键操作（但请注意，删除最小元素总是需要 O(log n) 时间）。对于您正在做的事情，堆将大大加快。

于 2012-09-26T17:23:26.940 回答
3

您可以使用二进制搜索来查找插入点，然后在其中插入值，而不是运行插入排序。但这很慢，因为您可能需要多次移动大量数据（想想如果随机数据的排序与您需要的相反，会发生什么情况，时间会是O(N^2)）。

最快的方法是先插入，然后一次对所有内容进行排序。如果这不可能，请考虑用自平衡有序树结构（例如RB-Tree ）替换您的数组。

于 2012-09-26T17:11:25.153 回答