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

1、第13章 外排序,外排序通常应用于数据量非常大的情况，在排序的过程中，待排序的数据不断地在内存与外存之间进行交换，将已经排序的放在外存，待排序的数据调入内存。比较常用的外排序方法是多路归并法，根据存储待排序文件的存储介质，可分为磁盘排序和磁带排序。本章的主要学习内容包括：外存的存取特性、磁盘排序和磁带排序。,13.1 外存的存取特性,计算机的存储器分为内存储器和外存储器，分别简称为内存和外存。 1磁盘信息的存取 磁盘是一种随机存取的设备，可以直接存取设备上的数据。磁盘由盘片、磁头、盘片主轴、磁头控制器等组成，其中，盘片是用于存储数据的。盘片被划分为多个同心圆，称为磁道，磁道由外向内从0开始顺序

2、编号，所有的数据信息被记录在磁道上。磁盘一般由多个盘片构成，每一个盘片包含两个面，其中，最上面和最下面的外侧的一面不存储信息。例如，一个磁盘由6个盘片组成，则有10个面可保存信息。,13.1 外存的存取特性,所有的盘面的同一磁道构成一个圆柱，称为柱面，位于同一柱面上的磁道由上往下从0开始编号。每个磁道还可以进行划分为若干个部分，被称为扇区，每个扇区的大小是512字节。扇区所在的磁道地址称为扇区号。 例如，某磁盘有10个有效记录面，记录面上有效记录区域的内径为20cm，外径是30cm，道密度为10道/mm，每个磁道有16个扇区，每个扇区记录512字节，则该磁盘的容量是：记录面数磁道数磁道扇区数扇

3、区的字节数=10(30-20)/2101016512=40960000字节39M字节。,13.1 外存的存取特性,要存取某一数据信息，首先需要找到数据所在的柱面，移动磁头到所在的柱面即磁道，然后移动磁头到具体的数据存放位置，因此，要存取磁盘上的数据信息所需要的时间由3个部分构成：寻道时间、等待时间和传输时间。其中，寻道时间tseek就是读写磁头寻找数据所在磁道并定位的时间，等待时间tw就是将磁头移动到数据信息所在的起始位置，传输时间trw就是读或写数据所需要的时间。读写数据的所用时间可表示为T=tseek+tw+trw。,13.1 外存的存取特性,磁带作为主要的存储介质，一般磁带长3600英尺

4、、宽0.5英寸。磁带可以分为7道带和9道带，7道带的磁带，每一排可以存储8位即一个字节，其中7位是数据位，1位奇偶校验位。通常情况下，磁带的存储密度是每英寸800位或1600位，磁带的移动磁头速度是每秒200英寸。 磁带是一种启停设备，当磁头正在读写磁带上的记录，如果要停止读写，必须经过一个减速的过程，然后才能停止。同样，从磁头静止，到开始读写数据时，磁头是经过一个加速旋转的过程，然后才能匀速的旋转达到稳定状态。因此，在磁带的每个相邻的记录之间，需要一个空白区域，这个空白区域就称为间隙。间隙的大小通常为0.25英寸-0.75英寸。磁带的存储结构如图13.1所示。,13.2 磁盘排序,12.2.

5、1 归并排序的基本方法 在外排序中，归并排序的基本思想方法可分为两步： （1）第一步：将待排序的n个记录文件按照内存缓冲区的大小，分割为长度为m的若干个子文件，将这些子文件分批地不断调入内存，进行归并排序，生成有序的若干个子文件，并放在外存。将这些有序的子文件称为归并段。 （2）第二步：对已经有序的归并段继续不断在内存和外存互换，从而进行归并排序，直到待排序文件构成一个有序的序列。,13.2 磁盘排序,按照以上方法归并R3和R4，得到有序的600条记录。然后分别对两个新生成的归并段继续归并，直到待排序文件中所有记录都已经有序，则该文件的1200条记录均为有序序列。整个归并排序的过程如图13.2

6、所示。,13.2 磁盘排序,因此，总的归并时间可计算如下：（1）读入1200条记录并进行归并，则需要的时间为12tio+4tis；（2）将两个归并段即R1和R2归并为R1，R3和R4归并为R2，则需要花费的时间为12tio+1200tm；（3）然后将R1和R2归并为R1的需要的时间为12tio+1200tm。总共需要的时间为36tio+4tis+2400tm。,13.2 磁盘排序,12.2.2 多路归并排序 多路归并可以有效的减少时间的开销。对于上面提到的2路归并，在初始时，如果归并段是m个，则将构成的归并树的层数是+1，需要进行趟归并才能完成排序。而对于k路归并，就是将k个归并段进行归并，则

