问题描述
我有对象的序列，其分别具有从0到ushort.MaxValue（0-65535）的序列号。我在最高约10000项在我的顺序，所以不应该有任何重复，以及项目由于它们加载的方式大多是排序。我只需要访问数据的顺序，我不需要他们在列表中，如果可以提供帮助。这也是东西是相当频繁做，所以它不能有太高的大澳。
I have a sequence of objects, that each have a sequence number that goes from 0 to ushort.MaxValue (0-65535). I have at max about 10 000 items in my sequence, so there should not be any duplicates, and the items are mostly sorted due to the way they are loaded. I only need to access the data sequentially, I don't need them in a list, if that can help. It is also something that is done quite frequently, so it cannot have a too high Big-O.
这是什么列表进行排序的最好方法是什么？
What is the best way to sort this list?
这是示例序列可以是（的的在这个例子中，的假设该序列号是单字节并包装在255）：
An example sequence could be (in this example, assume the sequence number is a single byte and wraps at 255):
240 241 242 243 244 250 251 245 246 248 247 249 252 253 0 1 2 254 255 3 4 5 6
然后，正确的顺序是
The correct order would then be
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）性能。
I have a few different approaches, including making a array of ushort.MaxValue size, and just incrementing the position, but that seems like a very inefficient way, and I have some problems when the data I receive have a jump in sequence. However, it's O(1) in performance..
另一种方法是正常订购的项目，然后找到分离（6-240），然后将第一个项目结束。但我不知道这是一个好主意。
Another approach is to order the items normally, then find the split (6-240), and move the first items to the end. But I'm not sure if that is a good idea.
我的第三个想法是循环的顺序，直到我找到一个错误的序列号，向前看，直到我找到正确的，并将其移动到正确的位置。然而，这可以潜在地是相当缓慢的，如果有一个错误的序列号在初期
My third idea is to loop the sequence, until I find a wrong sequence number, look ahead until I find the correct one, and move it to its correct position. However, this can potentially be quite slow if there is a wrong sequence number early on.
推荐答案
我意识到这是一个老问题字节我还需要做到这一点，本来希望的答案，所以......
I realise this is an old question byte I also needed to do this and would have liked an answer so...
使用一个的SortedSet＆LT;的FileData＆GT; 与自定义比较;
Use a SortedSet<FileData> with a custom comparer;
其中，的FileData 包含您正在使用的文件的信息例如，
where FileData contains information about the files you are working withe.g.
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 他们现在以正确的顺序
When you read them out of the SortedSet they are now in the correct order
请注意，的SortedSet 采用了红黑内部应该给你的性能和内存之间的一个很好的平衡
Note that the SortedSet uses a Red-Black Internally which should give you a nice balance between performance and memory
插入为O（log n）的
遍历是O（n）
Insertion is O(log n)
Traversal is O(n)
这篇关于如何排序数序列环绕的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！