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

我目前面临一个困难的排序问题.我有一组事件需要相互排序(比较排序)和它们在列表中的相对位置.

在最简单的术语中,我有事件列表,每个事件都有一个优先级(整数),一个持续时间(秒),以及事件可以出现在列表中的最早发生时间.我需要根据优先级对事件进行排序,但是在最早发生的时间之前,列表中不会出现任何事件.这是一个(希望)让它更清晰的例子:

// 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 results = Sort( new List { 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"之前就已经开始,即使它的优先级较低.(希望以上解释我的问题,如果不让我知道,我会编辑它.)

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

我希望找到有关排序算法和数据结构的资源,以帮助我为这种"排序"问题设计一个很好的解决方案.我真正的问题实际上比这更复杂:分层排序,事件之间的变量缓冲,多个非恒定时间约束,因此越多的信息或想法越好.速度和空间并不是真正的问题.分类的准确性和代码的可维护性是一个问题.

编辑:澄清(基于评论)

事件消耗整个持续时间(即不允许事件重叠)

事件必须在他们最早的时间或之后发生,他们不能在他们最早的时间之前发生.

如果存在较低优先级事件,则事件可以晚于其最早时间发生

事件不能中断

最大持续时间是可以放入列表中的所有事件的总和.这未在上面显示.(实际上,所有事件的持续时间将远远大于时间列表的最大持续时间.)

没有任何差距.(没有空洞可以尝试回填.)

编辑:答案

虽然David Nehme给出了我选择的答案,但我想指出他的答案是插入的内心,其他几个人提供了插入排序类型的答案.这向我证实了专门的插入排序可能是要走的路.感谢大家的回答.

这实际上不仅仅是一个排序问题.这是发布日期的单机调度问题.根据您的尝试,问题可能是NP-Hard.例如,如果您试图最小化完成时间的加权和(权重与优先级成反比),则问题被归类为

1|ri;pmtn|? wiCi 

并且是NP难的.关于这个主题有很多论文,但它可能不仅仅是你需要的.

在您的情况下,您永远不需要具有间隙的解决方案,因此您可能只需要进行简单的离散事件模拟(O(n log(n)))时间.您需要将released_jobs存储为优先级队列.

unreleased_jobs = jobs  // sorted list of jobs, by release date
released_jobs = {}      // priority queue of jobs, by priority
scheduled_jobs = {}     // simple list
while (!unreleased_jobs.empty() || !released_jobs.empty()) {

    while (unreleased_jobs.top().earliestTime  <= t) {
        released_jobs.push(unreleased_jobs.pop())
    }
    if (!released_jobs.empty()) {
       next_job = released_jobs.pop();
       scheduled_jobs.push_back(next_job)
       t = t + next_job.duration
    } else {
       // we have a gap
       t = unreleased_jobs.top().earliestTime
    }
}

一个问题是,您可能会在短暂的高优先级作业之前拥有一个发布时间较低的优先级作业,但它会生成一个具有无间隙属性的计划(如果可能没有间隙的计划) .