如何对环绕的数字序列排序

本文关键字：数字 字序 排序 | 更新日期: 2023-09-27 18:17:55

我有一个对象序列，每个对象都有一个从0到ushort的序列号。MaxValue(0 - 65535)。我的序列中最多有大约10,000个项目，所以不应该有任何重复，而且这些项目大多是根据它们加载的方式排序的。我只需要按顺序访问数据，我不需要它们在列表中，如果这有帮助的话。这也是经常发生的事情，所以不能有太高的大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大小，只是增加位置，但这似乎是一个非常低效的方式，我有一些问题，当我收到的数据有一个跳跃的顺序。然而，它在性能上是0 (1).

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

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

如何对环绕的数字序列排序

这是你要找的吗?

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 };

:

我意识到这是一个老问题，我也需要这样做，并希望得到一个答案，所以…

使用带有自定义比较器的SortedSet<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)

相关文章：