保持更改数组排序顺序的算法

Question

我有一个包含十进制数的 20 项数组。它们是未分类的。在每次迭代中，只有数组的几项发生变化(20 项数组中的 ~1-3 项)。每次迭代后，我需要有相同的数组但“已排序”。

我不应该修改原始数组，相反我需要维护表示相同数组但已排序的“并行”结构。允许使用指针。

我确实关心延迟，所以我需要直接的解决方案!显然，我可以使用双链表来“记住”排序顺序，但我将花费 K*O(n)(具有相当大的 K)来更新这个列表，这听起来有点昂贵。我正在寻找比双链表更好的东西。

如果这很重要，我会在 C# 上实现它

Answer 1

假设您跟踪 1-3 个更改的元素，使用合并排序的单个步骤和对数组的额外迭代可以非常有效地完成

1. 将所有元素按顺序收集到两个数组 changed 和 notChanged¹ 中。
2. 排序 已更改(对于 1-3 个元素，它应该相当简单快捷)。
3. 使用merge(changed,notChanged)得到一个排序的数组

复杂度为 O(n)，我相信具有相当好的常量，因为 merge() 是在单个迭代中完成的，收集阶段也是如此。此外，由于我们仍在使用数组，因此这种方法的缓存效率应该很高。

---

(1) 注意 notChanged 是排序的，因为未更改的元素在它们之间是排序的!