数据结构-清华大学-殷人昆

《数据结构-清华大学-殷人昆》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

第七章排序从来处来往去处去次序之美美在规矩利在行方

1概述插入排序交换排序选择排序归并排序表排序基数排序各种内排序方法的比较外排序

2概述■排序：将一组杂乱无章的数据按一定的规律顺次排列起来。■数据表(datalist):它是待排序数据记录的有限集合。■排序码(key):通常数据记录有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分记录，作为排序依据。该域即为排序码。口每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。□本章所涉及排序码的值允许重复。

3■排序算法的稳定性：如果在记录序列中有两个记录r[i]和5,它们的排序码值k[ij==k[j],且在排序之前，记录门“排在r[j]前面。如果在排序之后，记录邙]仍在记录的前面，则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。■内排序与外排序□内排序是指在排序期间数据记录全部存放在内存的排序；□外排序是指在排序期间全部记录个数太多，不能同时存放在内存，必须根据排序过程的要求,不断在内、外存之间移动的排序。

4■排序的时间开销：排序的时间开销是衡量算法好坏的最重要的标志。内排序的时间开销可用算法执行中的排序码比较次数与数据移动次数来衡量;外排序的时间开销要看读写外存的次数。-算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受记录排序码序列初始排列及记录个数影响较大的，需要按最好情况和最坏情况分别进行估算。-算法执行时所需的附加存储：评价算法好坏的另一标准。

5■从排序过程中数据的总体变化趋势来看，排序方法的处理可以分为两大类。(1)有序区增长：将数据表分成有序区和无序区，在排序过程中逐步扩大有序区，缩短无序区，直到有序区扩大到整个数据表为止。如插入排序、选择排序、起泡排序、堆排序、归并排序等。(2)有序程度增长：数据表不能明确区分有序区和无序区，随着排序过程的执行，逐步调整表中元素的排列，使得表中的有序程度不断提高，直到完全有序。如快速排序、希尔排序、基数排序等。

