数据结构中归并排序的设计与实现.doc

课程设计任务书 学生姓名： 专业班级： 指导教师： 工作单位： 题 目: 归并排序的设计与实现 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1、系统应具备的功能： （1）输入一组数,用递归和非递归程序实现归并排序 （2）分析归并排序的复杂度 （3）将归并排序的思想用于外部排序中 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字（中文和英文）； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等； （4）结束语； （5）参考文献。 时间安排： 2010年元月10日－14日 （第19周） 元月10日 查阅资料 元月11日 系统设计，数据结构设计，算法设计 元月12日-13日 编程并上机调试 元月14日 撰写报告 元月15日 验收程序，提交设计报告书。 指导教师签名： 2010年元月10日 系主任（或责任教师）签名： 2010年元月10日 归并排序的设计和实现 摘要:该程序主要由五个部分组成：把一组待排的数据信息放在结构体里，2－路归并排序，对数组作一趟归并排序，对数组作归并排序，主函数 。 Abstract: The program mainly consists of five parts: the a row of data to be placed on structure, the 2 - way merge sort, for a trip to the array?Merge sort, merge sort on the array as the main function. 关键字:模型化, 2－路归并, 一趟归并, 归并 Keywords: modeling, 2 - way merge, a trip to merge, merge? 0.引言 归并排序是一种稳定的内部排序，“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。无论是顺序存储结构还是链表存储结构，都可在O（m+n）的时间量级上实现。利用归并的思想容易实现排序。 2—路归并排序：假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到不小于n/2整数个长度为2或1的有序子序列；再两两归并,……,如此重复，直至得到一个长度为n的有序序列为止。 1.算法把握 1.1归并排序算法的具体分析 咋一看，归并排序时一种“费力不讨好”的排序方法，因为最后一趟始终要对整个序列进行排序，这会使的前几趟的排序似乎是在做无用功，其实不然。对初始关键字两两分组并进行组内排序后，在下一次处理中，并不是简单地在组容量扩大一倍的基础上重新排序，而是把上一趟已经排好序的两组数组重新合并成一个新的有序组。这个把两个有序组合并到一个新的有序组的过程要比单独排序快得多。归并排序的核心操作时合并有序组。对于最开始的两两分组，也可以看成是两个只含有1个关键字的组进行合并。 1.2 除了核心的合并操作外，需要先把序列进行分组，每次组容量减半，直到组内只有一个关键字为止，再对组进行合并，直到所有关键字都属于一组为止。实际上，分组采用递归的方法更加方便。 2.需求分析 (1)通过建立一个结构体，用来存放数据信息，包括数据的个数，本身记录。 (2)2－路归并排序的算法，实现两两归并。 (3)主函数初始化数据，选择归并排序的方法及打印数据结果。 3.数据结构设计 用结构体存储待排的数据。 #includeiostream.h #define MAX 100 /*定义MAX是最大的允许输入数字个数*/ typedef struct { int n; /* n为文件中的记录个数，nMAXNUM */ int data[MAX]; }lqlist; 4.算法设计 4.1 2-路归并排序的非递归算法 //将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] void merge(RcdType SR[],RcdTypeTR[],int i,int m,int n) { for(j=m+1,k=I;i=mj=n;k++) {