题目: 归并排序的设计与实现初始条件：理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法；实践：计算机技术系实验室提供计算机及软件开发环境。
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）输入一组数,用递归和非递归程序实现归并排序；（2）分析归并排序的复杂度；（3）将归并排序的思想用于外部排序中。
2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字；（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等；（4）结束语；（5）参考文献。
时间安排：2007年7月2日－7日（第18周）7月2日查阅资料7月3日系统设计，数据结构设计，算法设计7月4日-5日编程并上机调试7月6日撰写报告7月7日验收程序，提交设计报告书。
指导教师签名： 2007年7月2日系主任（或责任教师）签名： 2007年7月2日归并排序的设计和实现摘要:该程序主要由五个部分组成：把一组待排的数据信息放在结构体里，2－路归并排序，对数组作一趟归并排序，对数组作归并排序，主函数。
关键字:模型化, 2－路归并, 一趟归并, 归并0.引言归并排序是一种稳定的内部排序，“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。
无论是顺序存储结构还是链表存储结构，都可在O（m+n）的时间量级上实现。
利用归并的思想容易实现排序。
2—路归并排序：假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到不小于n/2整数个长度为2或1的有序子序列；再两两归并,……,如此重复，直至得到一个长度为n的有序序列为止。
1.需求分析(1)通过建立一个结构体，用来存放数据信息，包括数据的个数，本身记录。
(2)2－路归并排序的算法，实现两两归并。
(3)主函数初始化数据，及打印数据结果。
2.数据结构设计用结构体存储待排的数据。
#include "stdio.h"#include<stdio.h>#define MAXNUM 100#define TRUE 1#define FALSE 0typedef int DataType;typedef struct{int n; /* n为文件中的记录个数，n<MAXNUM */int record[MAXNUM];} SortObject;3.算法设计3.1 2-路归并排序的非递归算法//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]void merge(RcdType SR[],RcdType&TR[],int i,int m,int n){for(j=m+1,k=I;i<=m&&j<=n;k++){ //将SR中记录由小到大的并入TRif(LQ(SR[i].key,SR[j].key)) TR[k]=SR[i++];else TR[k]=SR[j++];}if(i<=m) TR[k..n]=SR[i..m]; //将剩余的SR[i..m]复制到TRif(j<=n) TR[k..n]=SR[j..n]; //将剩余的SR[i..m]复制到TR}//merge3.2 2-路归并排序的递归形式void Msort(RcdType SR[],RcdType&TR1[],int s,int t){ //将SR归并排序为TRif(s==t) TR1[s]=SR[s];else{m=(s+t)/2; //将平分为SR[s..t]和SR[m+1..t]Msort(SR,TR2,s,m); // 递归的将SR[s..m]归并为有序的TR2[s..m] Msort(SR,TR2,m+1,t); //递归地将SR[m+1..t]归并为有序的TR{m+1..t} Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] }}//mergesort3.3 对顺序表L作归并排序Void mergesort(SqList &L){Msort(L.r,L.r,1,L.length);}//mergesort3.4 非递归形式归并算法void merge(int r[], int r1[], int low, int m, int high){/* r[low]到r[m]和r[m+1]到r[right]是两个有序段 */int i = low, j = m + 1, k = low;while ( i <= m && j <= high ){ /* 反复复制两个段的第一个记录中较小的 */if (r[i] <= r[j] )r1[k++] = r[i++];else r1[k++] = r[j++];}while (i <= m) r1[k++] = r[i++]; /* 复制第一个段的剩余记录 */while (j <= high) r1[k++] = r[j++];/* 复制第二个段的剩余记录 */}3.5 对 r 做一趟归并的算法void mergePass(int r[], int r1[], int n, int length) {int i = 0, j; /* length为本趟归并的有序子段的长度 */while(i + 2*length - 1 < n){ /* 归并长length的两个子段*/merge(r, r1, i, i+length-1, i + 2*length - 1);i += 2*length;}if(i + length - 1 < n - 1) /* 剩下两段，后一段长度小于 length */ merge(r, r1, i, i+length-1, n-1);else /* 将剩下的一段复制到数组r1 */for(j = i; j < n; j++) r1[j] = r[j];}3.6 对整个数据进行归并的算法void mergeSort(SortObject * p ){int record[MAXNUM];int length = 1;int i;while (length < p->n){/* 一趟归并，结果存放在数组record中*/mergePass(p->record, record, p->n, length);length *= 2;/* 一趟归并，结果存回 */mergePass(record, p->record, p->n, length);length *= 2;}}4. 程序实现4.1 主程序main(){int i;SortObject vector = {8, 49,38,65,97,76,13,27,49};clrscr(); /*请屏函数*/printf("The raw numbers is:\n"); /*归并前的数据*/for(i = 0; i < 8; i++)printf("%d ", vector.record[i]);mergeSort(&vector);printf("\n");printf("The sorted numbers is:\n");/*归并后的数据*/for(i = 0; i < 8; i++)printf("%d ", vector.record[i]);getchar();}4.2 程序运行结果在设计此程序的时候，我试图让用户自己输入要排序的数据，但是发现最后的结果是数据并没有排序，所以在程序中固定了要排序的数据。
5.设计体会通过这次实验我也着实又感受了一次编程的乐趣，从中也学到了不少知识。
做程序是一个比较累的工作，特别是当遇到困难时，程序通不过时，真的很令人沮丧。
但是改正一个错误时，那种喜悦心情也很令人期盼，这种心情堪比久旱见甘霖的喜悦。
就是因为有这种令人身心愉悦的可能，我才得以能够整晚不睡来改程序中的不足之处。
编程中有苦有乐，其中的苦乐只有亲身经历才能体会到。
要想做出好的程序，必须做好忍受其间痛苦的准备。
虽然都说“程序＝数据结构＋算法”，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。
我感受最深的一点是：以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。
感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。
但现在编程感觉完全不同了。
在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。
最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。
这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。
这样无形中就提高了自己编写的程序的质量。
另外，我还体会到深刻理解数据结构的重要性。
只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。
了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。
这次实验中我也出现过一些比较困难的地方。
在对数据进行模型化的时候，只用数组不能足以获取数据的信息，必须建立一个结构体。
后来在同学的指点下，意识到自己的错误。
不过收获也很不少。
总之，我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步不断提高的。
6.结束语本程序实现了清屏操作和数据的归并排序，主要是2－路归并排序的过程，程序运行简单易行，可操作性可靠，结果明了。
参考文献[1] 王开铸，俞经善，金虎，李秀坤.《C语言数据结构程序设计》，哈尔滨工业大学出版社，2003年1月[2] 严蔚敏，吴伟名.《数据结构》，清华大学出版社，2001年1月[3]赵仲孟，张蓓.《数据结构》，西北工业大学出版社，2001年9月。