数据结构与算法第9章文件管理和外排序.ppt

《数据结构与算法第9章文件管理和外排序.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法第9章文件管理和外排序.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。数据结构与算法第9章文件管理和外排序 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。主要内容主要内容o9.1 主存储器和外存储器主存储器

2、和外存储器o9.2 文件的组织和管理文件的组织和管理o9.3 外排序外排序o9.4 文件管理和外排序知识点总结文件管理和外排序知识点总结“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.1 9.1 主存储器和外存储器主存储器和外存储器o 计算机存储器主要有两种：n主存储器(primary memory或者main memory，简称“内存”，或者“主存”)随机访问存储器(Random Access Memory,即RAM)高速缓存(cache)视频存储器(video memo

3、ry)n外存储器(peripheral storage或者secondary storage，简称“外存”)硬盘软盘磁带“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。外存的优缺点外存的优缺点o优点：价格低、信息不易失、便携性 o缺点：存取速度慢 一般的内存访问存取时间的单位是纳秒（1纳秒=10-9秒），而外存一次访问时间则以毫秒（1毫秒=10-3秒）或秒为数量级。o牵扯到外存的计算机程序应当尽量减少外存的访问和存取次数，从而减少程序执行的时间“十一五十一五”国家级规划教材。张

4、铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。内存的优缺点内存的优缺点o优点：访问速度快o缺点：造价高、存储容量小和断电后丢 失数据oCPU直接与主存沟通，对存储在内存地址的数据进行访问时，所需要的时间可以看作是一个很小的常数“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。外存数据访问方式外存数据访问方式p外存空间被划分成长度固定的存储块，称为页(page)，每一页包含一定数量的数据单元p作为

5、外存的基本存储单位，数据以页块为单位进行存取，这样可以减少外存的定位次数，从而减少外存读写的时间耗费“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.2 9.2 文件的组织和管理文件的组织和管理o文件(file)是存储在外存上的数据结构，是由大量性质相同的记录(record)组成的集合。o所谓记录，就是具有独立逻辑意义的数据块，是文件的基本数据单位。o最简单的记录可以是字符或者二进制序列，复杂的记录通常可以由若干字段或域(field)的数据项组成。“十一五十一五”国家级规划教

6、材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.2 9.2 文件的组织和管理文件的组织和管理按照记录的类型，文件可以分成两种：o操作系统的文件 操作系统的文件是一组连续的字符序列，这种序列没有明显的结构。用户也可以将文件中的信息划分成若干个逻辑记录，以便存取和使用。o数据库文件 数据库文件是有结构的记录集合，其中每一条记录都由一个或多个数据项组成，而每个数据项是不可再分的基本数据单元。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算

7、法，高教社，高教社，2008.2008.6 6。9.2 9.2 文件的组织和管理文件的组织和管理 如表9.1所示为一个数据库文件，每个学生的信息组成一个记录，每一条记录由6个数据项构成。姓名姓名学号学号性别性别出生年月出生年月所在院系所在院系入学时间入学时间贾由贾由00646125男男1988.5数学数学2006.9.1陈醒陈醒00648308男男1989.7计算机计算机2006.9.1吴轲吴轲00648230男男1988.3计算机计算机2006.9.1王子琪王子琪00648139女女1988.2计算机计算机2006.9.1“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。

8、张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.2 9.2 文件的组织和管理文件的组织和管理按照记录信息长度，文件可以分成o定长文件 如果文件中每一条记录均含有相同的信息长度，那么这种文件称为定长文件。通常定长文件处理起来比较方便。o不定长文件 若文件中的记录不是相等长度的，则称为不定长文件。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.2 9.2 文件的组织和管理文件的组织和管理按照关键码(key)的个数，文件可以分成

9、：o单关键码文件 单关键码文件是指文件的记录中只有一个标识关键码o多关键码文件 多关键码记录文件中，记录除了有一个主关键码以外还允许有若干个次关键码“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.2 9.2 文件的组织和管理文件的组织和管理p文件的操作有实时和批量两种处理方式n实时操作要求有较短的应答响应时间，在接受指令后尽可能快地完成检索或修改任务。n批量的文件处理则允许较长反馈时间。用户可以根据需求选择不同的文件处理方式。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵

