第十一章 外部排序

 

一、内容提要

 

1、外部排序指待排序文件较大，内存一次存放不下，尚需存放在外部介质的文件的排序。

2、为减少平衡归并中外存读写次数所采取的方法：增大归并路数和减少归并段个数。

3、利用败者树增大归并路数。

4、利用置换—选择排序增大归并段长度来减少归并段个数。

5、由长度不等的归并段，进行多路平衡归并，需要构造最佳归并树。

6、磁带的多步归并排序。

 

二、学习要点

 

1、熟悉外部排序的两个阶段，归并过程。

2、掌握外部排序过程中进行外存读/写次数的计算方法。

3、“胜者树”增大归并路数不能减少外存读写次数，”败者树”可以胜任。掌握败者树建立及归并算法。

4、  熟悉置换—选择排序的过程，理解它能得到平均长度为工作区两倍的初始归并段的道理。

5、  熟练掌握最佳归并树的构造方法，及该过程中对外存读/写次数的计算方法。

6、  了解磁带多步归并的特点，熟悉归并过程及设置虚假的方法，及归并过程所需外存读/写次数的计算方法。

 

三、习题解析

 

1．“败者树“中“败者“者指的是什么?若利用败者树求k的个数中的最大者，若在比较中有a>b，谁是败者。

【解答】

   所谓”败者树”，就是在比赛（选择）树中，每个双亲结点存放两个子女结点中的”败者”，而让“胜者”参加高一层的比赛。在根结点之上，再加一个结点O，表示全局比赛获胜者。

这里用败者树求k个数中最大者，若a>b, a 是胜者，b小则是败者。

 

2．”败者树”与“堆”有何区别。

【解答】”败者树”是由参加比赛的n个元素作叶子结点所形成的完全二叉树。而”堆”则是n个元素的序列，且具有如下性质：

          Ki<=K2i              或：  Ki>=K2i

           且 Ki<=K2i+1               且 Ki>=K2i+1      (0<=i<=n DIV 2)

由于堆的这个性质中,下标i与2i及2i+1的关系，恰与完全二叉树第i个结点和它的子树结点序号关系完全一致，故堆可看成是含n个结点的完全二叉树。

 

3．设有12个归并段，其长度分别为30，44，8，6，3，20，60，18，9，62，68，85。现欲作4路外部归并排序，试华出表示归并过程的最佳归并树，并计算WPL。

【解答】

   因（12-1）MOD (4-1)=2，所以的第一次归并路数为2+1=3路，所以最佳归并树如下：             ____________( 413) __________

          ╱            ╱ ╲            ╲

 ______(64) ­­­­­­­­­_____      (68)    (85)    ______(196)_____

╱      ╱ ╲      ╲               ╱     ╱  ╲      ╲

(9 )     (17)   (18)     ( 20)          (30)   (44)    ( 60)    (62)

╱ | ╲

(3)  (6)  (8)

WPL=(3+6+8)*3+(9+18+20+30+44+60+62)*2+（68+85）*1

=51+243*2+153*1

=690