问题描述
我读的由乔恩·本特利（的）。
I am reading Programming Pearls by Jon Bentley (reference).
下面笔者提有关各种排序算法，如归并排序，多通道排序。
Here author is mentioning about various sorting algorithms like merge sort, multipass sort.
问题：
-
如何通过读取输入文件一次，使用的工作文件，并写入输出文件只有一次确实算法合并排序工作？
How does algorithm for merge sort work by reading input file once and using work files and writing output file only once?
如何撰文表示，该40通即多道排序算法的工作方式是只写一次输出文件并没有工作文件？
How does the author denote that the 40 pass i.e. multipass sort algorithm works by writing only once to output file and with no work files?
有人能解释一下上面的一个简单的例子，像有内存来存储3位数字，并具有10位存储，如 9,0,8,6,5,4,1,2,3,7
Can someone explain the above with a simple example, like having memory to store 3 digits and having 10 digits to store, e.g. 9,0,8,6,5,4,1,2,3,7
推荐答案
这是从编程珠玑（第二版）由Jon宾利，这是一个很好的书第1章。从第一版的等效例子略有不同;在多通道算法只取得了27越过数据（并有较少的内存可用）。
This is from Chapter 1 of 'Programming Pearls' (second edition) by Jon Bentley, which is an excellent book. The equivalent example from the first edition is slightly different; the multipass algorithm only made 27 passes over the data (and there was less memory available).
由乔恩·本特利描述的那种拥有特殊的设置限制。
The sort described by Jon Bentley has special setup constraints.
- 文件含有10万条记录。
- 在每个记录是7位数字。
- 在没有与记录相关联的其他数据。
- 还有就是内存仅1时MIB排序必须做到的。
输入文件的单一读出吸食从输入尽可能多的行作为将适合在存储器中，排序该数据，并将其写入出到工作文件。冲洗和重复，直到有输入文件中没有更多的数据。
The single read of the input file slurps as many lines from the input as will fit in memory, sorts that data, and writes it out to a work file. Rinse and repeat until there is no more data in the input file.
然后，通过阅读工作文件和排序后的内容合并成一个单一的输出文件的完整过程。在极端情况下，可能有必要建立新的，更大的工作文件，因为该程序无法读取所有的工作文件一次。如果发生这种情况，则安排最终道次以具有可处理的输入的最大数目，和具有中间道次的文件合并适当的数字。
Then, complete the process by reading the work files and merging the sorted contents into a single output file. In extreme cases, it might be necessary to create new, bigger work files because the program can't read all the work files at once. If that happens, you arrange for the final pass to have the maximum number of inputs that can be handled, and have the intermediate passes merge appropriate numbers of files.
这是一个通用的算法。
这是在数据的特殊性质被利用。由于号是唯一的和有限的范围内，该算法可以读取文件的第一时间，从该范围的第一第四十〇提取号码，分拣和写那些;然后提取的范围内，第二第四十〇那么第三，...，那么最后第四十
This is where the peculiar properties of the data are exploited. Since the numbers are unique and limited in range, the algorithm can read the file the first time, extracting numbers from the first fortieth of the range, sorting and writing those; then it extracts the second fortieth of the range, then the third, ..., then the last fortieth.
这是一个特殊用途的算法，利用该号码的性质。
This is a special-purpose algorithm, exploiting the nature of the numbers.
这篇关于关于多通道排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！