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

Question

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

例如，我有 100 字节的串行数据，只能读取一次，还有 40 字节的缓冲区。我需要打印出排序的字节。

我需要它在 Javascript 中，但任何一般的想法都是值得赞赏的。

Answer 1

这种排序是不可能一次性完成的。

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

与您的问题最相关的可能是外部排序算法，它需要多次通过才能对无法放入内存的数据进行排序。也就是说，如果你有可以存储处理过程输出的外围设备，你可以在 O(log(N/M)) 个过程中对大于内存的数据进行排序，其中 N 是问题的大小，M 是你的内存大小。

用于外部排序的经典存储外围设备是磁带机；但是，相同的算法适用于磁盘驱动器（任何类型）。此外，随着缓存层次结构的深入，外部排序的原则甚至对于内存中的排序也变得更加相关 - 尝试看看缓存忽略算法。