1

我有 20 项数组，其中包含十进制数字。它们是未分类的。在每次迭代中，只有几项数组更改（约 1-3 项 20 项数组）。每次迭代后，我需要有相同的数组但“排序”。

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

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

如果这件事我将在 c# 上实现它

4

2 回答 2

3

假设您跟踪 1-3 个更改的元素，则可以使用一步 merge-sort和对数组的额外迭代非常有效地完成

  1. 将所有元素收集到两个数组changed和notChanged1 - 按顺序。
  2. 排序changed（对于 1-3 个元素，它应该相当容易和快速）。
  3. 用于merge(changed,notChanged)获取排序数组

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

(1) 注意notChanged是排序的，因为没有改变的元素是在它们之间排序的！

于 2012-12-05T16:50:00.523 回答
0

只需使用两种结构：这很简单，很健壮，因为您使用现有的运行良好的集合，并且实施成本便宜：

使用两个集合：

一个未排序：例如在 java ArrayList 中，它是一个动态增长的数组
一个已排序：使用任何你想要的。
像往常一样，这两个“集合”都指向内容对象。

在多线程的情况下使事情线程安全：

将两个集合封装在一个类中，您可以在其中同步所有访问，以便对两个集合的读取和写入永远同步。

于 2012-12-05T16:45:28.147 回答