基于非比较排序问题的排序算法？
我目前面临着一个困难的排序问题。我有一个事件集合，这些事件需要根据彼此(一个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给出了我选择的答案，但我想指出的是，他的答案是插入排序，其他几个人提供了插入排序类型的答案。对我来说，这证实了一个专门的插入排序可能是可行的。感谢你们所有人的回答。
回答 9
Stack Overflow用户
发布于 2008-11-17 21:49:16
这实际上不仅仅是一个排序问题。这是一个带交货期的单机调度问题。根据你正在尝试做的事情，这个问题可能是NP难的。例如，如果您试图最小化完成时间的加权和(权重与优先级成反比)，则问题的categorized为
1|ri;pmtn|Σ wiCi 并且是NP-难的。有许多关于这个主题的papers，但它可能比您需要的更多。
在您的情况下，您永远不会想要一个有间隙的解决方案，所以您可能只需要做一个简单的离散事件模拟( 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
}
}一个问题是，您可能有一个低优先级作业，它的发布时间恰好在一个短的、高优先级作业之前，但它将生成一个具有无间隙属性的调度(如果没有间隙的调度是可能的)。
Stack Overflow用户
发布于 2008-11-17 22:04:03
我认为：
- Sort tasks by priority
- 将任务放入时间线中，在earliestTime之后的第一个可用空位，这个空位有一个足够大的空洞来完成任务。
将时间线转换为列表a任务，并等待(间隔)。
问题：
- Are gaps？
- 可以拆分任务吗？
- 给出如下问题中的任务:是延迟b完成c更好，还是执行d更好，以便b可以按时开始？
编辑：
我的问题的答案是：
- No (ish -如果没有要运行的内容，我猜我们可能会有一个不清楚的gap)
- No
- Still，但我猜这个示例建议运行c并延迟b。
在这种情况下，算法可能是：
- Sort by priority
- Keep以t=0
- Search开始在已排序列表中搜索当前‘时间’的计数器，对于可以在t开始的最高优先级项目。
- 将项目添加到运行顺序，并将其持续时间添加到t。
- 重复3&4，直到列表耗尽。如果在% t没有可运行的任务，并且仍有未完成的任务，请按运行顺序保留1秒的休眠任务。
该算法也是O(n^2)。
Stack Overflow用户
发布于 2008-11-17 21:48:00
换句话说，您希望在制定两个约束的同时优化整体运行时间(强:最早执行点，弱:优先级)？这称为constraint satisfaction problem。对于这类问题，有专门的解算器。
顺便说一句，jakber的解决方案不起作用。即使没有持续时间，下面的示例显然也失败了：
event a (priority = 1, start = 5)
event b (priority = 2, start = 0)排序的序列将是a，b，而想要的结果肯定是b，a。
https://stackoverflow.com/questions/297035
复制相似问题
腾讯云开发者