6待排序数据表的结构定义constintDefaultSize=100;typedefintDataType;typedefstructElement{DataTypekey;otherdata;〃表元素定义〃排序码〃其他数据成员）；typedefstructdataList{〃数据表定义Elementelem[DefaultSize];〃存宿羲组intn;前元素个数

7插入排序(InsertSorting)■基本方法是：每步将一个待排序的记录，按其排序码值的大小，插入到前面已经排好序的一组记录的适当位置上,直到记录全部插入为止。直接插入排序(InsertSort)■直接插入排序的基本思想是：当插入第个记录时,前面的elem[0h…,elem[i-l]已经排好序。这时，用的排序码与…的排序码顺序比较，找到插入位置即

8将插入,原来位置上的记录向后顺移。

9”101234567t25>21,无需移动t49>25,无需移动

10

11t37<5252,49后移

12直接插入排序的算法voidInsertSort(dataList&L){Elementw；inti";for(i=1;iO;j—)〃从后向前比较if(w.key

13法分析■设待排序记录个数为〃，则该算法的主程序执行趟。排序码比较次数和记录移动次数与记录排序码的初始排列有关。■最好情况下，排序前记录已按排序码的值从小到大有序，每趟只需与前面有序记录序列的最后一个记录比较1次，移动0次记录，总的排序码比较次数为"-1,记录移动次数为Oo■最坏情况下，第i趟时第，个记录必须与前面i个记录都做排序码比较，并且每做1次比较就要做1次数据移动。

14■因此，在最坏情况下，总排序码比较次数KCN和记录移动次数RMN分别为n-lKCN=i=双11-D。-n2/29i=lRMN=£(i+2)=(n+4)(n-1)/2。n2/2•]■在平均情况〒的排序码比较次数和记录移动次数约为4/4。因此，直接插入排序的时间复杂度为O(n2)o■直接插入排序是一种稳定的排序方法。■直接插入排序需要一个附加记录暂存待插记录。

15折半插入排序(BinaryInsertsort)-折半插入排序的基本思想是：设在顺序表中有一个记录序列elem[0]9elem[l],elem[w-l]o其中,elem[0]5elem[l]^…,elem[i-l]是已经排序的数据记录。在插入时，不是利用顺序查找从后向前寻找插入位置，而是利用折半查找法寻找elem[f]的插入位置。折半插入排序的算法voidBinaryInsSort(dataList&L){Elementw;inti,k,left,right,mid;for(i=1;i

16left=0;right=i-1;w=L.elem[i];while(left<=right){〃在内寻找elem[i]插入位置mid=(left+right)/2;〃中间位置if(w.key=left;k--)L.elem[k+1]=L.elem[k];〃空出left位置L.elem[left]=w;

17}//for

18算法分析-折半搜索比顺序搜索查找快，所以折半插入排序就平均性能来说比直接插入排序要快。-它所需的排序码比较次数与待排序记录序列的初始排列无关,仅依赖于记录个数。-在插入第，个记录时，需要经过|_1吗，」+1次排序码比较，才能确定它应插入的位置。-因此，将〃个记录元素（为推导方便，设为〃=2匕k=log2n）,折半插入排序所进行的排序码比较次数为：

19n-1*[1峭」+1)=!+2+土・+3h—卜k+k1—1~Ki=l2°21222k-1=1*2。+2"+3*22+・・・+k*2i=(k-l)*2k+1=n^(log2n-l)+l=n^log2n-n+l■这是折半查找算法分析得到的结果。折半查找的时间复杂度为O(nk)g2n)，这是指排序码比较次数的时间开销，但记录移动次数就不同了。■折半插入排序的记录移动次数比直接插入排序多一点，依赖于记录元素的初始排列。■折半插入排序是一个稳定的排序方法。■折半插入排序需要一个附加记录暂存待插记录。

20希尔排序(ShellSort).希尔排序方法又称为缩小增量排序。.该方法的基本思想是：设待排序记录序列有n个记录，首先取一个整数gapvn作为间隔，将全部记录分为gap个子序列，所有距离为gap的记录放在同一个子序列中，在每一个子序列中分别施行直接插入排序。■然后缩小间隔gap,例如取gap=[gap/2」，重复上述的子序列划分和排序工作。直到最后取gap=1,将所有记录放在同一个序列中排序为止。

2116V21.21后移08<25.25后移

2252>49.无需移动

2337>25.无需移动

2401234567i=2gap=2

2549>1621<4952>49无需移动49后移无需移动25*>0825=2537>25无需移动无需移动无需移动结果

26i=3gap=l国同闻同0123

2716<0816后移

28国园国国

29国国阂国456725<4937<52

3049后移52,49后移国同同阂

31■开始时gap的值较大，子序列中的记录较少，排序速度较快；随着排序进展，gap值逐渐变小，子序列中记录个数逐渐变多，由于前面工作的基础，大多数记录已基本有序，所以排序速度仍然很快。

32希尔排序的算法voidShellSort(dataList&L){Elementw；gap=L.n/2;while(gap!=0){〃宿环，直到gap为零for(i=gap;i=gap;j=j-gap)if(w.key

33算法分析■开始时gap的值较大，子序列中的记录较少，排序速度较快；随着排序进展，gap值逐渐变小，子序列中记录个数逐渐变多，由于前面工作的基础，大多数记录已基本有序，所以排序速度仍然很快。■gap取法有多种。最初shell提出取gap=|_n/2」，gap=Lgap/2j,直至!]gap=loknuth提出取gap=[gap/3」+L■对特定的待排序记录序列，可以准确地估算排序码的比较次数和记录移动次数。

34■但想要弄清排序码比较次数和记录移动次数与增量选择间的依赖关系，并给出完整的数学分析，还没有人能够做到。Knuth利用大量实验统计资料得出：当n很大时，排序码平均比较次数和记录平均移动次数约在ni・25到1.6出・25的范围内。■后来Hibbard提出一个稍微不同的增量序列，让gap=2T7,3J最坏情况下结果更好，运行时间在理论上证明可达到O(n3/2),但实际模拟结果可达到O(n5”。■希尔排序是个不稳定的排序方法。

35交换排序(ExchangeSort)■基本思想是两两比较待排序记录的排序码，如发生逆序(即排列顺序与排序后的次序正好相反)则交换之。直到所有记录都排好序为止。起泡排序(BubbleSort)■起泡排序的基本思路是：设待排序记录序列中的记录个数为〃。最多作“T趟起泡，2,…，n-lo在第，趟.中从后向前,j=〃一2,…，i,顺次两两比较和如果发生逆序,即elem[j-l]>elem[j],则交换elem[j-l]和elem[j]。

3601234567同国国国国同阈同Exchang=lExchang=l

37Exchang=lExchang=lExchange

38起泡排序的算法voidBubbleSort(dataList&L){inti=1,j;intexchange=1;while(i=i;j)if(L.elem[j-l].key>L.elem[j].key){〃逆序Swap(L.elem[j-1],L.elem[j]);//交装exchange=1;〃标志置为1,有交换)i++；

39算法分析■第i趟对待排序记录序列进行排序，结果将该序列中排序码最小的记录交换到序列的第一个位置其他记录也都向排序的最终位置移动。在个别情形，记录可能在排序中途向相反的方向移动。■最多做趟起泡就能把所有记录排好序。■起泡排序的时间代价受记录的初始排列影响。在记录的初始排列已经按排序码的值从小到大排好序时，此算法只执行一趟起泡，做次排序码比较，不移动记录。这是最好的情形。

40■最坏情形是算法执行趟起泡，第，趟(iwiv〃)做次排序码比较，执行次记录交换。像所有记录在一开始就已经按其排序码值逆序即为这种情况。因此，在最坏情形下总的排序码比较次数KCN和记录移动次数RMN为：KCN=2(n-i)=-n(n-l)i=l2RMN=32L(n-i)=-n(n-l)■起泡排序是一本居定的排序方法。■起泡排序需要一个附加记录作为交换记录使用。

41快速排序（QuickSort）.快速排序又称分区排序，其基本思路是：任取待排序记录序列中的某个记录（例如取第一个记录）作为基准，按照该记录的排序码值的大小，将整个记录序列划分为左右两个子序列：＞左侧子序列中所有记录的排序码值都小于或等于基准记录的排序码值；＞右侧子序列中所有记录的排序码值都大于基准记录的排序码值。■基准记录则排在这两个子序列中间（这也是该记录最终应安放的位置）。

42■然后分别对这两个子序列重复施行上述方法,到所有的记录都排在相应位置上为止。■下图是对一组排序码的一趟划分的例子。逆向正向

43012345it-——16<21t67FA逆向正向m0123456712345•||•159」3667逆向Elit49>21Jj

44快速排序一趟划分的算法intPartiton1(dataList&L,inti,intj){Elementw=L.elem[i];while(i=w.key)j一一;if(i

45L.elem[i]=w;//基准记录就位

46returni;〃返回基准位置,即排序区间划分点快速排序的递归算法voidQuicksort(dataList&L,intleft,intright){if(left

47■设待排序区间为L[left.right],以w=L[left]作为划分的基准。用指针i=left+1和j=right从区间的左端和右端开始向中间检查：(1)若L[j]>=w,让j--，重复这一步，直到遇到L[j]vw的记录容止；(2)若L[i]v=w,让i++,重复这一步，直到遇到L[i]>w的记录停止；(3)若ivj,则交换L[i]与L[j],且令i++,j—,■然后继续重复以上(1),(2),(3)步，向中间靠拢，

48直到i=j为止。交换L[j]与L[left]后，基准排在位置j,此即划分点，它左边子区间记录的排序码都比它的排序码小，右边子区间记录的排序码都比它的排序码大。■此算法比前一个划分算法整齐，算法时间复杂度都是O(n),但由于它每一次交换需要3次数据传递，比前一个算法需要数据传送的次数多。而前一个划分算法的数据传送次数已经达到了最少。■下面是一个使用此算法进行划分的示例。

49同同国同同国同囱01234567-\iij425>2108<2125,08交换01234567~iiij<

5049>2116<2149,16交换

51iiij一i=j与基准对换01234567intPartition2(DataList&L,intleft,intright){if(left

52do{while(i<=j&&〃反向检测L.elem[low].key<=L.elem[j].key)j--;while(i

53.算法的思路是：以待排序序列的第一个元素作为比较基准，然后从左向右一趟扫描过去，凡是比基准小的都交换到左边，最后对基准再做一次交换，得到划分结果。■下面给出用这个算法一趟划分的结果。同国同国同同国同01234567IkiIf->f21<2521<4921V25*21>16,16继续继续继续与25交换41，"3F

5421>08,08与49交换2K522K37继续继续

5534567012ik基准21与最后交换到前面的比21小的元素08交换国园固国国国同时01234567\k-一趟划分的算法如下所示。这三种划分算法的时间复杂度都是O(n),随序列不同，差别不大。

56intPartitions(dataList&L,intlow,inthigh){inti,k=low;for(i=low+1;i<=high;i++)if(L.elem[i].key

574,7,5,6,3,1,2PartitionlPartitionlPartitions比较次数101111移动次数142124递归深度2334,7,5,6,2,3,1PartitionlPartitionlPartitions比较次数111012移动次数161818递归深度3234,6,5,7,3,1,2PartitionlPartitionlPartitions比较次数11910移动次数172118递归深度322

58算法分析■算法quicksort是一个递归的算法，其递归树如图所不。■这是快速排序算法一次次调用partition算法得到的结果。

59■快速排序执行排序的趟数取决于递归树的高度。■如果每次划分能将序列划分为长度接近相等的子序列，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。■在n个元素的序列中，对基准元素定位所需时间为O(n)。若设T(n)是对n个元素的序列进行排序所需的时间，而且每次对一个记录正确定位后，正好把序列划分为长度相等的两个子序列，则T(n)

60Wcnlog2n+nT(l)=O(nlog2n)■可以证明，函数quicksort的平均计算时间也是O(nlog2n)0实验结果表明：就平均计算时间而言,快速排序是所有内排序方法中最好的一个。■快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。.最大递归调用层次数与递归树高度一致，理想情况为「log2(n+l)1。故栈的存储开销为OQogz11)。■最坏情况是待排序记录序列已经按其排序码从小到大排好序。

61■在最坏的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个记录的子序列。总的排序码比较次数将达^(n-i)=1n(n-l)i=l2n2X——2■附加存储(递归栈)的开销也将达到0(11)。■快速排序是一种不稳定的排序方法，其原因与希尔排序类似，都是因为出现相隔一段距离传送数据。■快速排序也可以改为非递归算法。在把待排序区间划分为两个子区间后，利用栈保存其中一个子区间的端点，再对另一个子区间快速排序。以后再从栈中恢复该子区间执行快速排序。159-52

62选择排序.选择排序的基本思想是：口每'—'趟（例如第i趟,i=0,1,・・・,〃一2）在后面〃一i个待排序记录序列中选出排序码值最小的记录，作为有序记录序列的第，个记录。待到第〃-2趟作完，待排序记录只剩下1个，就不用再选了。□选择排序的每一趟可把有序区扩大，直到〃-1趟后即可把有序区扩大到整个待排序序列。

63简单选择排序(SelectSort)・简单选择排序的基本步骤是：①在一组记录elem[i]〜中选择具有最小排序码的记羡；②若它不是这组记录中的第一个记录，则将它与这组记录中的第一个记录对调；③在这组记录中剔除这个具有最小排序码值的记录。在剩下的记录elem[i+1]elem[n-1]中重复执行第①、②步，直到剩余记录只有一个为止。

64最小者16交换25,16最小者08交换21,08>\k最小者21159-55交换“RI

65不交换同同同同同同阈同1=4i\\k最小者25本交换1=5最小者37iWk——>\k

66交换49,37国同同同国同同国1=6最小者49用左一山交换49,52国同国固国同国阈i=l时选择最小记录的过程画园同国固团

67012345i\\k最初假定L[k](k=i)最小

685女指示当0前序列中1234i\\kj\49>25,j++团连国国同国国国除JI25*>25,j++词国同国国国16<25,j++词国同国同画

69159-5821>16

70简单选择排序的算法voidSelectSort(dataList&L){inti,j,k;for(i=0;i

71算法分析■简单选择排序的排序码比较次数KCN与记录的初始排列无关。设整个待排序记录序列有〃个记录，则第，趟选择具有最小排序码记录所需的比较次数总是次。总排序码比较次数为KCN=£(n—i—l)=^^i-o2■记录的移动次数与序列的初始排列有关。当这组记录初始时已经按其排序码值从小到大有序时，记录的移动次数RMN=O,最坏情况是每趟都要进行交换，总记录移动次数为RMN=3(n-1)。

72■简单选择排序是一种不稳定的排序方法。■简单选择排序算法只用到一个附加存储用于数据交换。堆排序(HeapSort)■利用堆及其运算，可以实现选择排序的思路。■堆排序分为两个步骤①根据初始输入数据，利用堆的筛选算法siftDown()形成初始堆；②通过一系列的记录交换和重新调整堆进行排序。

73■如果堆排序采用小根堆，所有记录在排序后将按其排序码从大到小排列。所以改使用大根堆。21254925*1608初始排序码集合214908i=2时的局部调整

74214908i=1时的局部调整214908■i=0时的局部调整形成大根堆

75大根堆的向下筛选算法voidsiftDown(dataList&H,intstart,intm){inti=start;intj=2*i+l;HElemTypew=H.heap[i];while(j<=m){〃藁后位置if(j=H.heap[j].key)break;else{H.heap[i]=H.heap[j];i=j;j=2*j+l;}〃大子女上移，向下继续调整)

76H.heap[i]=w;〃回放到合适位置

77将表转换成堆的算法for(inti=(H.n-2)/2;i>=0;i--)siftDown(H,i,H.n-1);基于初始堆进行堆排序■大根堆的存储结构采用完全二叉树的顺序存储，实际上它的所有结点是保存在一维数组H.heap[0]中的。对大根堆进行各种操作，实际上是对一维数组的操作，因此，堆排序的结果将存放在一维数组中。■大根堆排序的过程可描述如下：

78■大根堆堆顶H.heap[O]保存具有最大排序码的记录，将H.heap[O]与H.heap[n-1]对调，把具有最大排序码的记录交换到最后；.对前面的11-1个记录，使用堆的向下筛选算法siftDown(H,0,n-2),重新建立大根堆，具有次大排序码的记录又上浮到H.heap[0H立置。其中n是堆的当前大小。■对调H.heap[0]和H.heap[n-2]记录，调用siftDown(H,0,n-3),对前n-2个记录重新筛选形成大根堆，…，如此反复执行，最后得到全部排序好的记录序列。此算法即堆排序。

7949252125*1608初始大根堆

8008252125女164908252125*1649交换0号与5号记录,5

81号记录就位

822525*21081649从0号到4号重新调整为大根堆

831625*210825491625*21082549交换0号与4号记录,4

84号记录就位

8525*1621082549从0号到3号重新调整为大根堆

8608162125*254908162125*2549交换0号与3号记录,3号记录就位

8721160825*2549从0号到2号重新调整为大根堆

8808162125*254908162125*2549交换0号与2号记录,2号记录就位

8916082125*254916082125*2549从0号到1号重新调整为大根堆

9008162125*254908162125*2549交换0号与1号记录,1号记录就位

91堆排序的算法voidHeapSort(maxHeap&H){〃对小根堆H.heap[0]到H.heap[H.CurrentSize-l]进〃行排序，使得表中各个记录按其排序码非递减有序。inti;for(i=(H.CurrentSize/2-1;i>=0;i--)siftDown(H,i,H.CurrentSize-1);〃初始堆for(i=H.CurrentSize-1;i>=1;i--){Swap(H.heap[0],H.heap[i]);//交换siftDown(H,0,i-1);〃重建大根堆

92算法分析■若设堆中有n个结点，且2h/WnV2h,则对应的完全二叉树有h层。在第i层上的结点数(i=1,2,…,h)。在第一个形成初始堆的for循环中对每一个非叶结点调用了一次堆的向下筛选算法siftDown(),因此该循环所用的计算时间为：h-l2・Z2”・(h-i)i=l■其中，i是层号，非叶结点最多有h-l层，第i层最多有27个结点，第i层每个结点最多下移h-i层。每个结点每次执行横/纵向2次比较。

93h-12pi(h-i)=2*i=lh—1)*2°+(h—2)*2]+・・・+1*2卜2]=2*{(2R2+2r3+・・・+2。)+(2h-3+2h-4+***+2°)+…+2°}h-l个=2*{Qh“—1)+(2h-2-l)+…+(21-1)}=2*{(2h-x+2h-2+-+21+2°)-2°-(1+1+―+1)}=2*{(2h-l)-l-(h-l)}=2*{2h-l-h}=2*{(n+l)-1-「log2(n+l)l}=2*{n-Flog2(n+l)l}■当n=255时，h=「log2(n+l)1=8,形成初始堆得到排序码最小记录需比较2*(255-8)=494次。■排序过程中，第i次重构堆时堆内有n-i个结点,

94■自顶向下筛选时,排序码比较2*Llog2(n-i)J次,n-1次重构堆的排序码比较次数为n—l2*ZU°g2(n—i)」(2*{log2(n—1)+105(吁2)++10当1}i=l=2*log2(n-l)!-2*((n-l)log2(n-l)-1.5(n-l))==2*("l)*log2(nT)3*(n-1)■因此，堆排序的时间复杂性为O(nlog2ii)。■该算法的附加存储主要是在第二个for循环中用来执行记录交换时所用的一个临时记录。因此该算法的空间复杂性为0(1)。■堆排序是一个不稳定的排序方法。

95归并排序(MergeSort)-归并排序采用典型的分而治之算法，描述如下：MergeSort(List){if(List的长度大于1){将序列List划分为等长的两个子序列LeftList和RightList;MergeSort(LeftList);〃对子序列递归排序MergeSort(RightList);〃对子序列递归排序将两个子序列LeftList和RightList归并为一个序列List;

96两路归并(2-waymerging)■归并，是将两个或两个以上的有序表合并成一个新的有序表。■例如，原始序列L[]中有两个有序表L[4…L[m]和L[m+1]…L[川。把它们归并成一个有序表，存于另一序列L1的L1用…L1[川中。这种归并方法称为两路归并(2-waymerging)o■为了实现两路归并，需要设置3个指针：变量，和j是表L用…L.]和LM+1]…L[川的当前检测指针。女是表L1的存放指针。

97leftmidmid+1rightL|08212525*49627293”163754leftrightLI|0816212525*374954627293Ik■当i和j都在两个表的表长内变化时，根据对应项的排序码的大小，依次把排序码小的记录排放到新表女所指位置中；■当，与j中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表中。

98两路归并算法voidmerge(dataList&L,dataList&L1,intleft,intmid,intright){inti=left,j=mid+1,k=left;while(i<=mid&&j<=right)〃两两比较if(L.elem[i].key<=L.elem[j].key){Ll.elem[k]=L.elem[i];i++;k++;}else{Ll.elem[k]=L.elem[j];j++;k++;}while(i<=mid)//前一个表未见理完,复制{Ll.elem[k]=L.elem[i];i++;k++;}while(j<=right)〃后一个表未处理完,复制{Ll.elem[k]=L.elem[j];j++;k++;}

99迭代的归并排序算法・迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：□假设初始记录序列有n个记录，首先把它看成是n个长度为1的有序子序列（归并项），先做两两归并，得到「n/21个长度为2的归并项（如果n为奇数，则最后一个有序子序列的长度为1）；再做两两归并，…，如此重复，最后得到一个长度为n的有序序列。

100迭代的归并排序算法

101len=160816212525*374954627293一趟两路归并排序的情形-设L[0]到L[n-1]中n个记录已经分为一些长度为len^J

102归并项，将这些归并项两两归并，归并成长度为21en的归并项,结果放到Ll[]中。■如果n不是21en的整数倍，则一趟归并到最后，可能遇到两种情形：(1)剩下一个长度为len的归并项和另一个长度不足len的归并项，可用merge算法将它们归并成一个长度小于21en的归并项。(2)只剩下一个归并项，其长度小于或等于len,将它直接抄到Ll[]中。

103voidMergePass(dataList&L,dataList&LI,intlen){inti=0;while(i+2*len-1<=L.n-1){〃批量处理merge(L,LI,i,i+len-1,i+2*len-l);i=i+2*len;〃循环两两归并)if(i+len<=L.n-1)〃后一归并项长度不足len情形merge(L,LI,i,i+len-1,L.n-1);else〃只剩一个归并项情形，复制for(intj=i;j<=L.n-1;j++)Ll.elem[j]=L.elem[j];Ll.n=L.n;

104(两路)归并排序的主算法voidMergeSort(dataList&L){〃按记录排序码值非递减的顺序对表中记录排序dataListL1;〃设置辅助表intlen=1;while(len

105法分析■在迭代的归并排序算法中，aMergePass做一趟两路归并排序，要调用merge函数「n/(2*len)]«O(n/len)次;口MergeSort调用MergePass正好「log2111次；口每次merge。要执行比较O(len)。所以算法总的时间复杂度为O(nlog2n)o■归并排序需要另外一个与原待排序记录数组同样大小的辅助数组，占用附加存储较多。■归并排序是一个稳定的排序方法。

106另一个两路归并算法(递归)voidMerge(dataList&L,intleft,intmid,intright){dataListLI;inti=left,j=right,k=left,s;〃i,j是检测指针,k是存放指针,s是循环变量Ll.n=L.n;for(s=left;s<=mid;s++)〃正向复制Ll.elem[s]=L.elem[s];for(s=mid+1;s<=right;s++)〃反向复制LI.elem[right+mid+1-s]=L.elem[s];while(k<=right)〃归并过程if(Ll.elem[i].key<=Ll.elem[j].key)L.elem[k++]=Ll.elem[i++];elseL.elem[k++]=Ll.elem[j一一];

107）；

108leftmidmid+1rightL|08212525*49627293“163754正向复制<——反向复制leftmidmid+1rightLI|08212525^49627293||543716\i~\i__~~~~~f/~\jleftright'k'左［左'k'k

109递归的归并排序算法voiddoSort(dataList&L,intleft,intright){if(left

110表排序(LinkedListsorting)■前面介绍的排序方法都是基于排序码比较，把记录物理地移到它在序列中最终位置的方法。影响算法效率的关键是数据记录的移动。■为了提高排序速度，可考虑给每一个记录附加一个链接指针。通过指针把所有元素按排序码值从小到大的顺序链接起来，免去数据的移动。■这就是表排序，依据的数据结构就是静态链表。■不是所有排序方法都可以用链表实现，只有基于单向顺序比较的算法，如直接插入排序、简单选择排序、起泡排序、归并排序等才可以。

111静态链表的结构定义#defineDefaultSize10typedefintDataType;typedefstructElement{DataTypekey;other;intlink;)typedefstruct{Elementelem[DefaultSize];intn;〃在staticList.h文件中〃静态链表元素定义〃排序码〃其他元素内信息〃结点的链接指针〃静态链表定义〃存储数组〃当前元素个数}StaticLinkList;

112链表插入排序■链表插入排序的基本思想是：口对于静态链表数组中的一组元素elem[l],…，elem[矶若…,elem[i-l]已经通过指针link,按其排序码值从小到大链接起来。现要插入elemRhi=2,3,…,n9则必须在前面的iT个元素的链表中查找elem[i]应插入的位置,把elemfi]链入,从而得到…,elem[i]的一个有序链表。-如此重复执行，直到把elem卬也插入到链表中排好序为止。

113初始i=2i=3f=4i=5i=6keylinkkeylinkkeylinkkeylinkkeylinkkeylink

114链表插入排序的算法#includeHstaticList.hHconstDataTypemaxValue;〃排序码中的最大值voidinsertSort(staticLinkList&L){〃对L.elem[l],...,L.elem[n]按其排序码key排序,//L.elem[0]做为排序后有序循环链表头结点使用L.elem[0].key=maxelemalue;L.elem[0].link=1;L.elem[l].link=0;〃形成只有一个元素的循环链表inti,pre,p;

115)；for(i=2;i<=L.n;i++){〃每趟向有序链表中插入一个结点p=L.elem[O].link;〃p是链表检测指针pre=0;〃pre指向p的前驱while(L.elem[p].key<=L.elem[i].key)〃循链找插入位置,i是插入,p是检测位置{pre=p;p=L.elem[p].link;}L.elem[i].link=p;L.elem[pre].link=i;〃结点i链入结点pre后,结点p前

116算法分析■使用链表插入排序，每插入一个元素，排序码比较次数最多等于链表中已排好序的元素个数（初始排列已经按排序码值从小到大有序），最少等于1（初始排列已经按排序码值从大到小有序）。故总排序码比较次数最好情况下为〃最大为ni=25+2广)=0")■用链表插入排序时，元素移动次数为0。但增加了n个链域link和一个表头结点。■链表插入排序方法是稳定的排序方法。

117链表选择排序■基于静态链表实现简单选择排序的基本思路是：□设所有待排序的数据元素已经在链表中顺序链接，并把L.elem[O]用作表头结点。□每一趟排序时从原链表中选择排序码值最大的元素，将它从链中摘下，再插入一个初始为空的新链表的首部。-当所有元素都从原链表中摘下并插入到新链表中,则新链表中元素已经有序链接起来。21254925*160f23450初始keylink012345

118i=1keylinki=2keylinki=3keylinki=4keylinki=5keylinki=6keylink最大者elem[3]链入薪链表最大者elem[2]链入新链表最大者elem[4]链入新链表最大者链入新链表最大者elem[5]链入新链表原始链表头指针为空

119链表选择排序的算法#includenstaticList.hnvoidselectSort(staticLinkList&L){〃L.elem⑼作为头结点使用，到L.elem|n］存〃放数据，静态链表采用单链表而不是循环链表。mtf=Lp,pre,i,j;for(i=1;i

120while(i!=0){〃在原始链表中检测if(L.elem[i].key>L.elem[p].key){P=i；pre=j;}〃p记忆当前找到的排序码最大结点j=i;i=L.elem[i].link;〃至原链表下一结点)if(p==f)f=L.elem[f].link;〃从链中摘下pelseL.elem[pre].link=L.elem[p].link;L.elem[p].link=L.elem[O].link;L.elem[O].link=p;〃结点p插入到链表前端

121算法分析■链表选择排序通过一个二重循环在原始链表中反复选择具有最大排序码值的元素。设原始链表中有〃个元素，要执行的排序码比较次数为£（…+1）=当tD=q高i=l2■数据移动次数为0。附加存储与链表插入排序相同。■链表选择排序是一个不稳定的排序方法。

122链表归并排序■链表归并排序算法的思路是:□首先把整个待排序序列划分为两个长度大致相等的部分，分别称之为左子表和右子表。对这些子表分别递归地进行排序，然后再把排好序的两个子表进行归并。■图示：待排序元素序列的排序码值为{21,25,49,25*,16,08},先是进行子表划分，待到子表中只有一个元素时递归到底。再实施归并，逐步退出递归调用的过程。

123

124链表两路归并算法#includenstaticList.hnintListMerge(staticLinkList&L,intsi,ints2){//两个有序链表第一个结点的下标分别为si和s2,〃函数返回归并后有序链表的第一个结点下标。//L⑼是工作单元。intk=0,i=si,j=s2;while(i!=0&&j!=0)〃做两两比较if(L.elem[i].key<=L.elem[j].key){L.elem[k].link=i;k=i;i=L.elem[i].link;}else{L.elem[k].link=j;k=j;j=L.elem[j].lmk;}

125if(i==0)L.elem[k].link=j;//i链检测完,j链接上elseL.elem[k].link=i;//j链检测完,i链接上returnL.elem[0].link;〃返回结果链头指针)；递归的归并排序算法intrMergeSort(staticLinklist&L,intleft,intright){//对链表1.&。111［招自］，6招111［邈枕］进行排序o各结点〃中的链域link应初始化为0,rMergeSort返回排序后〃链表第一个结点的下标，L.elem［0］是工作单元if(left>=right)returnleft;

126intmid=(left+right)/2;〃划分中间位置returnListMerge(L,rMergeSort(L,left,mid),rMegerSort(L,mid+1,right));)；算法分析■链表归并排序方法的递归深度为OQogzn），元素排序码的比较次数为Omiog211）。■链表归并排序所需附加存储与链表插入排序或链表选择排序相同，但又用到递归栈。■链表归并排序方法是一种稳定的排序方法。

127基数排序(RadixSort)■基数排序是采用“分配”与“收集”的办法，用对多排序码进行排序的思想实现对单排序码进行排序的方法。多排序码排序■以扑克牌排序为例。每张扑克牌有两个“排序码”：花色和面值。其有序关系为：a花色：*<♦

128■如果我们把所有扑克牌排成以下次序：*9*2,儿♦2,•••,♦2,•••,余2,•••,/A-这就是多排序码排序。排序后形成的有序序列叫做词典有序序列。-对于上例两排序码的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。-一般情况下，假定有一个n个元素的序列{elem。,elem15...5elem^j},且每个元素elem,.中含有d个排序码（K；,K；,…,瞪）

129■如果对于序列中任意两个元素elem,和eleiriy(03)都满足:依,K；,…,Kf)<(K；,肩,…,蜀)■则称序列对排序码侬1,昭,…,心)有序。其中，K称为最高位排序码，M称为最低位排序码。■如果排序码是由多个数据项组成的数据项组，则依据它进行排序时就需要利用多排序码排序。■实现多排序码排序有两种常用的方法：□最高位优先MSD(MostSignificantDigitfirst)a最低位优先LSD(LeastSignificantDigitfirst)

130・最高位优选法通常是一个递归的过程:口先根据最高位排序码K排序，得到若干元素组,元素组中各元素都有相同排序码KL口再分别对每组中元素根据排序码蜉进行排序，按号值的不同，再分成若干个更小的子组,每个子组中的元素具有相同的K和K2值。□依此重复,直到对排序码心完成排序为止。口最后，把所有子组中的元素依次连接起来，就得到一个有序的元素序列。

131■最低位优先法□首先依据最低位排序码心对所有元素进行一趟排序，再依据次低位排序码心-1对上一趟排序的结果再排序，依次重复，直到依据排序码K最后一趟排序完成，就可以得到一个有序的序列。口这种排序方法对每个排序码进行排序时，不需要再分组，而是整个元素组都参加排序。■LSD和MSD方法也可把单个排序码凡看作是一个子排序码组：（（，K；,…，进行排序。

132链式基数排序■基数排序是典型的LSD排序方法，利用“分配”和“收集”对单排序码进行排序。在这种方法中，把单排序码片看成是一个d元组：(K；,K；,…,K；)■其中的每一个分量号agso也可看成是一个排序码。■分量号有radix种取值，称radix为基数。例如，排序码984可以看成是一个3元组(9,8,4),每一位有0,1,…，9等10种取值，基数radix=10。排序码Fata，可以看成是一个4元组(d,a,t,a),每一位有‘a'Jb',…,3等26种取值,radix=26。

133■针对d元组中的每一位分量，把元素序列中的所有元素，按号•的取值，先“分配”到3个队列中去。然后再按各队列的顺序，依次把元素从队列中“收集”起来，这样所有元毛胺取值排序完成。■如果对于所有元素的排序码匹,&,…,（小依次对各位的分量，让也…J分别用“分配”、“收集”的运算逐趟进行排序，在最后一趟“分配”、“收集”完成后，所有元素就按其排序码的值从小到大排好序了。■各队列采用链式队列结构，分配到同一队列的排序码用链接指针链接起来。

134■每一队列设置两个队列指针：口intfront[radix]指示队头口intrear[radix]指向队尾■为了有效地存储和重排〃个待排序元素，以静态链表作为它们的存储结构。

135基数排序的“分配”与“收集”过程第w614f738—921—485—637—101—215—530—790—306第一趟分配（按最低位i=3）第一趟收集

136530—790—A921—101—>614—»485卜215—306—637—738

137基数排序的“分配”与“收集”过程第530-790f921->101->614->(485->215]->306f637f738第二趟分配（按次低位i=2）re[Q]re[l]re[2]re[3]re[4]i—Hi-H738306215士士n।6371咽困率画#[0]All]fr[2]fr[3]fr[4]第二趟收集re[5]re[6]re[7]re[8]re[9]八fr[9]fr[5]fr[6]fr[7]fr[8]101->306->614->215->921->530->637->738-4485->790

138基数排序的“分配”与“收集”过程第101f306f614卜215—►921f530->637->738f485f790第三趟分配（按最高位i=l）第三趟收集

139101215f306f485f530f614637f738f790f921I

140链表基数排序#include"staticList.h"〃静态链表头文件constintradix=10;//基数elemoidSort(staticlinkList&L,intd){intrear[radix],front[radix];〃队尾与队头指针inti,j,k,last,current;for(i=0;i=1;i--){〃按集序码key[i]分配for(j=0;j

141while(current!=0){〃分酉己k=getDigit(L.elem[current],i);〃取第i个排序码if(front[k]==0)front[k]=current;〃第k个队列空,该元素为队头elseL.elem[rear[k]].link=current;〃该队列不空，链接到队尾rear[k]=current;〃成为新的队尾current=L.elem[current].link;〃下一个元素)j=0;〃依次从各队列收集并拉链while(front。]==0)j++;〃跳过空队列

142L.elem[O].link=current=front。];〃新链表的链last=rear[j];//非空队列链尾for(k=j+1;k

143算法分析■若每个排序码有d位，需要重复执行d趟“分配”与“收集”。每趟对n个元素进行“分配”，对radix个队列进行“收集”。总时间复杂度为O(d(n+radix))■若基数radix相同，对于元素个数较多而排序码位数较少的情况，使用链式基数排序较好。■基数排序需要增加n+2*radix个附加链接指针。■基数排序是稳定的排序方法。

144各种内排序方法性能的比较.各种排序方法的性能应从以下七个方面综合考虑:(1)时间复杂度；(2)空间复杂度；(3)算法稳定性；(4)算法简单性；(5)待排序元素个数n的大小；，(6)待排序元素本身信息量的大小；(7)待排序元素排序码的分布情况。■各种内排序的时间和空间性能的比较如下所示。

145各种排序方法的比较排序方法比较次数移动次数稳定附加存储最好最差最好最差性最好最差直接插入排序0(n2)00(n2)q0(1)折半插入排序0(nlog2n)00(n2)0(1)起泡排序0(n)0(n2)00(i?)q0(1)快速排序O(nlog2n)0(n2)O(log2n)0(n)XO(log2n)0(n)简单选择排序0(n2)00(n)X0(1)堆排序0(nlog2n)0(nlog2n)X0(1)归并排序0(nlog2n)0(nlog2n)0(n)基数排序O(d(n+rd))00(rd+n)

146外排序磁盘存储器-磁盘存储器属于外存储器，与内存储器相比，它的优点是价格较低，具有持久存储能力；它的缺点是访问外存储器上的数据比访问内存要慢5〜6个数量级。■如果计算机的计算涉及外存储器，与内存运算相比，外存访问的时间可能成为运算效率的瓶颈。所以，在设计大型系统时，必须考虑如何使得计算机访问外村的次数达到最少。

147■磁盘存储器通常称为直接存取设备，或随机存取设备，它访问外存上文件的任一记录的时间几乎相同。■磁盘存储器可以顺序存取，也可以随机存取。■目前使用较多的是活动臂硬盘组:若干盘片构成磁盘组，它们安装在主轴上，在驱动装置的控制下高速旋转。除了最上面一个盘片和最下面一个盘片的外侧盘面不用以外，其他每个盘片上下两面都可存放数据。将这些可存放数据的盘面称为记录盘面。

148读写磁头主轴磁道盘片柱面活动臂（回转臂）

149每个记录盘面上有很多磁道，数据就存放在这些磁道上。它们在记录盘面上形成一个个同心圆。任一时刻，所有记录盘面的读写磁头停g在各个记录盘面的半径相同的磁道上。各个记录盘面上半径相同的磁道合在一起称为柱面。动臂的移动实际上是将磁头从一个柱面移动到另一个柱面上。一个磁道可以划分为若干段，称为扇区，一个扇区就是一次读写的最小数据量。这样，对磁盘存储器来说，从大到小的存储单位是：盘片组、柱面、磁道和扇区。

150n对磁盘存储器进行一次存取所需时间:①当有多个盘片组时，要选定某个盘片组。这是由电子线路实现的，速度很快。②选定盘片组后再选定某个柱面，并移动动臂把磁头移到此柱面上。这是机械动作,速度较慢。这称为“寻查（seek）”。③选定柱面后，要进一步确定磁道，即确定由哪个读写磁头读写，由电子线路实现。④确定磁道后，还要等待要读写的扇区转到读写磁头下面。这是机械动作。虽然是高速旋转，但比电子运算还要慢得多。

151⑤真正进行读写时间。■在磁盘组上一次读写的时间主要为:tio=tseek+tlatency+U■其中，是平均寻查时间，是把磁头定位到要求柱面所需时间。…是平均等待时间，是将磁头定位到指定块所需时间。「是传送一个扇区数据所需的时间。■在操作系统中，文件分配的最小单位和读写的最小单位是一个扇区，称为一个块(block)。磁盘一次读写操作访问一个扇区，称为访问“一页，，(page)或“一块”(block),或“一次访

152缓冲区（buffer）■为了实施磁盘读写操作，在内存中需要开辟一些区域，用以存放需要从磁盘读入的信息，或存放需要写出的信息。这些内存区域称为缓冲区。■多数操作系统至少设置两个缓冲区，一个为输入缓冲区；一个为输出缓冲区。■缓冲区大小应与操作系统一次读写的块的大小相适应，这样可以通过操作系统一次读写把信息全部存入缓冲区中，或把缓冲区中的信息全部写出到磁盘。■缓冲区的构造可以看作一个先进先出的队列。

153外排序的基本过程基于磁盘进行的排序多使用归并排序方法。其排序过程主要分为两个阶段:①建立用于外排序的内存缓冲区。根据它们的大小将输入文件划分为若干段,用某种内排序方法对各段进行排序。经过排序的段叫做初始归并段(Run)。当它们生成后就被写到外存中去。②按归并树模式，把①生成的初始归并段加以归并,一趟趟扩大归并段和减少归并段数，直到最后归并成一个大归并段为止。

154■示例：设有一个包含4500个记录的输入文件。现用一台其内存至多可容纳750个记录的计算机对该文件进行排序。输入文件放在磁盘上，磁盘每个页块可容纳250个记录，这样全部记录可存储在4500/250=18个页块中。输出文件也放在磁盘上，用以存放归并结果。■由于内存中可用于排序的存储区域能容纳750个记录,因此内存中恰好能存3个页块的记录。■在外排序一开始，把18块记录，每3块一组，读入内存。对其进行内排序，形成初始归并段,再写回外存。总共可得到6个初始归并段。

155两路归并排序的归并树第三趟归并结果初始归并段第二趟归并结果第一趟归并结果R1234564500/

156输入缓冲区1输出缓冲区输入缓冲区2―■若把内存区域等份地分为3个缓冲区。其中的两个为输入缓冲区，一个为输出缓冲区，可以在内存中利用2路归并函数merge()实现2路归并。■首先,从参加归并排序的两个输入归并段&和&中分别读入一块,放在输入缓冲区1和输入夔冲区2中。然后在内存中进行2路归并，归并结果顺序存放到输出缓冲区中。

157■若总记录个数为〃,磁盘上每个页块可容纳b个记录，内存缓冲区可容纳，个页块，则每个初始归并段长度为len=i*b,可生成r=[nHen]个等长的初始归并段。■在做2路归并排序时，第一趟从，个初始归并段得到「〃21个归并段,以后各趟将从/(/>1)个归并段得到「〃21个归并段。总归并趟数等于归并树的高度减一：「10g2，L■估计2路归并排序时间嗝的上界为：+S*n*tmg

158■对4500个记录进行外排序的例子,各种操作的计算时间如下：口读18个输入块，内部排序6段，写18个输出=60s+36tIO口成对归并初始归并段&〜4=36tI0+4500tmg□归并两个具有1500个记录的归并段与2和&4=24tI0+3000tmg口最后将&234和氏56归并成一个归并段=36tIO+4500%■合计=6%+132tIO+12000tmg

159■由于£/o=^seek+tlatency+%,其中"se凝和Gtency是机械动作，而总、tJS.£冲是电子线路的动作，所以机远远大于小和〃g。想要提高外排序的速度，应着眼于减少必■若对相同数目的记录，在同样页块大小的情况下做3路归并或做6路归并（当然，内存缓冲区的数目也要变化），则可做大致比较：归并路数根236归并趟数S321总读写磁盘次数d13210872

160■增大归并路数，可减少归并趟数，从而减少总读写磁盘次数d。■对，个初始归并段，做机路平衡归并，归并树可用正则m叉树（即只有度为m与度为0的结点的m叉树）来表示。■第一趟可将厂个初始归并段归并为/=17/桃1个归并段，以后每一趟归并将，个归并段归并成/=「1/帆］个归并段，直到最后形成一个大的归并段为止。归并趟数S=「log”1。

161根路平衡归并(zn-wayBalancedmerging)・做机路平衡归并时，如果有r个初始归并段，则相应的归并树有「log/1+l层，需要归并「log”1趟。下图给出对有36个初始归并段的文件做6路平衡归并时的归并树。

162-做内部m路归并时，在m个记录中选择最小者,需要顺序比较机-1次。每趟归并n个记录需要做(〃-1)*(忆-1)次比较，S趟归并总共需要的比较次数为：(加-1)=「log/r]*(〃-1)*(iw-1)=「log2rl*(〃-1)*(w-1)/「log2初・在初始归并段个数，与记录个数〃一定时，可将「log2，〕*(〃T)视为常数，而0«T)/「log2-l在刀增大时趋于无穷大。因此,增大归并路数叫会使得内部归并的时间增大。

163■可以使用“败者树”从机个归并段中选最小者，当机较大时(机26),选出排序码最小的记录只需比较「logz/!次。S*(〃-l)*「log2%]=「logzZ〕*(n-1)*「log2ml=「log2rl*(n-1)*「log2川/「log?川-rlog2r-|*(w-1)■排序码比较次数与机无关，总的内部归并时间不会随上的增大而增大。■关于败者树的讨论，不在本课程的范围内讨论。

164初始归并段的生成(RunGeneration)■为减少读写磁盘次数，除增加归并路数m外，还可减少初始归并段个数八在总记录数〃一定时,要减少，，必须增大初始归并段长度。■如果规定每个初始归并段等长，则此长度应根据生成它的内存工作区空间大小而定。■采用选择置换排序，在使用同样大内存工作区的情况下，可生成平均比原来等长情况下大一倍的不等长的初始归并段，以减少初始归并段个数。

165例如，设输入文件口中各记录的排序码序列为{17,21,05,44,10,12,56,32,29}选择和置换过程的步骤如下：①从输入文件B中把帆个记录读入内存工作区中（内存工作区,可容纳的记录个数为机）②在r中选择一个排序码最小的记录，⑷，其排序码存入LastKey作为门槛。以后再选出的排序码比它大的记录归入本归并段，比它小的归入下一归并段。③将此，⑷记录写到输出文件方。中（q是叶结点序号）。

166④⑤⑥⑦若B未读完，则从为读入下一个记录，置换r[q];否则在r[q]中置一个如00的标记。在内存工作区中从所有排序码比LastKey大的记录中选择一个排序码最小的记录r[q]作为门槛,其排序码存入LastKey。重复③〜⑤，直到在败者树中选不出排序码比LastKey大的记录为止。此时，在输出文件方。中得到一个初始归并段，在它最后加一个归并段结束标志。重复②〜⑥，重新开始选择和置换，产生新的初始归并段,直到输入文件3中的记录全部选完并输出为止。

167输入文件以内存数组r输出文件FO-2105441012563229441012563229172105101256322917214405125632291021440517563229101244051721322910125605172144291012320517214456291012320517214456oo2910123229123210298321012OOOO32101229OOOOOO10122932OOOOOO10122932oo.若按在机路平衡归并排序中所讲的，每个初始归

168并段的长度与内存工作区的长度一致，则上述9个记录可分成3个初始归并段：RunO{05,17,21)Runl{10,12,44)Run2{29,32,56)■若采用选择与置换排序，可生成2个长度不等的初始归并段：RunO{05,17,21,44,56)Runl{10,12,29,32}最佳归并树■归并树是描述归并过程的机叉树。因为每一次做机路归并都需要有机个归并段参加，因此，归并树是只有度为0和度为m的结点的正则m叉树。

169■示例：设有13个长度不等的初始归并段,其长度（记录个数）分别为0,0,1,3,5,7,9,13,16,20,24,30,38-其中长度为0的是空归并段。对它们进行3路归并时的归并树如图所示。

170此归并树的带权路径长度为WPL=(24+30+38+7+9+13)*2+(16+20+1+3+5)*3=377。

171■在归并树中□各叶结点代表参加归并的各初始归并段□叶结点上的权值即为该初始归并段中的记录个数□根结点代表最终生成的归并段□叶结点到根结点的路径长度表示在归并过程中的读记录次数□各非叶结点代表归并出来的新归并段口归并树的带权路径长度WPL即为归并过程中的总读记录数。因而，在归并过程中总的读写记录次数为2^WPL=754O

172-不同的归并方案所对应的归并树的带权路径长度各不相同。-为了使得总的读写次数达到最少，需要改变归并方案，重新组织归并树。-可将Huffman树的思想扩充到机叉树。在归并树中，让记录个数少的初始归并段最先归并，记录个数多的初始归并段最晚归并，就可建立总读写次数达到最少的最佳归并树。-例如，假设有U个初始归并段，其长度（记录个数）分别为1,3,5,7913,16,20,24,30,38,做3路归并。

173-为使归并树成为一棵正则三叉树,可能需要补入空归并段。补空归并段的原则为：口若参加归并的初始归并段有〃个，做机路平衡归并。因归并树是只有度为0和度为机的结点的正则机叉树，设度为0的结点有劭(=〃)个，度为根的结点有“加个，则看n^=(m-l)nm+l〃机=(〃0-1)/(加T)。口若(n0-l)%(m-1)=0,则说明这〃o个叶结点正好可以构造机叉归并树。♦若(n0-l)%(m-1)=u#0,则对于这“0个叶结点,其中的〃个不足以参加根路归并。

174口故除了有〃帆个度为根的内结点之外，还需增加一个内结点。它在归并树中代替了一个叶结点位置，被代替的叶结点加上刚才多出来的u个叶结点,再加上m-u-1个记录个数为零的空归并段，就可建立归并树。♦在示例中,“0=11,加=3,(11-1)%(3-1)=0,可以不加空归并段，直接进行3路归并。-它的带权路径长度WPL=38*1+(13+16+20+24+30)*2+(7+9)*3+(1+3+5)*4=328。

17535（7）⑥f®®®®©®®®13597259135997（24）顿@（38）13162049159-15235997162024253038497916613■如果做5路归并，让机=5,则有

176(11-1)/(5-1)=2■表示有2个度为5的内结点；但是,w=(11-1)%(5-1)=2/0■需要加一个内结点，它在归并树中代替了一个叶结点的位置，故一个叶结点参加这个内结点下的归并，需要增加的空初始归并段数为m-u-1=5-2-1=2■应当补充2个空归并段，则归并树如图所示。

1770)(0)(1)(3)(5®®®®带权路径长度WPL=(l+3+5)*3+(7+9+13++16)*2+(20+24+30+38)=229159-154

178例题1下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是I、简单选择排序II.希尔排序m.快速排序IV.堆排序V.二路归并排序A.仅I、III.IVB.仅I、III.VC.仅II、III>IVD.仅III、IV、V解答：选A。简单选择排序每一趟把当前待排序序列中最小元素对换到序列最前端，快速排序每一趟把基准元素通过划分安放到序列中它最终应在的位置，堆排序每一趟通过交换和重新调整堆,把堆顶元素安放到它在有序序列中的最终位置。

179例题2使用递归的快速排序算法，下列关于递归次数的叙述中，正确的是A.递归次数与数据的初始排列次序无关B.每次划分后先处理较长分区可减少递归次数C.每次划分后先处理较短分区可减少递归次数D.递归次数与每次划分后所得分区的处理顺序无关解答：选D。快速排序的递归次数与初始数据的排列次序有关；快速排序的递归次数与每次划分后得到的分区处理顺序无关。

180例题3对给定的排序码序列110,119,007,911,114,120,122进行基数排序，则第2趟分配收集后得到的排序码序列是A.007,1105119,114,911,120,122B.007,110,119,114,911,122,120C.007,110,911,114,119,120,122D.1105120,911,122,114,007,119解答：选C。基数排序第1趟按个位进行分配与收集，第2趟按十位进行分配与收集，且要求它们的排序都是稳定的。第2趟的排序结果应按十位有序排列，十位数字相同时按照个位有序排列。

181例题4设线性表每个元素有两个数据项(kl,k2),排序规则如下：先着kl,kl值小由七品，大的在后；在kl值相同的情况下，再看k2,k2值小的在前，大的在后。满足这种要求的排序方法是A.先按kl值进行直接插入排序，再按k2值进行简单选择排序B.先按k2值进行直接插入排序，再按kl值进行简单选择排序C.先按kl值进行简单选择排序，再按k2值进行直接插入排序D.先按k2值进行简单选择排序，再按kl值进行

182直接插入排序

183解答：选D。这是多排序码排序问题，一般采用基数排序。基数排序先对k2排序，再对kl排序。为得到在kl相等情况下k2从小到大有序，要求对kl排序的算法是稳定的。因此可选对k2排序用简单选择排序，对kl排序用直接插入排序。