数据结构与算法数据结构与算法DATASTRUCTUREDATASTRUCTUREANDARITHMETICANDARITHMETIC计算机专业本科主干基础课第8章外部排序8.1外部排序的方法8.1.1外部排序的方法8.1.2多路平衡归并8.1.3置换-选择排序8.2最佳归并树8.1.1外部排序的基本过程待排序的记录数量巨大，无法一次将待排序的记录全部调入内存，一部分数据只能驻留在外存上（磁带、磁盘、CD-ROM）上。不能使用内部排序的方法进行排序。否则将引起频繁访问外存。8.1外部排序的方法当记录以文件的形式存于磁盘上时，通常是按当记录以文件的形式存于磁盘上时，通常是按物理块来存放的，物理块来存放的，物理块也叫做页块。物理块也叫做页块。每个页每个页块可存放若干个记录。操作系统是按页块对磁块可存放若干个记录。操作系统是按页块对磁盘信息进行读写盘信息进行读写。。磁盘通常是指由若干片磁盘组成的磁盘组磁盘通常是指由若干片磁盘组成的磁盘组,,各各个盘片安装在同一主轴上高速旋转。各个盘面个盘片安装在同一主轴上高速旋转。各个盘面上半径相同的磁道构成了柱面。各盘面设置一上半径相同的磁道构成了柱面。各盘面设置一个读写磁头，它们装在同一活动臂上，活动臂个读写磁头，它们装在同一活动臂上，活动臂可以直接从一个柱面移到另一个柱面上。可以直接从一个柱面移到另一个柱面上。为了访问某一页块为了访问某一页块,,先寻找柱面先寻找柱面::活动臂使读活动臂使读写磁头移到指定柱面上写磁头移到指定柱面上::寻查寻查(seek)(seek)。再根据。再根据盘面号选择相应读写磁头盘面号选择相应读写磁头,,等待指定页块转到等待指定页块转到读写磁头下读写磁头下::等待等待(latency)(latency)。传输一个字符的。传输一个字符的时间为时间为trw，则在磁盘组上读写一个页块的时间：则在磁盘组上读写一个页块的时间：tio＝tseek＋tlatency＋trw外排序主要的时间开销用在信息的内、外存交换上，内存排序所需时间可以忽略不计，因此在外排序的过程中主要考虑访问外存的次数。•当记录以文件的形式存于磁盘上时，其排序过程主当记录以文件的形式存于磁盘上时，其排序过程主要分为两个阶段：要分为两个阶段：(2)(2)、、把把(1)(1)生成的生成的初始归并段加以归并初始归并段加以归并,,逐步扩大归并段和减少归并段个数逐步扩大归并段和减少归并段个数,,直到最后直到最后归并成一个归并段归并成一个归并段((有序文件有序文件))为止。为止。基于磁盘进行的排序多使用归并排序方法基于磁盘进行的排序多使用归并排序方法。。(1)(1)、建立用于外排序的内存缓冲区。根据它们、建立用于外排序的内存缓冲区。根据它们的大小将输入文件划分为若干段的大小将输入文件划分为若干段,,用某种内排用某种内排序方法对各段进行排序。经过排序的段叫做序方法对各段进行排序。经过排序的段叫做初初始归并段始归并段。当它们生成后就被写到外存中去。。当它们生成后就被写到外存中去。•例：例：设有一个包含设有一个包含45004500个记录的输入文件。个记录的输入文件。现用一台其内存至多可容纳现用一台其内存至多可容纳750750个记录的计算个记录的计算机对该文件进行排序。输入文件放在磁盘上，机对该文件进行排序。输入文件放在磁盘上，磁盘每个页块可容纳磁盘每个页块可容纳250250个记录个记录,,这样全部这样全部记录可存储在记录可存储在4500/2504500/250＝＝1818个页块中。个页块中。输出文件也放在磁盘上输出文件也放在磁盘上,,用以存放归并结果。用以存放归并结果。•由于内存中可用于排序的存储区域能容纳由于内存中可用于排序的存储区域能容纳750750个记录个记录,,因此内存中恰好能存因此内存中恰好能存33个页块个页块的记录的记录..•在外排序一开始在外排序一开始,,把把1818块记录块记录,,每每33块一块一组组,,读入内存。利用某种内排序方法进行内读入内存。利用某种内排序方法进行内排序排序,,形成初始归并段形成初始归并段,,再写回外存。总共再写回外存。总共可可得到得到66个初始归并段个初始归并段。然后一趟一趟进行。然后一趟一趟进行归并排序。归并排序。两路归并排序的归并树两路归并排序的归并树R1750R2750R3750R4750R5750...
