编程珠玑

编程珠玑之外排序

外排序,主要应用于对海量数据的排序处理,当数据量特别大以至无法一次性将其装入内存中时,我们常用的快速排序,并归排序,堆排序等排序算法是无法使用的,这也是将这些常用排序算法称之为内排序算法的原因,无法一次性全部装入内存的海量数据被放置在磁盘上(文中我们将放在磁盘上的海量数据称之为大文件),如何高效的排序磁盘上的数据就是外排序算法设计时要考虑的首要问题,毕竟磁盘的访问速度跟内存相比差好几个数量级(磁盘的访问速度是毫秒级的,内存的访问速度是纳秒级的),所以外排序算法设计的关键还是如何高效的利用现有的内存空间,在实际应用中外排序算法的性能(不考虑额外的磁盘I/O情况下)可以达到O(nlgn)