java - 在排序数组中间添加值的最快方法 - Java

Question

我有一个排序数组，假设 D={1,2,3,4,5,6}，我想在中间添加数字 5。我可以通过在中间添加值 5 并将其他值向右移动一步来做到这一点。

问题是我有一个长度为 1000 的数组，我需要执行该操作 10.000 次，所以我需要一种更快的方法。

我有什么选择？我可以使用 LinkedList 来获得更好的性能吗？

Answer 1

这取决于您如何添加这些数字。如果仅按升序或降序排列 - 那么是的，LinkedList 可以解决问题，但前提是您在插入之间保留节点引用。

如果您以任意顺序添加数字，您可能需要解构数组，添加新条目并再次重建它。通过这种方式，您可以使用擅长添加和删除条目的数据结构，同时保持“排序”。然而，您必须放松您的假设之​​一。

选项 1
假设您在添加数字时不需要恒定时间随机访问:

使用二叉排序树。

缺点 - 在添加时，您无法通过元素的位置读取或引用元素，至少不容易。最好的情况 - 您使用的树可以跟踪左节点有多少个元素，并且可以在 log(n) 时间内获取第 i 个元素。如果您只是迭代元素，您仍然可以获得相当好的性能。

总运行时间从 n^2 降至 n * log(n)。随机访问是log(n)。

选项 2
假设您在添加元素时不需要对元素进行排序。

使用普通数组，但在其末尾添加元素，完成后对其进行排序。

总运行时间:n * log(n)。随机访问的时间复杂度为O(1)，但元素未排序。

选项 3
(这有点作弊，但是......)
如果您的值数量有限，那么采用 BucketSort 的思想将帮助您实现出色的性能。本质上 - 您可以用排序的映射替换数组。

运行时为O(n)，随机访问为O(1)，但只适用于极少数情况。

TL;DR
获取任意值、快速添加和恒定时间位置访问，同时保持排序性是很困难的。我不知道任何这样的结构。您必须放松一些假设才能有优化空间。