上机实验一
一、实验题目
用分治法进行归并分类
二、 算法介绍
将A(1),......,A(n)均分成两个集合，在对每个集合单独分类，然后将已分类的两个序列归并成一个含n个元素的分好类的序列；merge（）函数负责把两个已分类集合归并在一起，mergesort（）函数通过使用递归和调用merge（）函数完成该处理过程
三、程序流程图：
说明：A[N]、B[N]是全程数组，A[] 存放待分类的元素，B[]是辅助数组
归并分类算法mergesort（递归算法）的具体扩展：
说明：入口参数：待分类集合A(low:high)的头和尾元素位置low、high
merge函数的具体扩展：//使用辅助数组归并两个已分类的集合
说明：入口参数：集合A(low:high)的头和尾元素位置low、high及该集合的分割点（二分）
2
四、源程序及实验结果
程序代码如下： #include
int A[N],B[N]; //A[N]、B[N]是全程数组，A[] 存放待分类的元素，B[]是辅助数组 void merge(int low,int mid,int high) //使用辅助数组归并两个已分类的集合
/*数组A（low：high）包含两个放在A(low:mid)和A(mid+1:high)中的已分类的子集合 *此函数是使用一个辅助数组B（low：high）将这两个已分类的集合归并成一个集合，并存放到A（low：high）中 */
{ int h,k,i,j; h=low; i=low; j=mid+1;
while(h<=mid&&j<=high) //当两个集合都没取尽时 { if(A[h]<=A[j]) { B[i]=A[h]; h++; }
else { B[i]=A[j]; j++; } i++; }
//处理剩余的元素
if(h>mid) /*A(low:mid)数组取完时，将A(mid+1:high)中剩余元素依次复制到数组B(low： high)尾部*/ { for(k=j;k<=high;k++) { B[i]=A[k]; i++; } }
else for(k=h;k<=mid;k++) /*A(mid+1:high)数组取完时，将A(low:mid)中剩余元素依次复制 到数组B(low：high)尾部*/
{ B[i]=A[k]; i++; }
for(k=low;k<=high;k++) //将已归并的集合复制到A中 { A[k]=B[k]; }
3
}
void mergesort(int low,int high) //归并分类
/*将本集合二分为两个集合，再递归调用merge（）函数对每个集合单独分类并将已分类的 *两个序列归并为一个分好类的序列 */
{ int mid;
if(low { mid=(int)floor((low+high)/2); //求这个集合的分割点 mergesort(low,mid); //将一个子集合分类 mergesort(mid+1,high); //将另一个子集合分类 merge(low,mid,high); //归并两个已分类的子集合 } } void main() { int i=1,cx; //cx中存放待排序元素的个数 printf(\ //显示提示信息 scanf(\ //输入待排序元素的个数 printf(\ for(i=1;i<=cx;i++) //输入待排序的各个元素的值，并存放到集合A中 { scanf(\ } mergesort(1,i-1); //调用归并分类算法对数组A（1：i-1）进行归并排序 printf(\ for(i=1;i<=cx;i++) //输出进行归并排序后的集合A { printf(\ } getch(); } 运行结果如下图：(运行结果与理论结果一致) 五、结果分析 运行源程序后，先输入待排序元素的个数，回车。再分别输入打乱的元素的值序列，回车，显示按升序排列的元素值序列。 最坏情况：输入数据按非增次序排列,每次内层while循环执行j次（j=2,3,…, n)。则有，Ω(n(n+1)/2-1)= Ω(n2); 4 最好情况：输入数据已按非降序排列，不进入while循环，则最好情况下计算时间为Ω(n)。 上机实验二 一、实验题目 用分治法进行快速分类 二、算法介绍 在集合A(1:n)中选一元素t=A[s]，然后将其它元素重新排列，使A(1:n)中所有在t以前出现的元素都小于或等于t，而在t后出现的元素都不小于t,元素t为划分元素，快速分类就是通过反复对产生的集合进行划分来实现的。 三、程序流程图 说明：A[1024]是全程数组，其中存放待分类的元素 快速分类算法quicksort（递归算法）的具体扩展如下： 说明：入口参数:集合A（p:q）的p、q 5