c# - 如何对环绕的数字序列进行排序

Question

我有一个对象序列，每个对象都有一个从 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)，并将第一个项目移到最后。但我不确定这是否是个好主意。

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

Answer 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