time-complexity - 在插入新项目线性时间O（n）时对数组进行排序？

Question

如何在插入新元素时对数组进行排序？首先它是空的。当我添加新项目时，它将被排序。我可以在插入 O(n) 时空时这样做吗？

标签： time-complexitycomplexity-theoryspace-complexity

Answer 1

遍历数组¹，并在现有元素之间插入元素（a[i] < new <= a[i+1]，这是第一个位置a[i] < new）。然后将数组中的每个现有元素在插入新元素的位置后移动一个索引 ( a[j+1] = a[j] for j > i)。当数组被移动时，使用一个临时变量来保持浮点值。这也可以稍微改变以向后迭代，然后不需要显式临时变量，因为移位是在插入之前完成的。

因此，每个单独元素的插入是 O(n)，对于 n 个插入，总体而言是 O(n*n) 。¹即使需要创建一个新数组，例如在具有固定数组大小的语言中，空间也是 O(2n)，与 O(n) 相同。无论移动现有元素或分配新数组并复制所有元素，Big-O 时间复杂度都保持不变。

空间分配成本可以通过在阵列结构中预先分配松弛来“摊销”。这只是实施质量问题。使用二分搜索查找插入点不会改变“最坏情况”的 Big-O 边界：考虑何时插入总是发生在第一个索引处。