[奶瓶问题。。。。请教专家。。]我儿子刚开始吃配方奶粉的时候我给他买了一个爱得利的奶瓶，冲奶的时候随便怎么摇都不会洒。。几个月之后可能是奶瓶有些变形，冲好摇匀的时候要用纸把瓶子包好，不然会洒得到处都...+阅读

外排序的一个例子是外归并排序（External merge sort），它读入一些能放在内存内的数据量，在内存中排序后输出为一个顺串（即是内部数据有序的临时文件），处理完所有的数据后再进行归并。[1][2]比如，要对 900 MB 的数据进行排序，但机器上只有 100 MB 的可用内存时，外归并排序按如下方法操作：读入 100 MB 的数据至内存中，用某种常规方式（如快速排序、堆排序、归并排序等方法）在内存中完成排序。

将排序完成的数据写入磁盘。 重复步骤 1 和 2 直到所有的数据都存入了不同的 100 MB 的块（临时文件）中。在这个例子中，有 900 MB 数据，单个临时文件大小为 100 MB，所以会产生 9 个临时文件。 读入每个临时文件（顺串）的前 10 MB ( = 100 MB / (9 块 + 1)）的数据放入内存中的输入缓冲区，最后的 10 MB 作为输出缓冲区。（实践中，将输入缓冲适当调小，而适当增大输出缓冲区能获得更好的效果。

） 执行九路归并算法，将结果输出到输出缓冲区。一旦输出缓冲区满，将缓冲区中的数据写出至目标文件，清空缓冲区。直至所有数据归并完成。 为了增加每一个有序的临时文件的长度，可以采用置换选择排序（Replacement selection sorting）。它可以产生大于内存大小的顺串。具体方法是在内存中使用一个最小堆进行排序，设该最小堆的大小为 。

算法描述如下：初始时将输入文件读入内存，建立最小堆。 将堆顶元素输出至输出缓冲区。然后读入下一个记录： 若该元素的关键码值不小于刚输出的关键码值，将其作为堆顶元素并调整堆，使之满足堆的性质； 否则将新元素放入堆底位置，将堆的大小减 1。 重复第 2 步，直至堆大小变为 0。 此时一个顺串已经产生。将堆中的所有元素建堆，开始生成下一个顺串。

[3] 此方法能生成平均长度为 的顺串，可以进一步减少访问外部存储器的次数，节约时间，提高算法效率。[编辑]附加的步骤 上述例子的外排序有两个步骤：排序和归并。我们用一次多路归并就完成了所有临时文件的归并，而并非按内存中的二路归并那样，一次归并两个子串，耗费 次归并。外排序中不适用上述方法的原因在于每次读写都需要对硬盘进行读写，而这时非常缓慢的。

所以应该尽可能减小磁盘的读写次数。不过，在上述方法中也存在权衡。当临时文件（顺串）的数量继续增大时，归并时每次可从顺串中读入的数据减少了。比如说，50 GB 的数据量，100 MB 的可用内存，这种情况下用一趟多路归并就显得不划算。读入很多的顺串花费的时间占据了排序时间的大部分。这时，我们可以用多次（比如两次）归并来解决这个问题。

这时排序算法变为下述这样：第一步不变。 将小的顺串合并为大一些的顺串，适当减小顺串的数目。 将剩余的大一些的顺串归并为最终结果。 和内排序一样，高效的外排序所耗的时间依然是 。若利用好现在计算机上 GB 的内存，可使时间复杂度中的对数项增长比较缓慢。[编辑]优化性能 计算机科学家吉姆·格雷的 Sort Benchmark 网站用不同的硬件、软件环境测试了实现方法不同的多种外排序算法的效率。

效率较高的算法具有以下的特征：并行计算用多个磁盘驱动器并行处理数据，可以加速顺序磁盘读写。[4]在计算机上使用多线程，可在多核心的计算机上得到优化。 使用异步输入输出，可以同时排序和归并，同时读写。 使用多台计算机用高速网络连接，分担计算任务。[5] 提高硬件速度增大内存，减小磁盘读写次数，减小归并次数。 使用快速的外存设备，比如 15000 RPM 的硬盘或固态硬盘。

使用性能更优良个各种设备，比如使用多核心 CPU 和延迟时间更短的内存。 提高软件速度对于某些特殊数据，在第一阶段的排序中使用基数排序。 压缩输入输出文件和临时文件。 [编辑]其他算法 外归并排序法并不是唯一的外排序算法。另外还有外分配排序，其原理类似于内排序中的桶排序。在归并排序和桶排序之间存在数学上的某种对偶性。

[6] 此外还有一些不耗费附加磁盘空间的原地排序算法。[编辑]外部链接 STXXL， 一个包含外归并排序的代码包 外归并排序示例 多路归并实现 Java 语言外归并排序

以下为关联文档：

有问题请教什么是结扎啊？还有宝宝多大可喝成人喝的那种奶啊？ 结扎手术是计划生育的一项有效的绝育手术，它适用于一对夫妇有两个或两个以上的孩子以及其他避孕手段不适用或失败时采用。结...

请教日语问题多谢 ！だ 是 です 的简体。 可以这么理解 太田さんから电话があったんですけれども、まだ企画案が届いていないそうです。 けれども 是正常表达， 口语简化后 けども、けれど、けど...

请教人力成本问题人力资源成本，是指企业在生产运作过程中通过各种方式用于劳动者的全部费用，通常包括职工工资、劳动保护费、职工福利费、教育经费、劳动保险费、工会经费、住房费用等内容。人...

请教函数问题公式K4,L4单元格其中一个为0或为空就返回0，还是两个同时为0或为空时返回0 K4,L4单元格其中一个为0或为空就返回0 =(K4<>0)*(L4<>0)*ROUND(G4+J4-P4,2) 或 =IF(OR(K4=0,L4=0),,ROU...

虚拟内存问题请教？①使用128MB或者更少内存的用户，建议将当前物理内存容量的1。75倍设置为页面文件的最小值。 ②内存大小在128MB到256MB之间的用户，建议将当前物理内存容量的1。5倍设置为页面...

俄语问题请教！центральный процессор 或者мэйнфрейм主机水路 水上运输 водный транспорт （船遇险后）投弃货物 выбрасывать гру...

请教迪拜旅游问题各位达人请慷慨相助，不吝赐教：我的位置是在Al Wasl Road和Thanya Road相交汇的十字路口附近。1.离我最近的地铁站是 First Gulf Bank Metro Station，稍微再远点的是 Mall of th...

请教归并排序的问题？想了很久都不明白1、为什么要加1？原因请看最后一个问题“这里为什么是1~~L.length 而不是0~~L.length-1？”，因为该程序约定关键码的下标从1开始，而不是从0开始 2、每一次递归都要分配内存，那不很...

请教高手：用Excel怎样给一组数字排序排序：很多时候大家排序完以后，想回到开始没有排序前的状态，那么我们只需要在第一列插入“序号”按序号排序就可以恢复到没有排序之前的状态，因为排序只是方便大家查看数据（这样可...