当前位置：文档之家 › 第11章外部排序PPT课件

第11章外部排序PPT课件

  • 格式：pptx
  • 大小：514.58 KB
  • 文档页数：14

下载文档原格式

  / 14

合集下载

第十七讲-外部排序

第十七讲-外部排序

磁盘文件的归并排序
个缓冲区。 若把内存区域等份地分为 ３个缓冲区。其中的两个为输缓 冲区，一个为输出缓冲区， 冲区，一个为输出缓冲区，可以在内存中利用简单 ２归并 路归并。 函数 ｍｅｒｇｅ（ ）实现 ２路归并。 首先， 首先，从参加归并排序的两个输入归并段 Ｒ１和 Ｒ２中分 别读入一块，放在输入缓冲区１和输入缓冲区２ 别读入一块，放在输入缓冲区１和输入缓冲区２中。然后 路归并， 在存中进行 ２路归并，归并结果顺序存放到输出缓冲区中 。 当输出缓冲区装满2５０个记录时，就输出到磁盘。 当输出缓冲区装满 ５０个记录时，就输出到磁盘。 ５０个记录时 如果归并期间某个输入缓冲区空了， 如果归并期间某个输入缓冲区空了，就立即向该缓冲区继 续装入所对应归并段的一块记录信息， 续装入所对应归并段的一块记录信息，使之于另一个输入 缓区的剩余记录归并，直到Ｒ 归并为Ｒ１２、Ｒ 缓区的剩余记录归并，直到Ｒ１和Ｒ２归并为Ｒ１２、Ｒ 归并Ｒ３４、Ｒ 、Ｒ５ 归并为Ｒ５６为止 为止。 ３和Ｒ４归并Ｒ３４、Ｒ５和Ｒ６归并为Ｒ５６为止。 再把Ｒ１２和 ３４归并为Ｒ１２３４，最后把Ｒ 再把Ｒ１２和Ｒ３４归并为Ｒ１２３４，最后把Ｒ１２３ 归并为 ５６归并为 １２３４５６。 归并为Ｒ ４和Ｒ５６归并为Ｒ１２３４５６。
K 路平衡归并与败者树
选择树 或 败者树 分析： 分析： 第一次建立选择树的比较所花时间为: 第一次建立选择树的比较所花时间为 O( K-1 ) = O ( K) 而后每次重新建造选择树所需时间为： 而后每次重新建造选择树所需时间为： O( log2K) n 个记录处理时间为初始建立选择树的 次重建选择树的时间： 时间加上 n-1 次重建选择树的时间： O((n-1) log2K)+O(K) = O ( n log2K ) 这就是k路归并一遍所需的 这就是 路归并一遍所需的CPU处理时间 路归并一遍所需的 处理时间 。归并遍数为 logkm，总时间为： ，总时间为： O(n log2K logKm) = O(n log2m) K 路归并 CPU 时间与 K 无关，选择树很好 无关，

外排序

外排序

外排所需总的时间为： 外排所需总的时间为：
m*tIS + d*tIO + S*u*tmg = 10*tIS + 500*tIO + 4*10000*tmg
示例： 示例：
• 设有一个包含4500个对象的输入文件。现 设有一个包含4500个对象的输入文件。 个对象的输入文件 用一台其内存至多可容纳750个对象 内存至多可容纳 个对象的计 用一台其内存至多可容纳750个对象的计 算机对该文件进行排序。输入文件放在磁 算机对该文件进行排序。 盘上，磁盘每个页块可容纳250个对象 每个页块可容纳 个对象， 盘上，磁盘每个页块可容纳250个对象， 250＝ 这样全部对象可存储在 4500 / 250＝18 个 页块中。输出文件也放在磁盘上，用以存 页块中。输出文件也放在磁盘上， 放归并结果。 放归并结果。
一、外排序的基本过程
• 当对象以文件形式存放于磁盘上的时候，通常 当对象以文件形式存放于磁盘上的时候， 是按物理块存储的。 是按物理块存储的。 • 物理块也叫做页块，是磁盘存取的基本单位。 物理块也叫做页块，是磁盘存取的基本单位。
• 每个页块可以存放几个对象。操作系统按 每个页块可以存放几个对象。 页块对磁盘上的信息进行读写。 页块对磁盘上的信息进行读写。 • 本节所指的磁盘是由若干片磁盘组成的磁 盘组， 盘组，各个盘片安装在同一主轴上高速旋 转。各个盘面上半径相同的磁道构成了柱 各盘面设置一个读写磁头， 面。各盘面设置一个读写磁头，它们装在 同一动臂上， 同一动臂上，可以径向从一个柱面移到另 一个柱面上。 一个柱面上。
硬盘简介 磁盘的主要技术指标 柱面：多个盘片的同一磁道。 柱面：多个盘片的同一磁道。 目前常见的硬盘容量有 6.2GB、10GB、20GB、 、 、 、 40GB、60GB、80GB等等。 、 等等。 、 等等

