如何在插入新元素时对数组进行排序？首先是 空的。当我添加新项目时，它将被排序。我可以吗 插入O（n）时空？
环绕数组1，然后在现有元素之间插入元素（a[i] < new <= a[i+1]，这是第一个位置a[i] < new）。然后，在插入新元素的位置之后，将数组中的每个现有元素移动一个索引（a[j+1] = a[j] for j > i）。使用临时变量在数组移动时保持浮动值。也可以稍作更改以向后迭代，然后不需要显式的temp变量，因为在插入之前已完成了移位。
每个单个元素的插入因此为O（n），对于n个插入而言，其<< O（n * n）总和。 1即使需要创建一个新数组，例如在具有固定数组大小的语言中，空格也为O（2n），与O（n）相同。无论移动现有元素或分配新数组并复制所有元素，Big-O的时间复杂度都保持不变。
可以通过预先分配数组结构中的松弛空间来“摊销”空间分配成本。这仅是实现方面的关注。使用二进制搜索找到插入点不会改变“最坏情况”的Big-O界限：请考虑何时插入总是发生在第一个索引处。