7、将构成+1层的归并树，也就是需要进行趟的归并。例如，如果k=4，则16个归并段的归并过程如图13.3所示。,13.2 磁盘排序,选择树是一种完全二叉树，在该完全二叉树中，叶子结点存放各个归并段的当前待排序的元素，非叶子结点则表示对应孩子结点的最小的一个，从叶子结点开始，依次将当前互为兄弟结点中关键字最小的一个存入双亲结点，则根结点的关键字就是当前归并段中最小的一个关键字，即为将要输出的记录。一个8路归并排序的选择树如图13.4所示。,13.2 磁盘排序,从图13.4中可以看出，输出关键字最小的记录，只有刚建立胜方树的时候需要进行k-1次比较，即非叶子结点的个数次的比较。当一个关键字最小的记录输

8、出后，只需要进行-1次的比较，即只需要将上次最小关键字所在的那棵而叉树比较即可。 与胜方树相对应的还有一个称为败方树的二叉树。与胜方树相反，在败方树中，将兄弟结点中关键字较大的一个存入双亲结点中，而将较小的关键字继续进行比较，在根结点上附加一个结点，将最终的优胜者存放在其中。一个8路归并的败方树如图13.5所示。,13.2 磁盘排序,在败方树中，当输出当前归并段中最小的关键字的记录后，后面进行的比较次数减少了许多。只需要将归并段的下一个关键字key存入叶子结点，并将key与其双亲结点的关键字进行比较，将两者中较大的一个存入双亲结点，较小的一个继续与上一层的双亲结点进行比较。重复执行以上操作，直

9、到根结点。因此，当关键字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-D9

10、00第三块，记录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并存储

11、在磁带机T1上。 不难看出，磁带的归并排序与磁盘的归并排序的思想一样，其排序所用的时间也主要是在于对记录的扫描次数，归并过程中主要时间的耗费在寻找记录上，而为了避免这种耗费，可以采用多路归并，但是多路归并是以增加磁带机的数量为代价的。对于k路归并，需要k+1台磁带机，其中k台磁带机用于存放输入数据，剩下的1台用于存储输出数据。而如果这样做，在对输出的数据排序时，还需要进行扫描，因此，可以使用2k台磁带机来避免这种情况，其中，k台磁带机用于存储输入的数据，另外k台磁带机用于存储输出数据。在排序过程中，这些磁带机来回交换，就避免了对磁带记录的扫描。,13.3 磁带排序,12.3.2 多路非平衡归并

12、排序 非平衡归并排序是为了减少磁带机的使用，并能减少排序过程中的扫描次数。其主要做法是，不同的磁带机上输入的归并段个数不同，通过对归并段的非均匀分配，从而减少磁盘机的使用。 下面通过利用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

13、 磁带排序,第二步：将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 小结,本章主要介绍了数据结构中另一种排序外排序。 在对大量的数据记录进行排序时，需要进行外排序。外排序通过将待排序的记录选择一部分调入内存，在内存中对这一部分数据记录排序，然后将排序结果存储在外存中。通过

14、以上反复地在内存和外存进行调换和排序的过程称为外排序。 外排序的主要方法是归并排序。在外排序中，归并排序可分为两个阶段进行：（1）第一阶段：将待排序的n个记录文件按照内存缓冲区的大小，分割为长度为m的若干个子文件，将这些子文件分批地不断调入内存，进行归并排序，生成有序的若干个子文件，并放在外存。将这些有序的子文件称为归并段。（2）第二阶段：对已经有序的归并段继续不断在内存和外存互换，从而进行归并排序，直到待排序文件构成一个有序的序列。,13.4 小结,本章首先介绍了外存的一些特性，磁带和磁盘是外存常用的存储设备。磁带是一种顺序存取的设备，而磁盘是一种随机存取的设备。磁盘排序过程中，为了减少时间的耗费，介绍了胜方树，通过胜方树可以减少每趟过程中排序的次数，但是在最小关键字输出后，仍然需要和兄弟结点进行比较。因此，在这种情况下，引入了败方树，败方树与胜方树相反，从叶子结