1、沈阳工程学院数据结构与算法实验报告排序沈 阳 工 程 学 院学 生 实 验 报 告（课程名称： 数据结构与算法 ）实验题目： 排序 班 级 学 号 姓 名 地 点 指导教师 实 验 日 期 : 年 月 日一、实验目的1. 掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。2. 深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。3. 了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。二、实验环境Turbo C或是Visual C+三、实验内容与要求实验1归并排序的实现已知关键字序列为1,8,6,4,10,5,3,2,22，请对此序列进行归并排序，并输出
2、结果。实验2要求使用两种不同的排序算法，将指定文件中的字符按行进行插入排序说明：除了使用下面介绍的直接插入排序算法之外，要求再使用一个自己熟悉的排序算法来实现此功能。算法思路【建立文件】建立一个文本文件IN.TXT，输入若干字符串（文件中的数据可自拟），每个串以回车结束。【算法输入】从文件IN.TXT中按行读取字符并存入二维字符数组。【算法输出】将排序后的二维字符数组输出到另一个文本文件OUT.TXT中。【算法要点】先将指定文本文件IN.TXT中的数据按行读入一个二维字符数组；然后对该二维字符数组中的字符按行执行直接插入排序；最后将已排好序的数据按行写入另一个文本文件OUT.TXT 中。直接插
3、入排序是一种最简单的排序方法，它的基本思想是在排序过程中，每次都将无序区中的第一条记录插入有序区中适当的位置，使其仍保持有序。初始时，取第一条记录为有序区，其他记录为无序区。显然，随着排序过程的进行，有序区不断扩大，无序区不断的缩小。最终无序区变为空，有序区中包含了所有的记录，这时排序结束。将无序区第一个记录xi(i=1,2,3,n-1)插入有序区x0xi-1时，可以先在有序区中找到插入位置j(1jn-1)，然后将其后的记录xjxn-1均后移一位，腾出位置j以插入xi。更为有效的方法是将寻找插入位置和移动记录交替进行，即从有序区的后部开始，如果该位置m(m=i-l,i-2,1)的记录大于待插记
4、录，则直接后移一位；待插记录则插入最后空出来的位置上。算法中引入附加的变量k的作用是进入查找循环前，保存xi的副本（记录后移时会冲掉xi）；在while循环中为了防止下标变量越界，可以加入break来自动控制while循环的结束。四、实验过程及结果分析#includestdio.hint num=0;void print_data(int data,int first,int last) int i=0; for(i=0;ifirst;i+) printf( * ); for(i=first;i=last;i+) printf(%3d,datai); for(i=last;i=8;i+) pr
5、intf( * ); printf(n);void merge(int array,int first,int last) /一趟归并 int mid,i1,i2,i3; int temp10; int i,j; mid=(first+last)/2; i1=0;i2=first;i3=mid+1; while(i2=mid&i3=last) if(arrayi2arrayi3) tempi1+=arrayi2+; else tempi1+=arrayi3+; if(i2=mid) while(i2=mid) tempi1+=arrayi2+; if(i3=last) while(i3=las
6、t) tempi1+=arrayi3+; for(i=first,j=0;i=last;i+,j+) arrayi=tempj; print_data(array,first,last);void mergesort(int data,int first,int last) /归并排序 int mid; if(firstlast) mid=(first+last)/2; mergesort(data,first,mid); mergesort(data,mid+1,last); print_data(data,first,last); merge(data,first,last); void
7、main() int a=1,8,6,4,10,5,3,2,22; mergesort(a,0,8);运行结果：#include #include char xx5080 ;int maxline = 0 ; void readtxt(void) ; void selectsort(void); void writetxt(void) ; void main() ; readtxt(); selectsort(); writetxt() ; void readtxt(void) FILE *fp; int i = 0 ; char *p ; fp = fopen(in.txt, r); whi
8、le(fgets(xxi, 80, fp) != NULL) p = strchr(xxi, n) ; if(p) xxip - xxi = 0 ;i+ ; maxline = i ; fclose(fp); void writetxt(void) FILE *fp ; int i ; fp = fopen(out.txt, w) ; for(i = 0 ; i maxline ; i+)fprintf(fp, %sn, xxi) ; fclose(fp) ; void selectsort(void)int n ,i,j,len;char k;for(n=0;nmaxline;n+)len= strlen(xxn);for(i=0;ilen;i+)k=xxni;j=i-1;while(kxxnj)if(j0)break;xxnj+1=xxnj;j-;xxnj+1=k;五、成绩评定优良中及格不及格出 勤内 容格 式创 新效 果总 评指导教师： 年 月 日
