文档介绍：: .
算法设计与分析实验报告
实验名称分治法实现归并排序算法评分
实验日期年月日指导教师
姓名专业班级学号
一 •实验要求
1. 了解用分治法求解的问题：当要求解一个输入规模为 n,且n的取值相当大的问题时，
如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中 1<k < n,而
且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类
问题分治法是十分有效的。
2. 掌握分治法的一般控制流程。
Da nQp,q)
global n , A[1:n]; integer m,p,q; // 1 二piiq^n
if Small(p,q) then return G(p,q);
else m=Divide(p,q); // p <m<q
return Comb in e(Da nC(p,m),Da nC(m+1,q));
en dif
end Da nC
3•实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。
二•实验内容
1. 编程实现归并排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。
2. 输入10组相同的数据，验证排序结果和完成排序的比较次数。
3. 与复杂性函数所计算的比较次数比较。
4. 用表格列出比较结果。
5. 给出文字分析。
三•程序算法

procedure MERGESORT(low, high)
〃A(low ; high)是一个全程数组，它含
有high-low+1 > 0个待排序的元素//
integer low , high ;
if low<high ;
then mid
//
求这个集合的分割点//
将一个子集合排序〃
将另一个子集合排序
归并两个已排序的子集合//
call MERGESORT(low , mid) //
call MERGESORT(mid+1 , high) //
call MERGE(low , mid, high) // en dif
end MERGESORT
归并两个已排序的集合
procedure MERGE(low , mid , high)
//A(low : high)是一个全程数组//
// 辅助数组 B(low ； high)//
integer h ， i， j，k ；
h j low ; i j low ; j j mid+1 ;
while h < mid and j < high do // 当两个集合都没取尽时 //
if A(h) w A(j) then B(i) j A(h) ; h J h+1
else B(i) J A(j) ; j Jj+1
en dif i j i+1
repeat
if h>mid the n
for k jj to high do // 处理剩余的元素//
B(i) j A(k) ; i j i+1
repeat
else for k j h to