数据结构 第三部分学习 文档 参考.ppt

* 外排序的模型 由于一次外存操作所需的时间可以执行数百条甚至上千条指令因此在外排序中主要考虑的是如何减少外存储器的读写 在外存上进行排序的最常用的方法是利用归并排序因为归并排序只需要访问被归并序列中的第一个元素这非常适合于顺序文件 外排序由两个阶段组成 预处理阶段根据内存的大小将一个有n个记录的文件分批读入内存用各种内排序算法排序形成一个个有序片段 归并阶段将这些有序片段逐步归并成一个有序文件