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

Question

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

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

我需要它在 Javascript 中，但任何一般的想法都会受到赞赏。

Answer 1

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

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

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

外部排序的经典存储外设是磁带机；然而，相同的算法适用于磁盘驱动器(无论何种类型)。此外，随着缓存层次结构的深入，外部排序的原则变得更加相关，即使对于内存中排序也是如此——试着看看 cache-oblivious。算法。