1、 1 C语言程序设计语言程序设计 课程设计报告课程设计报告 题目：题目： 归并排序与堆排序归并排序与堆排序 专业：专业： 计算机科学与技术计算机科学与技术 班级：班级： 姓名：姓名： 指导教师：指导教师： 成绩：成绩： 计算机学院计算机学院 2017 2017 年年 4 4 月月 27 27 日日 2 目录目录 1 1 归并排序的设计内容及要求归并排序的设计内容及要求.3.3 1.11.1 设计内容设计内容33 1.21.2 设计任务及具体要求设计任务及具体要求3 3 2 2 归并排序概要设计归并排序概要设计44 2.12.1 该系统的功能简介该系统的功能简介.4.4 2.2 2.2 总体程序
2、框图总体程序框图.5.5 3 3 归并排序设计过程或程序代码归并排序设计过程或程序代码.6.6 3.13.1 各个模块的程序流程图及介绍各个模块的程序流程图及介绍.6.6 3.23.2 对关键代码加以分析说明对关键代码加以分析说明.7.7 4 4 归并排序程序调试分析归并排序程序调试分析1414 5 5 堆排序的基本简介堆排序的基本简介.15.15 5.1 5.1 堆排序的框架图堆排序的框架图1616 6 6 堆排序的算法描述堆排序的算法描述.19.19 6.1 6.1 堆排序的算法介绍堆排序的算法介绍2323 7 7 堆的原理分析堆的原理分析.23.23 8 8 小结小结2424 9 9 附
3、程序运行结果图附程序运行结果图2424 3 1 设计内容及要求 1.1 设计内容 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 (Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完 全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表 合并成一个有序表，称为二路归并。 归并过程的内容为:比较 ai和 aj的大小，若 aiaj，则将第一个有序表中 的元素 ai复制到 rk中，并令 i 和 k 分别加上 1;否则将第二个有序表中的元素 aj复制到 rk中，并令 j 和 k 分别加上 1，如此循环下去，直到其中一个有序表
4、取完， 然后再将另一个有序表中剩余的元素复制到 r 中从下标 k 到下标 t 的单元。 归并排序的算法我们通常用递归实现，先把待排序区间s,t以中点二分，接着把 左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作 合并成有序的区间s,t 1.2 设计任务及具体要求 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序 列； 设定两个指针，最初位置分别为两个已经排序序列的起始位置； 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指 针到下一位置； 重复步骤 3 直到某一指针达到序列尾； 将另一序列剩下的所有元素直接复制到合并序列尾 2 概要设计
5、 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 -
6、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 2
