数据结构篇_知识点板块_第九章外部排序

2022年05月11日 阅读数:2
这篇文章主要向大家介绍数据结构篇_知识点板块_第九章外部排序,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
  • 数据结构篇为本人考研时所写笔记,包括知识点和编程思想两大板块,笔记内容依据王道数据结构考研书所写,但比书本上知识更加生动形象,愿本篇章能对您有所帮助

9、外部排序

  1. 基本概念:

① 基本概念:将待排序的记录存储在外存上,排序时再把数据一部分一部分地调入内存进行排序,在排序过程当中须要屡次进行内存和外存之间的交换算法

② 外部排序过程当中的时间代价主要考虑访问磁盘的次数,即IO次数编程

③ 为减小平衡归并中外存读写次数所采起的方法:增大归并路数和减小归并段个数数据结构

(1) 利用。优化

(2) 由长度不等的归并段,进行多路平衡归并,须要构造最佳归并树code

  1. 采用的归并排序通常包括两个独立的阶段:

① 根据内存缓冲区大小,将外存上的文件分红若干长度为t的子文件,依次读入内存并利用内部排序方法对它们进行排序(例如在内存中进行2路归并,归并后的对象顺序存放在输出缓冲区中。若输出缓冲区中对象存满,则将其顾序写到输出归并段(R1')中,再清空输出缓冲区,继续存放归并后的对象。若某个输入缓冲区中的对象取空,则从对应的输入归并段中再读取下一块,继续参加归并。如此继续,直到两个输入归并段中的对象所有读入内存并都归并完成为止),并将排序后获得的有序子文件从新写回外存,称这些有序子文件为归并段或顺串(输入/输出缓冲区没有传送用户界面消息的做用,但有产生初始归并段工做区的做用)对象

② 对这些归并段进行逐趟归并,使归并段(有序子文件)逐渐由小到大,直至获得整个有序文件为止排序

  1. 外部排序的总时间=内部排序所需的时间+外存信息读写的时间(”主要矛盾“-优化的主要方向)+内部归并所需的时间内存

  2. 优化:二叉树

① 多路平衡归并并行

(1) 基本概念:

​ (1 最多只能有k个段归并为一个

​ (2 每一趟归并中,如有m个归并段参与归并,则通过一趟处理获得向上取整(m/k)个新的归并段

​ (3 创建总的I/O次数最少称为最佳归并书(相似于哈夫曼树)

(2) 代价:

​ (1 须要增长相应的输入缓冲区

​ (2 每次从k个归并段中选一个最小元素须要(k-1)次关键字比较(利用败者树(相似于比赛选拔的那样的彻底二叉树)增大归并路数(并非越大越好)从而减小比较次数)

② 减小初始归并段数量r(可利用置换-选择排序增大归并段长度从而减小归并段个数,其做用是用于生成外部排序的初始归并段,不是对外部排序中输入/归并/输出并行处理(因其不是一种完整的生成有序文件的外部排序算法))