外部排序 [英] external sorting

问题描述

在此网页：

<一个href="http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html">http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html

合并由此而来运行汇集成   先后更大的运行，直到   文件排序。

Merge the resulting runs together into successively bigger runs, until the file is sorted.

在我引用的，我们怎么可以合并由此而来一起运行???我们不哈瓦那么多的记忆。

As I quoted, how can we merge the resulting runs together??? We don't hava that much memory.

推荐答案

想象一下，你有数字1 - 9

Imagine you have the numbers 1 - 9

9  7  2  6  3  4  8  5  1

和我们假设只有3适合在内存中的时间。

And let's suppose that only 3 fit in memory at a time.

所以，你会打破他们成3块，每一个分类，储存每个结果在一个单独的文件：

So you'd break them into chunks of 3 and sort each, storing each result in a separate file:

279
346
158

现在你打开每个三个文件作为流和读取从第一值：

Now you'd open each of the three files as streams and read the first value from each:

2 3 1

输出的最低值 1 ，并从该流的下一个值，现在你有：

Output the lowest value 1, and get the next value from that stream, now you have:

2 3 5

输出下一个最低值 2 ，并继续向前，直到你输了整个排序列表。

Output the next lowest value 2, and continue onwards until you've outputted the entire sorted list.

这篇关于外部排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！