循环创建双精度并将它们插入到排序数组中，在C中

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

{ 0.124, 4.567, 12.3 }

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

 { 0.124, 4.567, 7.56, 12.3 }

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

尝试

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

题

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

编辑：

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

但如果情况并非如此，也许还有另一种选择？

由于您要做的只是在每次迭代中拉出最小元素，所以请使用min-heap 。您可以实现它们以进行O（1）插入，O（1） find-min和O（1） 减少键操作（但请注意，删除最小元素总是需要O（log n）时间）。对于你正在做的事情，堆将大大加快。

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

最快的方法是先插入，然后立即对所有内容进行排序。如果无法做到这一点，请考虑使用自平衡有序树结构（例如RB-Tree）替换arrays。