问基于非比较排序问题的排序算法？

EN

我目前面临着一个困难的排序问题。我有一个事件集合，这些事件需要根据彼此(一个comparison sort)以及它们在列表中的相对位置进行排序。

在最简单的术语中，我有一个事件列表，每个事件都有优先级(整数)、持续时间(秒)和事件可以出现在列表中的最早发生时间。我需要根据优先级对事件进行排序，但列表中不能出现早于其最早发生时间的事件。这里有一个例子(希望)能让它更清楚：

// Psuedo C# code
class Event { int priority; double duration; double earliestTime ; }

void Example()
{
    Event a = new Event { priority = 1, duration = 4.0, earliestTime = 0.0 };
    Event b = new Event { priority = 2, duration = 5.0, earliestTime = 6.0 };
    Event c = new Event { priority = 3, duration = 3.0, earliestTime = 0.0 };
    Event d = new Event { priority = 4, duration = 2.0, earliestTime = 0.0 };

    // assume list starts at 0.0 seconds
    List<Event> results = Sort( new List<Event> { a, b, c, d } );

    assert( results[ 0 ] == a ); // 4.0 seconds elapsed
    assert( results[ 1 ] == c ); // 7.0 seconds elapsed
    assert( results[ 2 ] == b ); // 12.0 seconds elapsed
    assert( results[ 3 ] == d ); // 14.0 seconds elapsed
}

项目"b“必须排在最后，因为它直到列表中的6.0秒才能开始，所以它被推迟了，即使它的优先级较低，"c”也会排在"b“之前。(希望上面解释了我的问题，如果不能，请让我知道，我会编辑它。)

我现在的想法是使用insertion sort来管理排序过程。与许多其他常见的排序算法不同，插入排序一次一个地按顺序决定列表的顺序。因此，对于每个索引，我应该能够找到下一个最低优先级的事件，它的最早发生时间将得到满足。

我希望找到关于排序算法和数据结构的资源，以帮助我为这种“排序”问题设计一个好的解决方案。我真正的问题实际上比这复杂得多:分层排序，事件之间的可变缓冲区，多个非常量时间约束，所以信息或想法越多越好。速度和空间并不是真正需要考虑的问题。排序的准确性和代码的可维护性是一个问题。

编辑：澄清(基于注释)

优先级较低的事件会占用整个持续时间(也就是说，在优先级较低的事件发生时或之后发生的事件不会重叠，如果存在优先级较低的事件，则不能在优先级较低的事件发生之前发生。如果存在较低优先级的事件，则allowed)

• Events

• be earliestTime是最大持续时间可以包含在列表中的所有事件的总和。上面没有显示这一点。(在现实中，所有事件的持续时间都会远远大于时间列表的最大duration.)

• There，不能有任何间隙。(没有空洞可以尝试和回填。)

编辑：应答

虽然David Nehme给出了我选择的答案，但我想指出的是，他的答案是插入排序，其他几个人提供了插入排序类型的答案。对我来说，这证实了一个专门的插入排序可能是可行的。感谢你们所有人的回答。