將數字插入到已排序的數組中！

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）。