10、海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.2 9.2 文件的组织和管理文件的组织和管理o9.2.1 文件组织文件组织o9.2.2 C+的流文件的流文件“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.2.1 9.2.1 文件组织文件组织o文件逻辑组织有以下三种形式：顺序结构的定长记录、顺序结构的变长记录和按关键码存取的记录。o文件的物理结构可以有多种多样的组织方式。常见的物理组织结构有：n顺序文件

11、n散列文件n索引文件n倒排文件“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.2.2 C+9.2.2 C+的流文件的流文件o文件流是以外存文件为输入输出对象的数据流。o文件流与文件不是同一个概念，文件流不是由若干个文件组成的流。文件流本身不是文件，而只是以文件为输入输出对象的流。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.2.2 C+9.2.2 C+

12、的流文件的流文件p标准输入输出流类包括istream，ostream和iostream类nistream是通用输入流和其它输入流的基类，支持输入nostream是通用输出流和其它输出流的基类，支持输出niostream是通用输入输出流和其它输入输出流的基类，支持输入输出p3个用于文件操作的文件类nifstream类，从istream类派生，用来支持从磁盘文件的输入nofstream类，从ostream类派生，用来支持向磁盘文件的输出nfstream类，从iostream类派生，用来支持对磁盘文件的输入和输出“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海

13、燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.2.2 C+9.2.2 C+的流文件的流文件 下面是下面是fstream类的一些主要成员函数：类的一些主要成员函数：#include /fstream=ifstream+ofstreamvoid fstream:open(char*name,openmode mode);/打开文件进行处理fstream:read(char*ptr,int numbytes);/从文件当前位置读入一些字节fstream:write(char*ptr,int numbtyes);/向文件当前位置写入一些字节/seekg和seekp：

14、在文件中移动当前位置，以便在文件中的任何位置读出或写入字节fstream:seekg(int pos);/输入时用于设置读取位置fstream:seekg(int pos,ios:curr);fstream:seekp(int pos);/设置输出时的写入位置fstream:seekp(int pos,ios:end);void fstream:close();/处理结束后关闭文件“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.2.2 C+9.2.2 C+的流文件的流文件文

15、件常见的三个基本操作：o把文件指针设置到指定位置o从文件的当前位置读取字节o向文件中的当前位置写入字节，都是围绕文件指针进行的n程序员对磁盘文件进行输入输出时，都需要管理标志文件当前位置的文件指针。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3 9.3 外排序外排序o9.3.1 置换选择排序置换选择排序 o9.3.2 二路外排序二路外排序o9.3.3 多路归并多路归并选择树选择树“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，

16、数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3 9.3 外排序外排序o如果数据存放在外存文件中，则需要考虑外存特点，采用外存文件排序技术，简称外排序(external sort)。o需要根据内存的大小，将外存中的数据文件划分成若干段，每次把其中一段读入内存并用内排序方法进行排序。这些已排序的段或有序的子文件称为顺串或归并段(run)。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3 9.3 外排序外排序o外排序通常由两个相对独立的阶段组成

17、：n文件形成尽可能长的初始顺串n逐趟归并顺串，最后形成对整个数据文件的排列文件p外排序所需要的时间由三部分组成：n内部排序所需要的时间n外存信息读写所需要的时间n内部归并所需要的时间 p减少外存信息的读写次数是提高外部排序效率的关键“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3 9.3 外排序外排序o对同一个文件而言，进行外排序所需读写外存的次数与归并趟数有关系o假设有m个初始顺串，每次对k个顺串进行归并，归并趟数为logkmp为了减少归并趟数，可以从两个方面着手：n减

18、少初始顺串的个数mn增加归并的顺串数量k“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3.1 9.3.1 置换选择排序置换选择排序o算法的处理过程为：从输入文件读取一定数量算法的处理过程为：从输入文件读取一定数量的记录进入输入缓冲区；然后向内存工作区放的记录进入输入缓冲区；然后向内存工作区放入待排序记录并进行排序；记录被处理后，写入待排序记录并进行排序；记录被处理后，写到输出缓冲区；当输出缓冲区写满的时候，把到输出缓冲区；当输出缓冲区写满的时候，把整个缓冲区写回到外存文件