数据结构-C语言描述(第二版)课件：外部排序

数据结构-C语言描述(第二版)课件：外部排序

外部排序
磁盘的存取时间主要取决于寻查时间和等待时间。 磁 盘以2400～3600 r/min的速度旋转，因此平均等待时间约为 10 ms～20 ms， 而平均寻查时间约为几毫秒至几十毫秒，这 与CPU的处理速度相比较而言，仍是很慢的。因此，在讨论 外存的数据结构及其上的操作时，要尽量设法减少访问外存 的次数， 以提高磁盘存取效率。
第四步：把T1上的顺串1和T3上的顺串3合并，并把结 果放到T2
外部排序
上述例子采用的是2路归并法，与磁盘排序的情况一样， 排序的时间主要取决于对数据的扫描遍数。采用多路归并 能减少扫描的遍数，但对磁带排序来说，多路归并需要多 台磁带机，为了避免过多的磁带寻找时间，要归并的顺串 需要放在不同的磁带上。因此，k路归并至少需要k+1台磁 带机，其中k台作为输入带，另外一台用于归并后存放输出 结果。但这样需要对输出带再作一遍扫描，把输出带上的 各顺串重新分配到k台磁带上，以便作为下一级归并 使用。若使用2k台磁带机，则可避免这种再分配扫描，把k 台作为输入带，其余k台作为输出带，在下一级归并时，输 入带与输出带的作用互相对换。上述例子就是用4台磁带机 实现2路归并，T1、T2和T3、T4轮流地用作输入带和输出带。
外部排序 图10.2 活动臂示意图
外部排序
活动臂磁盘的磁头是安装在一个可活动臂上，随着活动 臂的移动， 磁头可在盘面上做同步的径向移动，从一个磁道 移到另一个磁道， 当盘面高速旋转，磁道在读／写头下通过 时，便可进行信息的读写。各记录盘面上半径相同的磁道合 在一起称为一个柱面， 柱面上各磁道在同一磁头位置下，即 活动臂移动时，实际上是把这些磁头从一个柱面移到另一个 柱面。 一个磁道内还可以分为若干段，称为扇段。因此，对 磁盘存储来说，由大到小的存储单位是： 盘片组，柱面，磁 道，扇段。以IBM2314型磁盘为例，其参数为：20个记录面 ／磁盘组，200个磁道／记录面，7294字节／磁道。因此， 整个盘片组的容量为： 7294×200×200≈29 MB。

第11章 外部排序

第11章 外部排序
• 改进：采用胜者树或者败者树，从 K 个元素中挑选 一个最小的元素仅需 log2k 次比较，这时总的时间耗 费将下降为： log2m × ( n - 1 ) × tmg
多路平衡归并的实现
二、胜者树及其使用 4路平衡归并
1 5
2 5
1234567 5 5 9 5 7 29 9
3 9
4
5
6
7
5
7
29
91
71
59
区
输
5
出
7
缓
冲
区
多路平衡归并的实现
二、胜者树及其使用 4路平衡归并
1
9
123
9 12 9
2
3
12
9
4567 16 12 29 9
4
5
6
7
16
12
29
9
输
5
7
29
9
入
16
12
38
22
缓
49
25
57
47
52
84
66
48
冲
78
91
71
59
区
输
5
出
7
缓
9
冲
区
多路平衡归并的实现
•采用胜者树，从 K 个元素中挑选一个最小的元素仅需 log2m × ( n - 1 ) × tmg 即内部归并时间与k无关, K 增大，归并趟数logkm减少 ，读写外存次数减少，外排总时间减少。
b[0]
b[1] b[2]
b[3]
5
7
29
9
输
5
7
29
9
入

