厦门大学：《数据结构》课程教学课件（PPT讲稿）第十一章 外部排序

Algorithms and DataStructures:EXSORT 目录 第11章外部排序 1、外存信息的存取 2、外部排序的方法 3、多路平衡归并的实现 4、置换-选择排序 5、最佳归并树 EXST

1 物料管理 EXST 1 Algorithms and DataStructures:EXSORT 1、外存信息的存取 2、外部排序的方法 3、多路平衡归并的实现 4、置换-选择排序 5、最佳归并树 目录 第 11 章 外部排序

Algorithms and DataStructures:EXSORT 1、外存信息的存取 1、外部排序： 内部排序：信息一次可全部调入内存，信息在内存中的处理时间是主要的时间耗费。 外部排序：信息量巨大，无法一次调入内存。只能驻留在带、盘、CD-ROM上。特点 为内存运行时间短，内、外存进行交换需要时间长。减少O时间成为主 要矛盾。 2、基本术语： ·记录(Record):数据项的集合存于内存，称之为结点。如果存之于外存，则叫做记 录。原因起源于是在历史上研究管理应用和计算机科学的两部分人 员的习惯。 ·域（场）：记录中的每个数据项，称之为域(Field)。 ·文件：记录的集合。 ·关键字：唯一标识记录的域，称之为关键字。 ·有序文件：文件根据关键字的大小。排成递增或递减的序列。 3、常用外存： ·磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度幔。 2 EXST

2 物料管理 EXST 2 Algorithms and DataStructures:EXSORT 1、外存信息的存取 1、外部排序： 内部排序：信息一次可全部调入内存，信息在内存中的处理时间是主要的时间耗费。 外部排序：信息量巨大，无法一次调入内存。只能驻留在带、盘、CD-ROM 上。特点 为内存运行时间短，内、外存进行交换需要时间长。减少 I/O 时间成为主 要矛盾。 • 记录（Record）：数据项的集合存于内存，称之为结点。如果存之于外存，则叫做记 录。原因起源于是在历史上研究管理应用和计算机科学的两部分人 员的习惯。 • 域（场）：记录中的每个数据项，称之为域（Field） 。 • 文件：记录的集合。 • 关键字：唯一标识记录的域，称之为关键字。 • 有序文件：文件根据关键字的大小。排成递增或递减的序列。 2、基本术语： 3、常用外存： • 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度幔

Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： ·磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度慢。 ·带信息的表示： 一种磁化方向、代表1 ↓另一种磁化方向，代表0 N 01001001 10101111 EXST

3 物料管理 EXST 3 Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： • 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度慢。 • 带信息的表示： 一种磁化方向、代表1 另一种磁化方向，代表0 01001001 10101111

Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： ·磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度慢（尤其是查找末端记录时）。 磁带机走向 原 出头 入头 接收盘 ·带文件的组织： 记录1 记录2 记录3 IRG(Inter Record Gap)记录间隙 EXST

4 物料管理 EXST 4 Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： • 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度慢（尤其是查找末端记录时）。 . . 磁带机走向 读 出 头 写 入 原 头 始 盘 接 收 盘 • 带文件的组织： 记录 1 记录 2 记录 3 IRG（Inter Record Gap）记录间隙

Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： 读写头 ·带文件的组织： 记录1 记录2 记录3 可靠读写区 IRG(Inter Record Gap)记录间隙 IRG:.5~.75inch,带来的问题是什么？ 带的利用率下降，如： 密度800 byte per inch的带。设每个记录有80byte ,共1000个记录。如果，RG=.6inch;带的利用率？ 1000×(80/800)=100inch(filel) 1000 X 0.6 600 inch total IRG) 利用率=17=14%必须改进带的利用率！ ·带文件的读写时间：To=ta+nXtw ta延迟时间：读写头到达相应的物理块的起始位置的时间。 tw读/写一个字符的时间；n记录数。 EXST

5 物料管理 EXST 5 Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： • 带文件的组织： 记录 1 记录 2 记录 3 IRG（Inter Record Gap）记录间隙 v t 可靠读写区 IRG：.5~.75 inch，带来的问题是什么？ 带的利用率下降，如： 密度 800 byte per inch 的带。设每个记录有 80 byte ，共 1000 个记录。如果， IRG＝ .6 inch ; 带的利用率？ 1000 × (80/800) ＝ 100 inch ( filel ) 1000 × 0.6 ＝ 600 inch ( total IRG) 利用率＝ 1/7= 14 % 必须改进带的利用率 ! • 带文件的读写时间：T i/o = ta + n×tw ta 延迟时间：读写头到达相应的物理块的起始位置的时间。 tw 读/写一个字符的时间； n 记录数。 读写头

Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： ·带文件的组织的改进： 块 块2 块3 IBG(Inter Block Gap)块间间隙 IBG:.5~.75inch,带来的好处是什么？ 每一块是一个物理记录，包含若干个逻辑记录。 B.F(块因子)=一个物理记录包含逻辑记录的个数 带的利用率上升，如上例： 设B.F=100 1000/100 X 0.6 6 inch total IBG 1000×80/800=100inch(file)利用率=100/106=94.3% EXST

