数据结构归并排序.doc

数据结构 归并排序
归并排序
实验题目:归并排序
实验要求:对输入的一组数据利用归并排序算法进行排序并输出
1 需求分析
本实验要求对输入的一组数据利用归并排序算法进行排序并输出。
归并排序是利用归并过程的算法。所谓归并，是指将若干个已排好序的表合并成一个有序表。而对两个有序表的归并，称为二路归并。对于一个表进行归并排序，可以理解为对该表进行了多次二路排序。因此，本实验的核心即转化为设计二路归并算法，并对其进行递归。
1. 输入形式:键盘输入一组数据
输入值范围:整数数组
2. 输出形式: 有序的整数数组
3. 程序功能:对一组数据进行排序
4. 测试
输入一组数据进行归并排序
数据个数:10
输入10个数进行归并排序:
23 4 56 67 34 2 57 8 90 1
1 2 4 8 23 34 56 57 67 90
2 设计概要
问题分析
本实验的核心是设计二路归并算法，并基于二路归并设计对于一个表的归并算法。 1. 二路归并排序
数据输入为存储数据的数组data[MAX]。同时设置数据接受数组B[MAX]。 对于数组中两段，分别标记其首元素下表为h，j，设数据接受数组B[MAX]的下标为i。 分别读取data[h],data[j]进行比较，将其中较小者存入数组B，同时较小数组段的下标(i/j)自加1.
循环上述过程直至两端数组均读取到最终的元素。
结束循环后，将存储在数组B中的元素逐一复制到数组A中。如此即完成了二路归并。
2. 线性表归并排序
由问题分析中所述，对线性表的排序即是多次运用二路归并排序算法。
A B
A1 A2
A11 A12
如图所示，对于线性表，若A、B 内部有序，则直接进行二路归并排序即可得到有序排列。
若A内部无序，则需将A拆分。若拆分后A1内部无序，则需要对A1作进一步的拆分。拆
分过程需要持续到数组任一一段内部均是有序，则对拆分的数组进行每两段的二路归并排
序，由此可以得到整个有序的线性表。
, 基于以上分析，我们可以利用递归思想编写算法: , 归并当前数组
, 拆分数组，递归归并前半部分，递归归并后半部分
程序模块
程序包含三个主要模块:主函数、归并函数、输出。 调用关系如下:
初始化
查找中点
主函数 归并算法 前部分归并
后部分归并
输出
3 详细设计

void main()
{
int i;
/*建立一数组进行归并排序*/
printf("输入一组数据进行归并排序\n");
Init();
MERGESORT(0,MAX-1);
for(i=0;i<MAX;i++)
printf("%d ",A[i]);
}
2. 归并函数
归并函数的核心是二路归并算法。根据问题分析中的叙述，我们设计算法流程如下:
根据算法流程，我们编写出源代码:
1)二路归并算法
void MERGE(int low,int mid,int high)//归并组合 {
int h,k,i,j;
int B[MAX];//组合比较后形成新的数组
h=low;