数据结构排序PPT课件

数据结构排序PPT课件
—— 若待排序记录一部分在内存，一部分在外存， 则称为外部排序。
注：外部排序时，要将数据分批调入内存来 排序，中间结果还要及时放入外存，显然外 部排序要复杂得多。
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
5.待排序记录在内存中怎样存储和处理？
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
Void BInsertSort (SqList &L) // 折半插入排序
{ for ( i=2；i<=L.length；++i )
{ L.r[0] = L.r[ i ]； // 将L.r [i] 暂存到L.r[0]
处理方式： ① 顺序排序 —— 数据间的逻辑顺序关系通过其物理
存储位置的相邻来体现，排序时直接移动记录； 适合数据较少的情况！
② 链表排序 ——数据间的逻辑顺序关系通过结点中 的指针体现，排序时只修改指针，不移动数据；
③ 地址排序 —— 数据存储在一段连续地址的空间， 构造一个辅助表保持各数据的存放地址（指针），排 序时先修改辅助表中的地址，最后再移动记录。
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
4. 什么叫内部排序？什么叫外部排序？ —— 若待排序记录都在内存中，称为内部排序；
内部排序基本操作有两种： ◆ 比较两个关键字的大小；(比不可少的操作) ◆ 存储位置的移动。
i=8
0
1
2
3
4

第11章外部排序

第11章外部排序

外部排序
将两个有序段归并成一个有序段的过程， 将两个有序段归并成一个有序段的过程，若 在内存进行，则很简单，上一章中的merge 在内存进行 ， 则很简单 ， 上一章中的 过程便可实现此归并。 过程便可实现此归并。 由于我们不可能将两个有序段及归并结果段 同时存放在内存中， 同时存放在内存中，在外部排序中实现两两 归并时，不仅要调用merge过程， 而且要进 过程， 归并时 ， 不仅要调用 过程 行外存的读/写 行外存的读 写。
11.2 外部排序的方法
外部排序指的是大文件的排序， 外部排序指的是大文件的排序，即待排序的 记录存储在外存储器上， 记录存储在外存储器上，待排序的文件无法 一次装入内存， 一次装入内存，需要在内存和外部存储器之 间进行多次数据交换， 间进行多次数据交换，以达到排序整个文件 的目的。 的目的。 外部排序最常用的是多路归并排序， 外部排序最常用的是多路归并排序，即将原 文件分解成多个能够一次性装人内存的部分， 文件分解成多个能够一次性装人内存的部分， 分别把每一部分调入内存完成排序。然后， 分别把每一部分调入内存完成排序。然后， 对已经排序的子文件进行归并排序。 对已经排序的子文件进行归并排序。
按字符组(记录 存放 按字符组 记录)存放。 记录 存放。 磁带上相邻两组字符组之间要留一空白区， 磁带上相邻两组字符组之间要留一空白区， 叫做间隙IRG(Inter Record Gap)。通常为 叫做间隙 。 1/4~3/4英寸。 英寸。 英寸 组成块可减少IRG数目，可减少 操作。 数目， 操作。 组成块可减少 数目 可减少I/O操作
分析d和 归并过程”的关系： 分析 和“归并过程”的关系： 若对10个初始归并段进行 路平衡归并， 个初始归并段进行5-路平衡归并 若对 个初始归并段进行 路平衡归并，即 每一趟将5个或 个或5个以下的有序子文件归并成 每一趟将 个或 个以下的有序子文件归并成 一个有序子文件，仅需进行二趟归并， 一个有序子文件，仅需进行二趟归并，外排 时总的读/写次数便减至 写次数便减至2*100+100=300， 时总的读 写次数便减至 路归并减少了200次的读 写。 次的读/写 比2-路归并减少了 路归并减少了 次的读

第十一章 外部排序

第十一章 外部排序
.
2
b1 9 9 18 20 . b2 20
3 4
b4 12 12 37 48 .
10
10 15 16 .
20 22 40 .ຫໍສະໝຸດ §11.4 置换-选择排序
• 问题: 是否可以不用内部排序构造初始归并段? • 例:若初始文件含有24个记录，其的关键字为: 51，49，39，46，38，29，14，61，15，1，48，52， 3，63，27，4，1389，24，46，58，33，76。 假设内存工作区可容纳6个记录，则可得如下4个初始 归并段： • RUN1：29，38，39，46，49，51 • RUN2：1，14，15，30，48，61 • RUN3：3，4，13，27，52，63 • RUN4：24，33，46，58，76，89
§11.3 多路平衡归并的实现
• 例:
3 1
胜利者
失败者
0
b0 b3 6 6 15 25
.
2
b1 9 9 18 20 . b2 20
4
b4 12 12 37 48 .
10
10 15 16 .
20 22 40 .
§11.3 多路平衡归并的实现
• 例:
1 3 0 1
胜利者
失败者
4 0
b0 b3 15 15 25
15,30,1,48,52,3,63,27,4,… 30,1,48,52,3,63,27,4,…
30,1,48,52,3,63,27,4,… 1,48,52,3,63,27,4,… 48,52,3,63,27,4,… 52,3,63,27,4,…
FO
29,38,39,46,49,51,61
WA
48,1,15,30,52,14 3,63,27,4,…

外部排序---数据结构

外部排序---数据结构


将b[ls[0]]写至输出归并段 补充记录(某归并段变空时,补)，调整败者树
算法描述：建立败者树
void CreateLoserTree() { b[k] = MINKEY; for (i = 0; i < k; i++) ls[i] = k; for (i = k - 1; i >= 0; i++) Adjust(i); } void Adjust(int s) { for (t = (s + k) / 2; t > 0; t /= 2) { if (b[s] > b[ls[t]]) s ls[t]; } ls[0] = s; }
外部排序的方法

由两个独立的阶段组成

将外存含n个记录的文件分成若干长度为l的子文件或段， 依次读入内存并用内部排序方法排序，将排序后的有 序子文件重新写入外存，称为归并段或顺串 对这些归并段进行逐趟归并，（有序子文件）由小变 大，直到获得整个有序文件

外排序基本方法：归并排序
[步骤] 生成若干初始归并串/顺串(文件预处理) 把含有n个记录的文件，按内存缓冲区大小分成若干长度为L 的子文件（段）； 分别调入内存用有效的内排序方法排序后送回外存； 多路合并
外排序基本方法：归并排序

外存上的信息的读/写以“物理块”为单位，假设 每个物理块可容纳200个记录，则每一趟归并所 需进行50次“读”和50次“写”，4趟归并并加 上内部排序所需进行的读写使得外排序总共需进 行500读/写
外排序基本方法：归并排序

外部排序所需的总的时间= 内部排序所需的时间（m*tis） + 外存信息读写的时间（d*tio） + 内部归并所需的时间（s*utmg） tis:：得到一个厨师归并段进行内部排序所需时间 tio：进行一次外存读/写所需时间 utmg：对u个记录进行内部归并所需的时间 m：经过内部排序后得到初始归并段的个数 s：为归并的趟数 d：为总的读/写次数

十章节外部排序

十章节外部排序

提高外排序效率的途径
扩大初始归并段长度，从而减少初始归并段个数m 进行多路(k路)归并
减少合并趟数s，以减少I/O次数
s = logkm
多路归并
多路平衡归并
[通过简单比较进行K路归并存在的问题] 设记录总数为n，初始归并段的个数为m，
从k个记录中选择一个关键字最小的记录时的比较次数为c 则s趟内部归并总的比较次数为：
设有9个初始归并段，记录个数(长度)分别为：
9，30，12，18，3，17，2，6，24
方 案 一
121
3-路归并 121
方
51
38
32
30 32
59
案 二
9 30 12 18 3 17 2 6 24
11 9 12 17 18 24
2 36
(9+30+12+18+3+17+2+6+24)2 [(2+3+6) 3+(9+12+17
调整败者树的方法
以在b[4]补充15为例
54
25 2与5比较
24 4与2比较
0
1
3 4与3比较 6
90
0
10 9 20 165 8 12
1
2
34
5
6
ห้องสมุดไป่ตู้
调整败者树的方法: 将新补充的结点与其双亲结点比较, 败者留在该双亲结点,胜者继续向上直至树根的双亲
建败者树的过程
调初调整始 整bb化[[5432106败]] 者树
54,43,29,…
21,23,33,36,62
16,7,54,87
43,29,…
21,23,33,36,62,87

数据结构11-外部排序

数据结构11-外部排序

例： 5 - 路平衡归
并的败者树：
[0] 531 [1] 510
[2] 5304
[3] 52
[4] 543
b0 12 b1 1805 b2 30
b3 b4 253 16
12 1805 30 14 12059 38
253 16 17 128598 56
b5
2334
0 3448
28 31
初始归并段
5
8 10 …
磁盘是在一片塑料薄膜上涂有磁性材料用以记 录数据的存储介质。它分成多个磁道（柱面），每 个磁道又分为多个扇区，多个磁盘组成的磁盘组还 涉及到盘片号（磁头号），磁盘绕轴高速旋转，读 写头则沿其一条半径作直线运动以寻道。它也不是
连续运转的设备，读写信息只能在旋转稳定时进行， 且找到要读写的记录也需要一定的寻道、寻扇区时 间，因此，在磁盘上读写信息所需的时间由三部分 组成：TI/O = tseek + tla + n tw，其中 tseek 为寻道时间 （seek time）， tla 为寻扇区时间（latency time time）， tw 为传输时间（transmission time）。磁盘 是一种随机存储设备。
§11.6 最佳归并树
用置换-选择排序得到的初始归并段长度各不相 同，那应如何进行 k 路平衡归并呢？这实际上是建立 k 叉霍夫曼树的问题：当初始归并段总数不足（ ( m 1 ) MOD ( k - 1 ) ≠ 0 ）时，需附加 k - ( m - 1 ) MOD ( k - 1 ) -1 个长度为零的虚段，亦即第一次归并时只 对 ( m - 1 ) MOD ( k - 1 ) + 1 个初始归并段归并。建 立 k 叉霍夫曼树每次仍是选择记录数相对少的初始归 并段先进行归并。最佳归并树不适合磁带归并排序。

排序算法精讲PPT课件

排序算法精讲PPT课件
if (L.r[j].key > L.r[j+1].key ) {
for(j = i - 2; L.r[0].key < L.r[j].key]; j--)
L.r[0] = L.r[j]; L.r[j] = L.r[j+1];
L.r[j+1] = L.r[j];
L.r[j+1] = L.r[0]; exchanged =TRUE;
有序序列R[1..i-1]
第i趟 简单选择排序
无序序列 R[i..n] 从中选出关键字最小的记录
有序序列R[1..i]
无序序列 R[i+1..n]
简单选择排序算法
❖ 以顺序表作为存储结构的简单选择排序算法
void SelectSort(SqList &L) {//对顺序表作简单选择排序
ffoorr((ii==11;;ii<<LL..elnenggthth; ;i+i+++) ){{
数据结构定义
#define MAXSIZE 100
typedef int Keytype;
// 定义关键字类型为整型
typedef char InfoType[100];
typedef struct { KeyType key; InfoType otherinfo;
}RedType;
// 关键字项 // 其他数据项 // 记录类型
typedef struct { RedType r[MAXSIZE+1]; int length;
}SqList;
// r[0]闲置或用作哨兵 // 顺序表长度 // 顺序表类型
直接插入排序
直接插入排序(Straight Insertion Sorting)的基本思想 是：n个待排序的元素由一个有序表和一个无序表组成， 开始时有序表中只包含一个元素。排序过程中，每次从 无序表中取出第一个元素，将其插入到有序表中的适当 位置，使有序表的长度不断加长，完成排序过程。

数据结构(十)外部排序

数据结构(十)外部排序
13 11 8
12
6 12 7 14
7
15 13
26
8 24 11
问题：当一个三角形塔给出后，找出一条从根到底层的路径， 使路径上的值最大。
分析： （1）贪心法往往得不到最优解
13
11
12 6 12 7 14 13 7
8
26 15 24 8 11
分析： （1）贪心法往往得不到最优解
13
11
12 6 12 7 14 13 7
如果问题的所有可能答案，都可以在多项式时间内进行正确 与否的验算的话，就叫完全多项式非确定问题。完全多项式非 确定性问题可以用穷举法得到答案，一个个检验下去，最终便 能得到结果。但是这样算法的复杂程度，常常是指数关系，因 此计算的时间随问题的复杂程度成指数的增长，很快便变得不
可计算了。
有大量问题具有以下特性：知道有效的非确定性算法， 但是不知道是否存在有效的确定性算法，同时，不能证明 这些问题中的任何一个不存在有效的确定性算法。这类问 题称为NP完全问题。
本课程许多算法都是多项式时间，即对规模为n 的输入，算法在最坏情况下的计算时间是O(nk),k是 常数。
一个问题称为是P的，如果它可以通过运行多项式 次(即运行时间至多是输入量大小的多项式函数的一种 算法获得解决）。----确定性问题
并不是所有问题都在多项式时间内可解的。在可计算 性理论中，著名的“图灵停机问题”，任何计算机不论 耗费多少时间也不可能解决该问题。 有写问题，虽然可以用计算机求解，但是对于任意常 数k，它们不能在O(nk)时间内得到解答。 ————非确定性问题
void output(St g[][NUM],int n) { int i,j; int mm=0; for(i=0;i<NUM;i++) { for(j=0;j<=i;j++) cout<<setw(3)<<g[i][j].val<<' '; cout<<endl;} cout<<g[0][0].val; j=0; for(i=0;i<n-1;i++) { j+=g[i][j].de; mm+=g[i+1][j].val; cout<<"->"<<g[i+1][j].val; } cout<<':'<<mm<<endl; }

第十一章 外部排序PPT资料26页

第十一章 外部排序PPT资料26页
▪ ta 延迟时间：读写头到达相应的物理块的起始 位置的时间；
▪ tw 读/写一个字符的时间；
▪ n 字符数。
由于磁带是顺序存取设备，在读一个记录时，必 须先顺序检索，直到所需信息通过读写头时才能 得到。因此检索速度很慢。
磁带主要用于处理变化少、只进行顺序存取的大 量数据。
磁盘（disc）
▪ 磁盘存储器通常称为直接存取设备，或随机存 取设备，它访问外存上文件的任一记录的时间 几乎相同。
假设“数据块”的大小为200，即每一次访问外存可 以读/写200个记录。 则对于10,000个记录，处理一遍需访问外存100次(读 和写各50次)。 1)求得10个初始归并段需访问外存100次; 2)每进行一趟归并需访问外存100次; 3)总计访问外存 100 + 4 100 = 500次
▪外排总的时间还应包括内部排序所需时间和逐趟归 并时进行内部归并的时间
外部排序总时间=产生初始归并段的时间 m*tIS +外存信息读写时间 d*tIO +内部归并所需时间 s*utmg
R1’
R2’
R3’
R4’
R5’
R1’’
R2’’
R3’’
R1’’’
R3’’’
有序文件
假设进行2路归并(即两两归并)，则：
➢第一趟由10个归并段得到5个归并段; ➢第二趟由 5 个归并段得到3个归并段; ➢第三趟由 3 个归并段得到2个归并段; ➢最后一趟归并得到整个记录的有序序列。
▪分析上述外排过程中访问外存(对外存进行读/写)的次数：
▪ 任一时刻，所有记录盘面的读写磁头停留在各 个记录盘面的半径相同的磁道上。运行时，由 于盘面做高速旋转，磁头所在的磁道上的数据 相继在磁头下，从而可以读写数据。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第11章外部排序
11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换-选择排序 11.5 最佳归并树
11.1 外存信息的存取
• 两种存储器:内存储器(主存)和外存储器(辅 存)。内存的信息可随机存取,且存取速度快, 但价格贵(?),容量小(?). 外存储器包括磁带和 磁盘(或磁鼓)．前者为顺序存取的设备,后者 为随机存取的设备.
• 外部排序:待排序记录的数量很大,以致内存一 次不能存纳全部记录,在排序过程中尚需对外 存进行访问的排序过程.
一．磁带信息的存取
• 磁带大多数有0.5英寸宽(1.27cm)，最长可达3600英 尺(1097.56m).
两种基本操作
• 在0.5寸,记录9位或7位二进制(称为9道或7道带， 9 轨或7轨带)。
后的文件。
11.3 多路平衡归并的实现
11.4 置换-选择排序
• 在整个排序(得到所有初始归并段)的过程中， 选择最小(或最大)关键字和输入、输出交叉 或平行进行(边输入输出,边选择最小关键字)。
• 假设初始待排文件为输入文件F真，初始归 并段文件为输出文件FO，内存工作区勾wA， FO和wA的初始状它为空，井设内存工作wA 区的容量可容纳钟个记录．则置换-选择排序 的操作过程为：
二．磁盘信息的存取
• 磁盘是一种直接存取的存储设备； • 它特征是存取时间变化； • 可以直接存取任何字符组； • 容量大、速度快，存取速度比磁带快得多； • 磁盘是一个扁平的圆盘(与电唱机的唱片类似)，盘
面上有许多饰为磁道的圆圈；
• 信息记载在磁道上。由于磁道的圆圈为许多同心 圆．所以可以直接存取。磁盘可以是单片的．也可 以由若干盘片组成盎组。每一片上有两个面。以6 片盘组为例．由于最顶上和最低下盘片的外侧面不 存信息．所以总共只有10个面可用来保存信
• 9道带每一横排就可表示一个字符(8位表示一个字符， 另一位作奇偶校验位)。
• 磁带上可记下各种文字信息或二进制信息，在磁带 上信息按字符组存放，而不是按字符存放，磁带上 信息的密度通常为每英寸800位或1600位或6250位 (即每英寸的二进制字符数)，移动速度是每秒200英 寸。
• 间隙IRG：磁带上相邻两组字符组(记录)之间空白 区。
置换-选择排序过程
(1)从FI输入w个记录到工作区WA。 (2)从WA中选出其中关键字取最小值的记录，记为MlNIMAX
记录 (3)将MINlMAX记录输出到FO中云。 (4)若FI不空，则从FI输入下一个记录到WA中。 (5)从WA中所有关键字比MINIMAX记录的关键字大的记录中
选出最小关键字记录，作为新的MINIMAX记录。 (6)重复(3)-(5)，直至在WA中选不出新的M1N]MAK记录为止，
由此得到一个初始归并段，输出一个归并段的结束标志到 FO中去。 (7)重复(2)-(6)．直至WA为空。由此得到全部初始归并段.
课件下载后可自由编辑，如有不理解 之处可根据本节内容进行提问
Thank you for coming and listening,you can ask questions according to this section and this courseware can be downloaded and edited freely
硬盘（磁盘）阵列
• 多个硬盘构成阵列； • 有一个管理程序，可以把阵列中的硬盘看成
一个硬盘，这样，可以拥有容量非常的大的 • 单个虚拟硬盘；保存文件可以在这个虚拟的
硬盘上进行，文件分布在不同的硬盘上。 • 阵列中如果一个硬盘有损坏，则影响整个虚
拟硬盘上的文件。
Hale Waihona Puke 11.2 外部排序的方法• 内存中排序，外部输出归并段（子文件）。 • 把归并段进行归并（重新合成），形成排序