19、。当输入缓冲区为整个缓冲区写回到外存文件。当输入缓冲区为空时，再次从外存文件中读取下一块记录。空时，再次从外存文件中读取下一块记录。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3.1 9.3.1 置换选择排序置换选择排序置换选择示例置换选择示例 30154525504935601627“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3.1 9.3.1

20、 置换选择排序置换选择排序 置换选择产生一个顺串的算法如下：1、初始化堆初始化堆：（1）从磁盘读M个记录放到数组RAM中；（2）设置堆尾指标LAST=M 1；（3）建立一个最小堆。2、重复以下步骤，直到堆为空（即重复以下步骤，直到堆为空（即LAST 0LAST 0）：）：（1）把具有最小关键码值的记录(根结点)送到输 出缓冲区；“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3.1 9.3.1 置换选择排序置换选择排序（2）设R是输入缓冲区中的下一条记录。判断R的关键码值是

21、否大于刚刚输出的关键码值，如果是，那么把R放到根结点。否则，(a)使用数组中LAST位置的记录代替根 结点；(b)把R放到LAST位置；(c)设置LAST=LAST-1。（3）重新排列堆，筛出根结点。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3.1 9.3.1 置换选择排序置换选择排序【算法算法9.1】置换选择算法/参数A是从外存读入数据后所存放的数组，n是数组元素的个数，in和out是输入和输出文件名templatevoid replacementSelection

22、(T*A,int n,const char*in,const char*out)T mval;/存放最小堆的最小值T r;/存放从输入缓冲区中读入的元素FILE*inputFile;/输入文件句柄FILE*outputFile;/输出文件句柄Buffer input;/输入缓冲区Buffer output;/输出缓冲区initFiles(inputFile,outputFile,in,out);/初始化输入输出文件“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3.1 9.

