将数字插入到已排序的数组中！

Question

我想写一段代码在适当的位置插入一个数字到排序的数组中（即插入后数组仍然应该保持排序）

我的数据结构不允许重复。

我打算做这样的事情：

1. 查找，我应该使用二进制搜索
2. 此元素创造空间来把这个元素，从该指数将所有的元素正确的索引下。
3. 把这个元素放在那里。

还有其他更好的方法吗？

Answer 1

如果你真的有一个数组而不是一个更好的数据结构，那是最优的。如果您在实施方面很灵活，请参阅AA Trees - 它们相当快速且易于实施。显然，比阵列占用更多的空间，如果元素的数量不足以注意到与指针魔术相比的blit缓慢，这是不值得的。

Answer 2

如果您插入了大量元素（记录n用于定位/删除和插入操作），基于树的堆实现会更有效。

Answer 3

数据是否必须始终完全排序？ 如果不是，只需要快速访问最小或最高的元素，Binary Heap会给出恒定的访问时间和logn添加和删除时间。 更重要的是它可以满足你的条件，即内存应该是连续的，因为你可以在一个数组上面实现一个BinaryHeap（I.e; array [2n + 1] left child，array [2n + 2] right child）。