c归并排序与堆排序的课程设计

1 学号 1608220203 《C语言程序设计》 课程设计报告

题目： 归并排序与堆排序 专业： 计算机科学与技术 班级： 16级网工3班 姓名： 代应豪 指导教师： 程庆 成绩：

计算机学院 2017 年 4月 27 日

2016-2017学年 第二学期 2

目录 1归并排序的设计内容及要求.........................................3 1.1设计内容.....................................................3 1.2设计任务及具体要求...........................................3 2 归并排序概要设计................................................4 2.1该系统的功能简介.............................................4 2.2 总体程序框图.................................................5 3 归并排序设计过程或程序代码.......................................6 3.1各个模块的程序流程图及介绍...................................6 3.2对关键代码加以分析说明.......................................7 4归并排序程序调试分析............................................14 5堆排序的基本简介................................................15 5.1 堆排序的框架图..............................................16 6堆排序的算法描述.................................................19 6.1 堆排序的算法介绍............................................23 7堆的原理分析.....................................................23 8小结.............................................................24 9 附程序运行结果图................................................24 3

1 设计内容及要求 1.1设计内容 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并过程的内容为:比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]

1.2设计任务及具体要求 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置； 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤3直到某一指针达到序列尾； 将另一序列剩下的所有元素直接复制到合并序列尾 2 概要设计

2.1系统的功能简介

归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一

个序列的操作。 4

如 设有数列{6，202，100，301，38，8，1} 初始状态： [6] [202] [100] [301] [38] [8] [1] 比较次数 i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4 i=3 [ 1 6 8 38 100 202 301 ] 4 总计： 11次 算法复杂度 时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。 空间复杂度为 O(n) 比较操作的次数介于(nlogn) / 2和nlogn - n + 1。 赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n) 归并排序比较占用内存，但却效率高且稳定的算法。 Pascal中的归并算法 所谓归并排序是指将两个或两个以上有序的数列（或有序表），合并成一个仍然有序的数列（或有序表）。这样的排序方法经常用于多个有序的数据文件归并成一个有序的数据文件。归并排序的算法比较简单。

2.2.总体程序框图 5

3 归并排序设计过程或程序代码 3.1各个模块的程序流程图及介绍 归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。

如 设有数列{6，202，100，301，38，8，1} 初始状态： [6] [202] [100] [301] [38] [8] [1] 比较次数 i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4 i=3 [ 1 6 8 38 100 202 301 ] 4 总计： 11次

3.2对关键代码加以分析说明 时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。 空间复杂度为 O(n) 比较操作的次数介于(nlogn) / 2和nlogn - n + 1。 赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n) 归并排序比较占用内存，但却效率高且稳定的算法 6

4归并排序程序调试分析 （1）假设已经有两个有序数列，分别存放在两个数组s，r中；并设i，j分别为指向数组的第一个单元的下标；s有n个元素，r有m个元素。

（2）再另设一个数组a，k指向该数组的第一个单元下标。 （3）算法分析（过程）： procedure merge(s,r,a,i,j,k); begin i1:=i; j1:=j; k1:=k; while (i1if s[i1]<=r[j1] then begin a[k]:=s[i1]; i1:=i1+1; k:=k+1; End else begin a[k]:=r[j1]; j1:=j1+1; k:=k+1; end; 7

while i1<=n do begin a[k]:=s[i1]; i1:=i1+1; k:=k+1; end; while j1<=m d while j1<=m do begin a[k]:=r[j1]; j1:=j1+1; k:=k+1; end; end; 完整的C++源代码 #include void Merge(int r[],int r1[],int s,int m,int t) { int i=s;int j=m+1;int k=s; while(i<=m&&j<=t) { if(r<=r[j])r1[k++]=r[i++]; else r1[k++]=r[j++]; 8

} if(i<=m) while(i<=m) r1[k++]=r[i++]; else while(j<=t) r1[k++]=r[j++]; for(int l=0;l<8;l++) r[l]=r1[l]; } void MergeSort(int r[],int r1[],int s,int t) { if(s==t)r1[s]=r[s]; else { int m=(s+t)/2; MergeSort(r,r1,s,m); MergeSort(r,r1,m+1,t); Merge(r1,r,s,m,t); } } void main() { int r[8]={10,3,5,1,9,34,54,565},r1[8]; MergeSort(r,r1,0,7); for(int q=0;q<8;q++) 9

cout<<" "<} end; 归并排序有两种实现方法：自底向上和自顶向下，算法实现如下：

1.自底向上算法 #include #include void Merge(int *a,int low,int mid,int high) { int i = low,j = mid + 1,k = 0; int *temp = (int *)malloc((high - low + 1)*sizeof(int)); while(i <= mid && j <= high) a < a[j] ? (temp[k++] = a[i++]):(temp[k++] = a[j++]); while(i <= mid) temp[k++] = a[i++]; while(j <= high) temp[k++] = a[j++]; memcpy(a + low,temp,(high -low + 1)*sizeof(int)); free(temp); } void MergeSort(int *a,int n) { int length;