23、3.1 置换选择排序置换选择排序initMinHeapArry(inputFile,n,A);/从输入文件读入n个数据初始化堆数组AMinHeap H(A,n);/建立最小堆 initInputBuffer(input,inputFile);/初始化输入缓冲区，读入一部分数据for(int last=(n-1);last=0;)/堆不为空mval=H.heapArray0;/获得堆的最小值sendToOutputBuffer(input,output,inputFile,outputFile,mval);/把mval送到输出缓冲区input.read(r);/从输入缓冲区读入一个记录rif(!

24、less(r,mval)/如果r值大于等于输出值，r放到堆的根结点H.heapArray0=r;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。else /r不能入堆H.heapArray0=H.heapArraylast;/用堆中last位置的记录代替根结点H.heapArraylast=r;/把r放到last位置H.setSize(last);/堆规模减小1 last-;/设置LAST=LAST-1if(last!=0)/重新排列堆H.SiftDown(0);/从根结点开始

25、向下筛选endUp(output,inputFile,outputFile);/处理输出缓冲区，关闭输入和输出文件9.3.1 9.3.1 置换选择排序置换选择排序“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3.1 9.3.1 置换选择排序置换选择排序 置换选择排序算法得到的顺串长度并不相等。平均情况下，置换选择排序算法可以形成长度为2M的顺串。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社

26、，高教社，2008.2008.6 6。9.3.2 9.3.2 二路外排序二路外排序 处理方法：即首先把数据文件划分成若干段，用有效的内排序方法对文件的各段进行初始排序以形成顺串；然后把这些顺串逐趟合并，直至变为一个顺串为止。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3.2 9.3.2 二路外排序二路外排序图图9.3 9.3 二路归并过程二路归并过程“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，

27、高教社，高教社，2008.2008.6 6。9.3.2 9.3.2 二路外排序二路外排序o为一个待排文件创建尽可能大的初始顺串，可以大大减少扫描遍数和外存读写次数。o归并顺序的安排也能影响读写次数，把初始顺串长度作为权，其实质就是Huffman树最优化问题。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。9.3.3 9.3.3 多路归并多路归并选择树选择树ok路归并是每次将k个顺串合并成一个排好序的顺串。一般情况下，对m个初始顺串进行k路归并时归并趟数为logkm。增加每次归并

28、的顺串数量k可以减少归并趟数。o选择树是完全二叉树，有两种类型：赢者树和败者树。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。赢者树赢者树o假设用完全二叉树的公式化描述方法来定义赢者树，采用数组作为存储结构。n选手或叶结点用数组L1.n表示，内部结点用数组B1.n-1表示n数组B中实际存放的是数组L的索引o赢者树的一个优点是，如果一个选手Li的分数值改变了，可以很容易地修改这棵赢者树。只需要沿着从Li到根结点的路径修改二叉树，而不必改变其它比赛的结果。“十一五十一五”国家级规

29、划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。赢者树赢者树【代码代码9.2】赢者树的类定义templateclass WinnerTree private:int MaxSize;/最大选手数int n;/当前选手数int LowExt;/最底层外部结点数int offset;/最底层外部结点之上的结点总数int*B;/赢者树数组，存储数组L的索引T*L;/叶结点数组“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教

30、社，2008.2008.6 6。赢者树赢者树/在内部结点Bp处开始从右分支向上比赛void Play(int p,int lc,int rc,int(*winner)(T A,int b,int c);public:WinnerTree(int Treesize=MAX);/构造函数WinnerTree()delete B;/析构函数void Initialize(T A,int size,int(*winner)(T A,int b,int c);/初始化赢者树int Winner();/返回最终胜者的索引void RePlay(int i,int(*winner)(T A,int b,in

31、t c);/外部Li改变后重构赢者树;“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。赢者树赢者树图图9.59.5 8 8路合并的赢者树路合并的赢者树 “十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。赢者树赢者树图9.6 重构后的赢者树“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社

32、，高教社，2008.2008.6 6。败者树败者树 o败者树是赢者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让获胜者去参加更高阶段的比赛。o另外，根结点处加入一个结点来记录整个比赛的胜者。o采用败者树是为了简化重构的过程。“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。败者树败者树重构过程如下：o将新进入选择树的结点与其父结点进行比赛n把败者的下标存放在父结点中n而胜者再与上一级的父结点比较o比赛沿着到根结点的路径不断进行，直到结点B1处n把败者的索引

33、放在结点B1n把胜者的索引放到结点B0“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。败者树败者树图图9.79.7 8 8路合并的败者树示例路合并的败者树示例 “十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。败者树败者树图图9.8 9.8 重构后的重构后的8 8路合并败者树路合并败者树 “十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，

34、王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。败者树败者树p利用败者树实现多路归并排序算法，首先初始化一棵败者树，取得最终胜者的索引。n把胜者送入输出缓冲区中，如缓冲区已满，就把输出缓冲区的数据传输到磁盘文件中n然后再从输入缓冲区中读入一个新的关键码，重新从叶结点到根结点调整败者树选择下一个胜者n如果输入缓冲区为空，则从输入文件读取一批数据进输入缓冲区；如果对应输入文件已经没有数据了（本顺串数据处理完毕），就在新的竞赛者位置置入一个较大的数“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结

35、构与算法，高教社，高教社，2008.2008.6 6。多路归并的效率多路归并的效率假设对k个顺串进行归并：o原始方法：找到每一个最小值的时间是O(k)，产生一个大小为n的顺串的时间复杂度是O(kn)o败者树方法：对k个顺串进行归并，初始化包含k个选手的败者树，需要时间O(k)，把最小值输出到缓冲区后，读入一个新值并重构败者树的时间为O(log k)，那么产生一个大小为n的顺串的总时间缩短为O(k+nlog k)，近似于O(nlog k)o显然败者树归并效率更高“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社

36、，2008.2008.6 6。o主存储器和外存储器的特点 o文件的组织形式o外排序思想o置换选择排序o二路外排序 o选择树（赢者树和败者树）9.4 9.4 文件管理和外排序知识点总结文件管理和外排序知识点总结“十一五十一五”国家级规划教材。张铭，王腾蛟，赵海燕，国家级规划教材。张铭，王腾蛟，赵海燕，数据结构与算法数据结构与算法，高教社，高教社，2008.2008.6 6。The EndThe EndThe EndThe EndThank You!Thank You!http:/ 张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕张铭，王腾蛟，赵海燕高等教育出版社，高等教育出版社，高等教育出版社，高等教育出版社，高等教育出版社，高等教育出版社，2008.2008.2008.2008.2008.2008.6 6 6 66 6。“十一五十一五十一五十一五十一五十一五”国家级规划教材国家级规划教材国家级规划教材国家级规划教材国家级规划教材国家级规划教材