数据结构-从概念到C++实现（第4版）课件 7-6外部排序

7-6外部排序v第七章排序技术学什么？外部排序的基本思想置换-选择排序败者树为什么外部排序需要新算法？外部排序需要着重考虑什么？基本思想外部排序的基本思想：采用多路归并排序，分为以下两个阶段：外部排序（externalsorting）：待排序的记录以文件的形式存储在外存上，在排序过程中需要在内存和外存之间进行多次数据交换预处理阶段：根据可用内存的大小，将原文件分解成多个能够一次性装入内存的子文件，分别对每一个子文件在内存中完成排序，得到若干个有序的子文件（称为归并段）；归并排序阶段：对归并段进行若干趟多路归并排序，直至将整个文件的记录排好序。为什么外部排序在归并排序阶段采用多路归并呢？R1R2R3R4R5R6R7R8R9R10R11R12归并段及归并结果不能同时存放在内存中，需要多次对外存进行读/写操作。基本思想R13R14R13R14R15R1R2R3R4R5R6R7R8R15多路归并可以减少归并排序的趟数对外存读/写操作的次数和归并排序的趟数成正比置换-选择排序假设待排序文件有

n个记录，内存缓冲区的容量是

k，每次将

k个记录读入内存进行排序，得到归并段的个数是多少？

如何增大归并段的记录个数呢？如何减少归并排序执行的趟数呢？采用多路归并

k-路归并排序

在k

个记录中取出最小值

败者树减少归并段的个数

增大归并段的记录个数增大k归并段的个数是n/k算法：置换-选择排序输入：待排序文件FI输出：归并段文件FO1.从文件FI中读取

w个记录到内存缓冲区buf；2.从buf中选取值最小的记录，记为

rmin；3.将

rmin输出到FO；4.若FI不空，则从FI中读取1个记录到buf中，转步骤5；否则，重复执行步骤2和步骤3，直至缓冲区buf为空，算法结束；5.从buf中所有比记录

rmin值大的记录中，选取值最小的记录，重新记为

rmin，转步骤3；6.如果buf中没有比记录

rmin值大的记录，则得到1个初始归并段，转步骤2构造下一个归并段；假设内存缓冲区buf可容纳

w个记录，假设每个物理块只能容纳1个记录置换-选择排序例1假设内存缓冲区buf可容纳4个记录，文件FI包含的记录为{10,20,12,18,6,25,5,22,15,30,28,10}，写出置换-选择排序的过程。归并段2615285归并段1内存缓冲区102012181528对于长度不等的初始归并段，不同的多路归并方案对排序性能有什么影响？620121810620251812186202552062225561525522615305256152853061528105152810615281028置换-选择排序最佳归并树例2置换-选择排序生成了9个初始归并段，长度分别为{9,30,12,18,3,17,2,6,24}，假设采用3-路归并排序。9301251183173826243212123611912321718245932121WPL=242WPL=223最佳归并树：带权路径长度最小的归并树。对于长度不等的初始归并段，不同的多路归并方案对排序性能有什么影响？方案1：方案2：最佳归并树需添加(k-1)-(n-1)mod(k-1)个虚段具有n个初始归并段，合并为k-路最佳归并树，需要填加多少个虚段？2311912321718245932121什么是虚段？长度为0的归并段败者树如何快速在多个记录中选取值最小的记录？顺序查找

k–1次比较败者树

O(log2k)败者树（treeofloser）：分支结点表示左、右孩子结点中的败者，让胜者去参加更高一层的比较。胜者树—