零基础学数据结构 第13章 外排序.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第,13,章 外排序,外排序通常应用于数据量非常大的情况，在排序的过程中，待排序的数据不断地在内存与外存之间进行交换，将已经排序的放在外存，待排序的数据调入内存。比较常用的外排序方法是多路归并法，根据存储待排序文件的存储介质，可分为磁盘排序和磁带排序。本章的主要学习内容包括：外存的存取特性、磁盘排序和磁带排序。,13.1,外存的存取特性,计算机的存储器分为内存储器和外存储器，分别简称为内存和外存。,1,磁盘信息的存取,磁盘是一种随机存取的设备，可以直接存取设备上的数据。磁盘由盘片、磁头、盘片主轴、磁头控制器等组成，其中，盘片是用于存储数据的。盘片被划分为多个同心圆，称为磁道，磁道由外向内从,0,开始顺序编号，所有的数据信息被记录在磁道上。磁盘一般由多个盘片构成，每一个盘片包含两个面，其中，最上面和最下面的外侧的一面不存储信息。例如，一个磁盘由,6,个盘片组成，则有,10,个面可保存信息。,13.1,外存的存取特性,所有的盘面的同一磁道构成一个圆柱，称为柱面，位于同一柱面上的磁道由上往下从,0,开始编号。每个磁道还可以进行划分为若干个部分，被称为扇区，每个扇区的大小是,512,字节。扇区所在的磁道地址称为扇区号。,例如，某磁盘有,10,个有效记录面，记录面上有效记录区域的内径为,20cm,，外径是,30cm,，道密度为,10,道,/mm,，每个磁道有,16,个扇区，每个扇区记录,512,字节，则该磁盘的容量是：记录面数,磁道数,磁道扇区数,扇区的字节数,=10(30-20)/2101016512=40960000,字节,39M,字节。,13.1,外存的存取特性,要存取某一数据信息，首先需要找到数据所在的柱面，移动磁头到所在的柱面即磁道，然后移动磁头到具体的数据存放位置，因此，要存取磁盘上的数据信息所需要的时间由,3,个部分构成：寻道时间、等待时间和传输时间。其中，寻道时间,t,seek,就是读写磁头寻找数据所在磁道并定位的时间，等待时间,t,w,就是将磁头移动到数据信息所在的起始位置，传输时间,t,rw,就是读或写数据所需要的时间。读写数据的所用时间可表示为,T=,t,seek,+t,w,+t,rw,。,13.1,外存的存取特性,磁带作为主要的存储介质，一般磁带长,3600,英尺、宽,0.5,英寸。磁带可以分为,7,道带和,9,道带，,7,道带的磁带，每一排可以存储,8,位即一个字节，其中,7,位是数据位，,1,位奇偶校验位。通常情况下，磁带的存储密度是每英寸,800,位或,1600,位，磁带的移动磁头速度是每秒,200,英寸。,磁带是一种启停设备，当磁头正在读写磁带上的记录，如果要停止读写，必须经过一个减速的过程，然后才能停止。同样，从磁头静止，到开始读写数据时，磁头是经过一个加速旋转的过程，然后才能匀速的旋转达到稳定状态。因此，在磁带的每个相邻的记录之间，需要一个空白区域，这个空白区域就称为间隙。间隙的大小通常为,0.25,英寸,-0.75,英寸。磁带的存储结构如图,13.1,所示。,13.2,磁盘排序,12.2.1,归并排序的基本方法,在外排序中，归并排序的基本思想方法可分为两步：,（,1,）第一步：将待排序的,n,个记录文件按照内存缓冲区的大小，分割为长度为,m,的若干个子文件，将这些子文件分批地不断调入内存，进行归并排序，生成有序的若干个子文件，并放在外存。将这些有序的子文件称为归并段。,（,2,）第二步：对已经有序的归并段继续不断在内存和外存互换，从而进行归并排序，直到待排序文件构成一个有序的序列。,13.2,磁盘排序,按照以上方法归并,R3,和,R4,，得到有序的,600,条记录。然后分别对两个新生成的归并段继续归并，直到待排序文件中所有记录都已经有序，则该文件的,1200,条记录均为有序序列。整个归并排序的过程如图,13.2,所示。,13.2,磁盘排序,因此，总的归并时间可计算如下：（,1,）读入,1200,条记录并进行归并，则需要的时间为,12t,io,+4t,is,；（,2,）将两个归并段即,R,1,和,R,2,归并为,R,1,，,R,3,和,R,4,归并为,R,2,，则需要花费的时间为,12t,io,+1200t,m,；（,3,）然后将,R,1,和,R,2,归并为,R,1,的需要的时间为,12t,io,+1200t,m,。总共需要的时间为,36t,io,+4t,is,+2400,tm,。,13.2,磁盘排序,12.2.2,多路归并排序,多路归并可以有效的减少时间的开销。对于上面提到的,2,路归并，在初始时，如果归并段是,m,个，则将构成的归并树的层数是,+1,，需要进行趟归并才能完成排序。而对于,k,路归并，就是将,k,个归并段进行归并，则将构成,+1,层的归并树，也就是需要进行趟的归并。例如，如果,k=4,，则,16,个归并段的归并过程如图,13.3,所示。,13.2,磁盘排序,选择树是一种完全二叉树，在该完全二叉树中，叶子结点存放各个归并段的当前待排序的元素，非叶子结点则表示对应孩子结点的最小的一个，从叶子结点开始，依次将当前互为兄弟结点中关键字最小的一个存入双亲结点，则根结点的关键字就是当前归并段中最小的一个关键字，即为将要输出的记录。一个,8,路归并排序的选择树如图,13.4,所示。,13.2,磁盘排序,从图,13.4,中可以看出，输出关键字最小的记录，只有刚建立胜方树的时候需要进行,k-1,次比较，即非叶子结点的个数次的比较。当一个关键字最小的记录输出后，只需要进行,-1,次的比较，即只需要将上次最小关键字所在的那棵而叉树比较即可。,与胜方树相对应的还有一个称为败方树的二叉树。与胜方树相反，在败方树中，将兄弟结点中关键字较大的一个存入双亲结点中，而将较小的关键字继续进行比较，在根结点上附加一个结点，将最终的优胜者存放在其中。一个,8,路归并的败方树如图,13.5,所示。,13.2,磁盘排序,在败方树中，当输出当前归并段中最小的关键字的记录后，后面进行的比较次数减少了许多。只需要将归并段的下一个关键字,key,存入叶子结点，并将,key,与其双亲结点的关键字进行比较，将两者中较大的一个存入双亲结点，较小的一个继续与上一层的双亲结点进行比较。重复执行以上操作，直到根结点。因此，当关键字,11,的记录输出后，败方树的修改如图,13.6,所示。,13.3,磁带排序,12.3.1 2,路归并排序,磁带的外排序与磁盘的外排序类似，都是对待排序的,n,条记录分批不断调入内存，进行归并排序后存入磁带，这样不断地在内存与外存之间交换，使归并段不断增大，最终完成排序。,例如，某个待排序的文件有,1200,条记录,(D1,D2,D1200),，能够使用的磁带驱动器（磁带机）有,4,台，分别是,T1,、,T2,、,T3,和,T4,。内存缓冲存储器可存储,300,条记录，因此将待排序的,1200,条记录分为,4,块，每块包含,300,条记录。其中，记录,D1-D300,属于第一块，记录,D301-D600,属于第二块，记录,D601-D900,第三块，记录,D901-D1200,属于第四块。,13.3,磁带排序,磁带的外排序步骤如下：,（,1,）分别将第,1,、,2,、,3,和,4,块调入内存，进行内排序，生成归并段,R1,、,R2,、,R3,和,R4,。然后将这,4,个归并段存储在磁带机,T1,和,T2,上。得到归并段如图,13.7,所示。,（,2,）将归并段,R1,和,R2,调入内存进行归并排序，将,R3,和,R4,调入内存进行归并排序。将每次归并产生的归并段分别存储在磁带,T3,和,T4,上，最终产生新的归并段,R1,和,R2,，,R1,和,R2,分别都包含,600,条记录，并存储在磁带,T3,和,T4,上。如图,13.8,所示。,13.3,磁带排序,（,3,）将归并段,R1,和,R2,按照步骤（,2,）进行归并后得到如图,13.9,所示的归并段,R1,并存储在磁带机,T1,上。,不难看出，磁带的归并排序与磁盘的归并排序的思想一样，其排序所用的时间也主要是在于对记录的扫描次数，归并过程中主要时间的耗费在寻找记录上，而为了避免这种耗费，可以采用多路归并，但是多路归并是以增加磁带机的数量为代价的。对于,k,路归并，需要,k+1,台磁带机，其中,k,台磁带机用于存放输入数据，剩下的,1,台用于存储输出数据。而如果这样做，在对输出的数据排序时，还需要进行扫描，因此，可以使用,2k,台磁带机来避免这种情况，其中，,k,台磁带机用于存储输入的数据，另外,k,台磁带机用于存储输出数据。在排序过程中，这些磁带机来回交换，就避免了对磁带记录的扫描。,13.3,磁带排序,12.3.2,多路非平衡归并排序,非平衡归并排序是为了减少磁带机的使用，并能减少排序过程中的扫描次数。其主要做法是，不同的磁带机上输入的归并段个数不同，通过对归并段的非均匀分配，从而减少磁盘机的使用。,下面通过利用,4,个磁带机实现,3,路归并的情况。例如，要对,14,个归并段进行,3,路归并排序，初始时，归并段不均衡地分布在,T1,、,T2,和,T3,上，,T4,作为输出磁带机。,13.3,磁带排序,第一步：将,T1,、,T2,和,T3,中的,R1,、,R2,、,R3,归并为新的归并段,R1,，将,R4,、,R5,、,R6,归并为新的归并段,R2,，将,R7,、,R8,、,R9,归并为新的归并段,R3,，然后将,R1,、,R2,、,R3,存储在磁带机,T4,中，此时，,T3,为空。第一步归并后的情况如图,13.11,所示。,13.3,磁带排序,第二步：将,T1,、,T2,和,T4,中的,R10,、,R11,、,R1,归并为新的归并段,R1,，将,R12,、,R13,、,R2,归并为新的归并段,R2,，然后将,R1,、,R2,存储在磁带机,T3,中，此时,T2,为空，第二步归并后的情况如图,13.12,所示。,13.3,磁带排序,第三步：将,T1,、,T3,和,T4,中的,R14,、,R1,、,R3,归并为新的归并段,R1,，并将,R1,存储在,T2,中，此时,T4,为空，则第三步归并后的情况如图,13.13,所示。,13.4,小结,本章主要介绍了数据结构中另一种排序外排序。,在对大量的数据记录进行排序时，需要进行外排序。外排序通过将待排序的记录选择一部分调入内存，在内存中对这一部分数据记录排序，然后将排序结果存储在外存中。通过以上反复地在内存和外存进行调换和排序的过程称为外排序。,外排序的主要方法是归并排序。在外排序中，归并排序可分为两个阶段进行：（,1,）第一阶段：将待排序的,n,个记录文件按照内存缓冲区的大小，分割为长度为,m,的若干个子文件，将这些子文件分批地不断调入内存，进行归并排序，生成有序的若干个子文件，并放在外存。将这些有序的子文件称为归并段。（,2,）第二阶段：对已经有序的归并段继续不断在内存和外存互换，从而进行归并排序，直到待排序文件构成一个有序的序列。,13.4,小结,本章首先介绍了外存的一些特性，磁带和磁盘是外存常用的存储设备。磁带是一种顺序存取的设备，而磁盘是一种随机存取的设备。磁盘排序过程中，为了减少时间的耗费，介绍了胜方树，通过胜方树可以减少每趟过程中排序的次数，但是在最小关键字输出后，仍然需要和兄弟结点进行比较。因此，在这种情况下，引入了败方树，败方树与胜方树相反，从叶子结点出发，将关键字最大者存储在双亲结点中，而关键字较小者继续比较。通过败方树，可以减少兄弟结点之间的比较。,磁带排序与磁盘排序类似，最为常用的方法是非平衡多路归并排序。非平衡多路归并排序是为了减少磁带机的使用，并能减少排序过程中的扫描次数。其主要做法是，不同的磁带机上输入的归并段个数不同，通过对归并段的非均匀分配，从而减少磁盘机的使用。每一趟归并，只是部分的记录参加归并，在每一趟归并完成之后，存放记录最少的磁带机变成空带，将作为下一趟的输出使用。,