详情

1.外部排序的基本宗旨

外存中的数据读入内存→在内存中排序→数据写入外存

2.外部排序

2.1.外部排序的思惟

采选归比肩序的思惟和要领

1.数据运奇迹态

2.将（36、8、26）（42、9、48）分辩存入输入缓冲区1、输入缓冲区2

3.将输入缓冲区1和输入缓冲区2的数据进行递加排序

4.将输入缓冲区1和输入缓冲区2的数据通过输出缓冲区逐个写入外存，变成一个有序团结段

5.将（1、37、25）（45、27、28）分辩存入输入缓冲区1、输入缓冲区2

6.将输入缓冲区1和输入缓冲区2的数据进行递加排序

7.将输入缓冲区1和输入缓冲区2的数据通过输出缓冲区逐个写入外存，变成一个有序团结段

8.对剩余12块内存挨次进行上述操作，悉数需要进行16次读操作和16次写操作，取得运行团结段

9.第一次团结：读入团结段1和团结段2中的第一块磁盘（相对最小），进行排序

10.挨次找出这两个输入缓冲区中最元素，并将其挪动到输出缓冲区中，当输出缓冲区满，则写入外存（1、8、9）

11.不息找出这剩余元素中的最小元素，直到某一个缓冲区中空，则读入其所属团结段的后一个内存块的数据，并不息进行上述操作。直到两个缓冲区都空，且团结段1和团结段2中的元素扫数读入内存，此时团结段1和团结段2就取得了一个有序的递加序列

输入缓冲区1空

输入团结段1的第二块内存

排序完成，团结段1和团结段2递加有序

12.对剩余的六个团结段进行上述操作，八个团结段→四个团结段

13.第二次团结：不息采选此要领挨次取出团结段1和团结段2（团结段1为八个团结段时的团结段1和团结段2，团结段2为八个团结段时的团结段3和团结段4）的各个块进行排序操作（材干9、10、11）→四个团结段→两个团结段

原团结段1、2排序变成团结段1

原团结段3、4排序变成团结段2

14.第三次团结：不息排序团结段1、2，变成临了的有序递加序列

2.2.外部排序的支拨

上述外部排序中：变成运行团结段→第一次团结（8~4）→第二次团结（4~2）→第三次团结(2~1)（每个历程都需要读和写16次，共32+32*3=128次）

总技能支拨=里面排序所需技能+里面团结所需技能+外部读写所需技能

2.3.优化——多路团结

改用四路团结：运行化团结段→第一次团结（8~2）→第二次团结（2~1）

需要读写次数：32+32*2=96

然而，与此同期，缓冲区的数目也要变成四个（k路团结需k个缓冲区）

论断：1.关于r个运行团结段进行k路团结，需要团结趟数=

（进取取整，团结树高度）

2.普及外部排序的速率、减少读写磁盘的速率的要领：提高k值，裁汰r值。

提高r值：增多团结段长度

然而，提高k有负面影响：

A.需要的缓存空间升高（k路团结需k个缓冲区）

B.里面团结的所需技能提高（选出最小重要字需要进行k-1次相比）

3.败者树

视为一棵竣工二叉树

1.将每个团结段的第一个元素动作叶子结点加入败者树中

2.从左至右、从上往下的更新分支节点的信息：判断其阁下子树的大小，除了根节点（最上头阿谁结点）纪录冠军来自哪个团结段外，其余各分支节点纪录的是失败者来自哪个团结段

3.取出最小的元素1后，从其所属的团结段中取出下一个元素6，挨次与从叶子结点到根节点的各个结点所纪录的败者信息进行对比

引进败者树后，选出最小的重要字，仅需log2k次相比（进取取整）

4.置换弃取排序

4.1.算法思惟

使用弃取置换排序，不错让每个运行段的长度不再受限于内存责任区大小

设内存责任区最多容纳w个数据

(1)将待排媒介件FI输入w个数据到内存责任区WA中

(2)弃取WA中重要字最小的数据，输出到FO中，何况用MIN纪录该最小重要字

(3)若FI不空，则从FI中不息输入文献到WA

(4)从WA中选出比MIN更大的重要字的数据，输出并更新此最小重要字动作新MIN

(5)重叠(2)~(4)直到WA中的每个重要字都＞MIN实现，由此取得一个新的团结段

(6)重叠(2)~(5)，直到WA空，取得扫数运行团结段

4.2.手算历程

1.运奇迹态

团结段1：

2.4、6、9挨次加入内存责任区中，（4、6、9）弃取最小的元素4，输出4并蜕变MIN=4

3.加入7，（7、6、9）弃取最小元素6>MIN=4，输出6并蜕变MIN=6

4.加入13，（7、13、9）弃取最小元素7>MIN=6，输出7并蜕变MIN=7

5.加入11，（11、13、9）弃取最小元素9>MIN=7，输出9并蜕变MIN=9

6.加入16，（11、13、16）弃取最小元素11>MIN=9，输出11并蜕变MIN=11

8.加入14，（14、13、16）弃取最小元素13>MIN=11，输出13并蜕变MIN=13

9.加入10，（14、10、16）弃取最小元素10MIN=13，输出14并蜕变MIN=14

10.加入22，（22、10、16）弃取最小元素16>MIN=14，输出16并蜕变MIN=16

11.加入30，（22、10、30）弃取最小元素22>MIN=16，输出并蜕变MIN=22

12.加入2，（2、10、30）弃取最小元素2MIN=22，输出30并蜕变MIN=30

13.加入3，（2、10、3）弃取最小元素3

团结段2：

14.（2、10、3）弃取最小元素2，输出2并蜕变MIN=2

15.加入19，（19、10、3）弃取最小元素3>MIN=2，输出3并蜕变MIN=3

16.加入20，（19、10、20）弃取最小元素10>MIN=3，输出10并蜕变MIN=10

17.加入17，（19、17、20）弃取最小元素17>MIN=10，输出17并蜕变MIN=17

18.加入1，（19、1、20）弃取最小元素1MIN=17，输出19并蜕变MIN=19

19.加入23，（23、1、20）弃取最小元素20>MIN=19，输出20并蜕变MIN=20

20.加入5，（23、1、5）弃取最小元素5MIN=23，输出23并蜕变MIN=23

21.加入36，（36、1、5）弃取最小元素36>MIN=36，输出36并蜕变MIN=36

22.加入22，（12、1、5）弃取最小元素12

第三个团结段：

23.（12、1、5）弃取最小元素1，输出1并蜕变MIN=1

24.加入18，（12、18、5）弃取最小元素5>MIN=1，输出5并蜕变MIN=5

25.加入21，（12、18、21）弃取最小元素12>MIN=5，输出12并蜕变MIN=12

26.加入39，此时，待排媒介件空，将内存责任区中的剩尾数据按序输出，即18、21、39，则第三个团结段为（1、5、12、18、21、39）

5.最好团结树

1.性质和构造竣工商酌于哈弗曼树

2.与哈弗曼树的区别：

k叉树，其中k>2时：需要判断是否能得志构造竣工k叉树，若不得志，则需要添加长度为0的“虚段”

(1)若（运行团结段数目-1）%（k-1）=0，则能组成竣工k叉树

(2)若（运行团结段数目-1）%（k-1）=u≠0火狐体育APP，则讲明需要添加（k-1）-u个虚段才能组成竣工二叉树