数据结构实验-归并排序算法

1、大连理工大学实验预习报告学院（系）： 电信 专业： 班级： 姓 名： 学号： 组： _ 实验时间： 实验室： 实验台： 指导教师签字： 成绩： 实验名称Merge sort一、 实验目的和要求(一)、实验目的Design the merge sort algorithm and implement it in C language设计归并排序算法并于C语言实现。(二)、实验要求Requirements:1) Analyze the time complexity of your algorithm2) Submit the document explaining your algorithm

2、as well as the source code. 要求：1) 分析算法的时间复杂度。2) 提交的文档中说明你的算法和源代码。二、实验原理归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将

3、这二组数据进行排序。如何让这二组组内数据有序了？可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。大连理工大学实验报告学院（系）： 电信 专业： 电创 班级： 1501 姓 名： 陈晓牛津 学号： 组： _ 实验时间： 2017/4/18 实验室： 实验台： 指导教师签字： 成绩： 实验名称Merge sort一、 算法分析归并组合功能:用二分检索查找的方法采用从低部分，高部分进行查找建立一个新的数组，将小的数放入新的数组中。 归并排序功能；利用递归进

4、行排序，先查找中点位置，再对前部分查找，然后后部分，将小的数据放入新的数组二、 关键代码及注释void mergesort(int *a,int left,int right)int mid; if(left right) /* 分组条件 */ mid = (left + right)/2; /* 取中点 */ mergesort(a,left,mid); /* 左边分组 */ mergesort(a,mid+1,right); /* 右边分组 */ partition(left,mid,right); /* 归并函数*/三、 运行结果四、 代码#includeint a=70,66,88,7

5、0,45,90,33,66,70,22,11,90,11,90,11,90,k = 0;int i;void mergesort(int *a, int left, int right);void partition(int left, int mid, int right);int main()printf(要排序的数组为：n); /* 输出要排序的数 */ for(i = 0; ai != NULL; i+) printf(%4d,ai);printf(n); mergesort(a,0,15); /* 归并排序 */ printf(则结果为：n); for(i = 0; ai != NU

6、LL; i+) /* 经过排序之后输出数组a */ printf(%4d,ai);printf(n);void mergesort(int *a,int left,int right)int mid; if(left = m & l mid+1) /* 终止条件为数组元素用尽 */ if(al am) /* 如果左边的小，则将左边的元素赋值给b */ bh+ = al+; else /* 否则将右边元素赋值给b */ bh+ = am+; if(right m) /* 如果右边的元素用完，则将左边的元素全部赋值给数组b，完成一趟排序 */ for(; l mid) /* 如果是左边的用完，则同理将右边的全部赋值给数组b */ for(; m = right; m+) bh+ = am; for(; left = right; left+) /* 完成归并，将数组b复制给数组a, 控制变量尤为重要 */ aleft = bj+;printf