我们知道，一般来说，“更智能”的比较会根据最坏情况的复杂度O（N * log（N））对任意数据运行进行排序。将流数据读入排序列表
我的问题是如果我们被要求不对一个集合进行排序而是对一个数据流进行排序会发生什么。也就是说，值是一个接一个地给我们的，没有指示接下来会发生什么（除了数据是有效的/在范围内）。直观地说，人们可能会认为它比排序数据更好（比如像一个接一个地拿起扑克牌），而不是收集所有数据并稍后排序（在处理完扑克牌后排序）。这是真的吗？
收集和排序将是O（N + N *日志（N））= O（N *日志（N））。然而，如果我们对它进行排序，它是O（N * K），其中K =找到合适的索引+时间来插入元素的时间。这使事情变得复杂，因为现在K的价值取决于我们对数据结构的选择。一个数组在寻找索引方面优越，但浪费时间插入元素。链接列表可以更容易地插入，但无法进行二分查找来查找索引。
是否有关于此问题的完整讨论？我们什么时候应该使用一种方法？可能会有一个理想的中间策略，每隔一段时间排序一次？
Balanced tree sort有O(N log N)复杂性和同时添加的元素在维持有序列表。
绝对不是！首先，如果我可以对流数据进行排序，我可以接受我的所有数据，然后将其流式传输给我自己，并使用更快的方法对其进行排序。即您可以从全数据到数据流执行缩减，这意味着它不能更快。
其次，你所描述的插入排序，这实际上在O(N^2)时间运行（即您的O(NK)描述是正确的，但K不恒定的N而是一个功能），因为它可能需要O(N)时间找到适当的指数。您可以将其改进为二进制插入排序，但这将运行在O(NlogN)（假设您正在使用链表，即使使用二进制优化，数组仍然需要O(N^2)），所以您没有真正保存任何内容。
也许还值得一提的一般原则;只要你在比较模型中（即你没有任何有关你正在排序的数据的非平凡和有用的信息，这是一般情况），任何排序算法最多只能是O(NlogN)。即此模型中排序算法的最差情况运行时间为omega(NlogN)。这不是一个假设，而是一个定理。所以不可能更快地找到任何东西（在相同的假设下）。
好吧，如果流的时间比较慢，会在您的最后一个元素到达时有一个完全排序的列表（减去最后一个元素）。然后，剩下要做的就是一个单一的二进制搜索周期， O（log n）的不是一个完整的二进制排序，为O（n log n）的。潜在地，有一个可感知的性能增益，因为你在其他排序算法上获得了先机。
管理，排队，从流中提取的数据是完全不同的问题，可能会适得其反，你的意图。我不会推荐这种方法，除非您可以在大致相同的时间对一个或两个元素进行流式处理来完成整个数据集的排序（并且您对编码流式传输部分感觉良好）。
使用堆排序在树排序行为不佳的情况下，即大型数据集，因为树排序需要额外的空间来存储树结构。