使用緩衝區對串行數據進行排序

Question

是否有任何算法使用小於數據長度的緩衝區對串行輸入中的數據進行排序？

例如，我有100個字節的串行數據，它可以只讀一次，並有40個字節的緩衝區。我需要打印分類的字節。

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

Answer 1

這種分類不可能在一次通過。

使用你的例子：假設你已經填充了你的40字節緩衝區，所以你需要開始打印出字節，以便爲下一個緩衝區騰出空間。爲了打印排序的數據，您必須先打印最小的字節。但是，如果最小的字節沒有被讀取，您不可能將其打印出來！

與您的問題最接近的相關信息可能是external sorting算法，這些算法需要多次通過才能對無法放入內存的數據進行排序。也就是說，如果外圍設備可以存儲處理過程的輸出，則可以在O（log（N/M））遍中對數據大於內存進行排序，其中N是問題的大小，M是記憶的大小。

用於外部分類的經典存儲外設是磁帶機;然而，相同的算法適用於磁盤驅動器（不管是什麼類型）。此外，隨着緩存層次的深入發展，即使對於內存分類，外部分類的原則也變得更加相關 - 請嘗試查看cache-oblivious算法。