[科普中国]-归并分类

定义

分治法的思想是将一个难以直接解决的问题分解成容易求解的子问题，以便各个击破、分而治之。利用分治法求解问题的过程是，将整个问题分解成若干子问题后分而治之；如果分解得到的子问题仍然不易求解，可反复使用分治策略将这些子问题分成更小的子问题，直至产生出容易求解的子问题，最后逐步合成这些子问题的解，以得到问题的解。归并分类就是分治法中的一种算法。

分类分类问题就是按照关键值的一种排序关系，如大于关系。如根据关键值的不增或不减次序，把文件中的各种记录一次排列起来，可使得一个无序文件变成有序文件。

文件的物理表示法（1）向量表示。要分类的初始文件的各个记录，按其自然顺序存放在连续一块内存空间中。

（2）链表表示。要分类文件的每个记录作为链表结构的一个结点，并按照各个记录的原始次序链接起来。

（3）地址向量。将要分类文件的各个记录存贮到内存的各块中，这些存贮块的地址是不连续的。按各记录的原始次序，将这些块的首地址依次存如内存的一块连续单元中，这样由各块的首地址组成一个向量，这个向量就是地址向量。

分类技术分类技术根据记录所处的环境不同而分为内部分类和外部分类两大类。内部分类是指分类期间全部数据都存放在内存的分类方法；外部分类则是针对大量记录而言的，分类期间，全部记录已不能同时存放在内存，需要记录在内、外存之间移动。常见的几种内部分类技术包括：

（1）计数分类。主要思想是对于每个记录，都要计算文件中其它记录的关键字值有多少是大于该记录的关键字值，从而找到这个记录的正确分类位置，这是一种效率较低的分类方法。

（2）选择分类。以教师对学生的考试成绩按分数进行分类为例，首先找到成绩最好的试卷，并把它出来，作为新一叠试卷的头一份试卷，然后在剩余的试卷中再选出分数最高的试卷，并把它放在新的那叠试卷之上，如此继续下去，最后就完成了按分数高低分类这些试卷，这个过程即为选择分类。

（3）冒泡分类。每一次仅进行相邻两个记录的比较，使位于文件底部的合适记录一下子放到文件的顶部，而只能每次向上移动一步，缓慢升到顶部，因此一个文件的全部分类是由多次重复比较相邻记录的关键字而实现的。

（4）线性插入；将原始文件顺序的第二个记录的关键字与第一个记录的关键字进行比较后，把第二个记录放到一个相对于第一个记录的合适位置。然后再取第三个记录于前二个记录进行比较关键字，并把第三个记录放到相对于前两个记录的合适位置，如此继续下去，最后完成分类。

（5）折半插入，它是线性插入的改进。

（6）归并分类，两个分类文件的归并问题和k个分类文件的归并问题。

算法基本思想设待分类的数据序列包含n个数据元素。

（1）先把该序列分成n个子序列，每个子序列只包含一个数据，显然，这n个子序列都是有序的；

（2）将这n个子序列两个一组，可分成（n+1）/2（取整）个互不相交的组；

（3）对每个组的2个子序列进行二路归并，总共得到（n+1）/2个有序子序列；

（4）对这些有序子序列两个一组，对每个组进行二路归并。

如此继续下去，最后得到一个有序的结果序列。1

程序# include "sort.h"getdata(int a[]);void output(int a[],int first,int last);void mersort(int a[],int b[],int s,int t);void merge(int a[],int l,int m,int n,int c[]);void main(){ int arr[MAX],arrb[MAX],n; n=getdata(arr); output(arr,l,n); printf("\n"); mersort(arr,arrb,l,n); output(arrb,l,n); printf("\n");}void mersort(int a[],int b[],int s,int t){ int i; if(s==t)return; else{ mersort(a,b,s,(s+t)/2); mersort(a,b,(s+t)/2+1,t); mersort(a,s,(s+t)/2,t,b); for(i=s;i