6 物料管理 EXST 6 Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： • 带文件的组织的改进： 块 1 块 2 块 3 IBG（Inter Block Gap）块间间隙 IBG：.5~.75 inch，带来的好处是什么？ 每一块是一个物理记录，包含若干个逻辑记录。 B.F（块因子） ＝ 一个物理记录包含逻辑记录的个数 带的利用率上升，如上例： 设 B.F = 100 1000 /100 × 0.6 ＝ 6 inch ( total IBG ) 1000 × 80/800 ＝ 100 inch ( file) 利用率＝ 100/106 = 94.3 %

Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： ·磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。 速度快、容量大、直接存取设备。 ·种类：固定头磁盘、活动头磁盘 固定头磁盘：每个磁道都有一个磁头（速度快) 活动头磁盘：每个盘面共用一个磁头， 增加了找道的时间，应用广泛。 ·柱面：各盘面的直径相同的磁道的总和。 ·物理位置：盘组号、若干个磁盘构成一组，系统可能有许 多组。 柱面号、 磁道号、 块（扇区号） ·盘文件的读写时间：Tlo=tseck+tia+n X twm tseck:找道时间 tia:等待时间 twm：传输时间/字符，n记录数。 EXST

7 物料管理 EXST 7 Algorithms and DataStructures:EXSORT 1、外存信息的存取 3、常用外存： • 磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。 速度快、容量大、直接存取设备。 • 种类：固定头磁盘、活动头磁盘 固定头磁盘：每个磁道都有一个磁头（速度快） 活动头磁盘：每个盘面共用一个磁头， 增加了找道的时间，应用广泛。 • 柱面：各盘面的直径相同的磁道的总和。 • 物理位置：盘组号、若干个磁盘构成一组，系统可能有许 多组。 柱面号、 磁道号、 块（扇区号） • 盘文件的读写时间：T i/o = tseck + tla + n×twm tseck ：找道时间 tla ：等待时间 twm ：传输时间/ 字符，n 记录数

Algorithms and DataStructures:EXSORT 2、外部排序的方法 1、步骤： ·生成合并段(un)：读入文件的部分记录到内存一>在内存中进行内部排序一> 将排好序的这些记录写入外存，形成合并段一>再读入该文件 的下面的记录，往复进行，直至文件中的记录全部形成合并段 为止。7、15、198、11、1316、23、315、12 ·外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文 件。 ·平衡合并分类法：被合并的初始合并段均匀分布在K条磁带上，即分布在T1、T2、 .Tk上。对这K条带进行合并，将生成的中间归并段分布在 TK+1小TK+2、.T2K上。然后，循环往复，直至最后形成一个 单一的合并段为止。 e.g:平衡2路归并，K=2.2K=4,需4条磁带。六个初始合并段均匀分布在T1、T2 上。每个合并段有1000个记录。T3、T4初始为空。合并过程如下： 初始分布：T1 R(1.1000) R(2001.2000) R(40015001 T2 R(1001.20000 R(3001.4000) R(5001.6000 T3:空 T4:空 EXST

8 物料管理 EXST 8 Algorithms and DataStructures:EXSORT 2、外部排序的方法 1、步骤： • 生成合并段（run）：读入文件的部分记录到内存 －> 在内存中进行内部排序 －> 将排好序的这些记录写入外存，形成合并段 －> 再读入该文件 的下面的记录，往复进行，直至文件中的记录全部形成合并段 为止。 • 外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文 件。 • 平衡合并分类法：被合并的初始合并段均匀分布在 K 条磁带上，即分布在 T1、T2、 . Tk 上。对这 K 条带进行合并，将生成的中间归并段分布在 TK+1、 TK+2 、. T2K 上。然后，循环往复，直至最后形成一个 单一的合并段为止。 e.g: 平衡 2 路归并， K ＝ 2。 2K = 4, 需 4条磁带。六个初始合并段均匀分布在 T1、T2 上。每个合并段有 1000 个记录。T3、T4 初始为空。合并过程如下： 初始分布： R（1. 1000） R（2001.2000） R（4001. 5001） R（1001. 2000） R（3001.4000） R（5001. 6000） T1 T2 T3 ：空 T4：空 7、15、19 8、11、13 16、23、31 5、12

Algorithms and DataStructures:EXSORT 2、外部排序的方法 初始分布： R(1.1000) R(2001.3000) R(4001.5000} T2 R(1001.2000 R(3001.4000) R(5001.6000 T3:空 T4:空 ·第一趟归并： T:空 T2:空 T3: R(1.2000) R(4001.6000) T4: R （2001.4000) 9 EXST

9 物料管理 EXST 9 Algorithms and DataStructures:EXSORT 2、外部排序的方法 • 初始分布： R（1. 1000） R（2001.3000） R（4001. 5000） R（1001. 2000） R（3001.4000） R（5001. 6000） T1 T2 T4：空 T3 ：空 • 第一趟归并： T1 ：空 T2 ：空 T3 ： T4： R（1. 2000） R（4001.6000） R（2001. 4000）

Algorithms and DataStructures:EXSORT 2、外部排序的方法 第二趟归并： T1: R(1.4000) T2 (4001.60000 T3:空 T4:空 ·第三趟归并： T1:空 T2:空 Tg: R(1.6000) T4:空 10 EXST

10 物料管理 EXST 10 Algorithms and DataStructures:EXSORT 2、外部排序的方法 • 第二趟归并： T3 ：空 T4 ：空 T1 ： T2： R（1. 4000） R（4001. 6000） • 第三趟归并： T3 ： T4 ：空 T1 ：空 T2：空 R（1. 6000）