3

我有一个对象序列，每个对象都有一个从 0 到 ushort.MaxValue (0-65535) 的序列号。我的序列中最多有大约 10 000 个项目，因此不应该有任何重复项，并且这些项目大多是根据加载方式进行排序的。我只需要按顺序访问数据，如果有帮助的话，我不需要它们在列表中。这也是经常做的事情，所以它不能有太高的 Big-O。

对该列表进行排序的最佳方法是什么？

示例序列可以是（在此示例中，假设序列号是单字节并在 255 处换行）：

240 241 242 243 244 250 251 245 246 248 247 249 252 253 0 1 2 254 255 3 4 5 6

正确的顺序将是

240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 0 1 2 3 4 5 6

我有几种不同的方法，包括制作一个 ushort.MaxValue 大小的数组，并且只是增加位置，但这似乎是一种非常低效的方法，当我收到的数据有顺序跳跃时我会遇到一些问题。但是，它的性能是 O(1)..

另一种方法是正常排序项目，然后找到拆分 (6-240)，并将第一个项目移动到末尾。但我不确定这是否是个好主意。

我的第三个想法是循环序列，直到找到错误的序列号，向前看直到找到正确的序列号，然后将其移动到正确的位置。但是，如果早期有错误的序列号，这可能会非常慢。

4

2 回答 2

1

这是你想要的？

var groups = ints.GroupBy(x => x < 255 / 2)
     .OrderByDescending(list => list.ElementAt(0))
     .Select(x => x.OrderBy(u => u))
     .SelectMany(i => i).ToList();

示例 在： 

int[] ints = new int[] { 88, 89, 90, 91, 92, 0, 1, 2, 3, 92, 93, 94, 95, 96, 97, 4, 5, 6, 7, 8, 99, 100, 9, 10, 11, 12, 13 };

出去：

88 89 90 91 92 92 93 94 95 96 97 99 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13

于 2013-06-12T09:42:59.800 回答
1

我意识到这是一个旧问题字节，我也需要这样做，并且希望得到答案，所以......

将 aSortedSet<FileData>与自定义比较器一起使用；

其中FileData包含有关您正在使用的文件的信息，例如

struct FileData
{
    public ushort SequenceNumber;
    ...
}

internal class Sequencer : IComparer<FileData>
{
    public int Compare(FileData x, FileData y)
    {
        ushort comparer = (ushort)(x.SequenceNumber - y.SequenceNumber);
        if (comparer == 0) return 0;
        if (comparer < ushort.MaxValue / 2) return 1;
        return -1;
    }
}

当您从磁盘读取文件信息时，将它们添加到您的SortedSet

当你把它们读出来时，SortedSet它们现在的顺序是正确的

请注意，SortedSet内部使用红黑，这应该可以让您在性能和内存之间取得很好的平衡

插入是 O(log n)
遍历是 O(n)

于 2014-01-23T13:02:13.073 回答