使用缓冲区对串行数据进行排序

Question

是否有任何算法使用小于数据长度的缓冲区对串行输入中的数据进行排序？

例如，我有100个字节的串行数据，它可以只读一次，并有40个字节的缓冲区。我需要打印分类的字节。

我需要它在JavaScript中，但任何一般的想法，赞赏。

Answer 1

这种分类不可能在一次通过。

使用你的例子：假设你已经填充了你的40字节缓冲区，所以你需要开始打印出字节，以便为下一个缓冲区腾出空间。为了打印排序的数据，您必须先打印最小的字节。但是，如果最小的字节没有被读取，您不可能将其打印出来！

与您的问题最接近的相关信息可能是external sorting算法，这些算法需要多次通过才能对无法放入内存的数据进行排序。也就是说，如果外围设备可以存储处理过程的输出，则可以在O（log（N/M））遍中对数据大于内存进行排序，其中N是问题的大小，M是记忆的大小。

用于外部分类的经典存储外设是磁带机;然而，相同的算法适用于磁盘驱动器（不管是什么类型）。此外，随着缓存层次的深入发展，即使对于内存分类，外部分类的原则也变得更加相关 - 请尝试查看cache-oblivious算法。