各种排序算法时间性能的比较

实训报告实训题目：各种排序算法时间性能的比较学院：计算机科学与技术学院专业：软件工程班级：142学号：69学生姓名：莫磊指导教师：蔡丽2016年3月15日一、实训目的及要求数据结构是计算机课程的一门重要的基础课，它的教学要求大致有三个重要方面：其一就是让学生学会分析研究计算机加工的数据对象的特性，以便为数据选择适当的物理结构和逻辑结构；其二，根据结构，选择适当的算法，并初步掌握算法的时间分析和空间分析；其三，学习复杂的程序设计。本综合实训利用VisualStudio2008集成编程环境为实践工具，通过上机实践培养学生分析具体问题、解决实际问题的能力，训练和培养学生的数据抽象能力和程序设计的能力。数据结构是一门实践性较强的课程，以培养学生的数据抽象能力和程序设计的能力为目的。在实训时应注重培养学生的实际操作能力。本综合实训安排了18学时的实验课时，具体要求如下：1.学习和理解每个实训题目的基本理论和方法；2.掌握每个实验的实现步骤和关键技术；3.准备好实验所需要的资源和文档；4.上机实现程序，得到通过调试的正确程序。5.根据每个实验的不同要求，完成实验报告的word文档。二、实训环境WindowsXPVisualStudio2013三、实训内容(1)设计并实现上述各种排序算法；(2)产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；(3)产生随机的初始排列分别调用上述排序算法，并比较时间性能。（4）对各种排序方法（直接插入排序、希尔排序、起泡排序、直接选择排序）的时间性能进行比较。四、算法描述及实训步骤上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次数和移动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法的目的。五、总结及心得体会直接选择排序算法是对冒泡排序的改进，这种方法是在参加排序数组中找出最小（或最大）的数据元素，使它与第一个元素中的数据相互交换位置然后再在余下的元素中找出最小（或最大）的数据元素与第二个元素中的元素交换位置，以此类推直到所有元素成为有序序列。六、实训结果七、源代码：#include#include#include//正序希尔排序voidxiEr(intnum[],intn,int&no,int&r){intitem;inti,j,d;for(d=n/2;d=1;d=d/2){for(i=d;in;i++){item=num[i];j=i-d;while((j=0)&&(itemnum[j])){num[j+d]=num[j];j=j-d;r=r+1;}num[j+d]=item;no=no+1;}}//printf(\n);//for(intx=0;xn;x++){//printf(%d\t,num[x]);//}}//逆序希尔排序voidxiErUp(intnum[],intn,int&no,int&r){intitem;inti,j,d;for(d=n/2;d=1;d=d/2){for(i=d;in;i++){item=num[i];j=i-d;while((j=0)&&(itemnum[j])){num[j+d]=num[j];j=j-d;r=r+1;}num[j+d]=item;no=no+1;}}}//正序冒泡排序voidMaoPao(intnum[],intn,int&no,int&r){boolflag;inttest;for(inti=1;in;i++){flag=true;for(intj=n-1;j=i;j--){if(num[j]num[j-1]){test=num[j];num[j]=num[j-1];num[j-1]=test;flag=false;r++;}no++;}if(flag){return;}}}voidMaoPaoUp(intnum[],intn,int&no,int&r){boolflag;inttest;for(inti=1;in;i++){flag=true;for(intj=n-1;j=i;j--){if(num[j]num[j-1]){test=num[j];num[j]=num[j-1];num[j-1]=test;flag=false;r++;}no++;}if(flag){return;}}}voidChaRu(intnum[],intn,int&no,int&r)//直接插入排序{//:比较次数，r:移动次数。inti,j,x;for(i=1;in;i++){no++;x=num[i];j=i-1;while((j=0)&&(xnum[j])){r++;num[j+1]=num[j];j--;}//顺序比较和移动num[j+1]=x;}}voidChaRuUp(intnum[],intn,int&no,int&r)//直接插入排序{//:比较次数，r:移动次数。inti,j,x;for(i=1;in;i++){no++;x=num[i];j=i-1;while((j=0)&&(xnum[j])){r++;num[j+1]=num[j];j--;}//顺序比较和移动num[j+1]=x;}}voidXuanZe(intnum[],intn,int&no,int&r)//直接选择排序/:比较次数,r:移动次数{intx;inti,j,k;for(i=1;i=n-1;i++){k=i-1;for(j=i;j=n-1;j++){no++;if(num[j]num[k])k=j;}if(k!=i-1){r++;x=num[i-1];num[i-1]=num[k];num[k]=x;}}}voidXuanZeUp(intnum[],intn,int&no,int&r)//直接选择排序/:比较次数,r:移动次数{intx;inti,j,k;for(i=1;i=n-1;i++){k=i-1;for(j=i;j=n-1;j++){no++;if(num[j]num[k])k=j;}if(k!=i-1){r++;x=num[i-1];num[i-1]=num[k];num[k]=x;}}}voidShuChu(intnum[],intn,intno,intr,charname[]){printf(===============输出%s排序后数据如下==============\n\n,name);for(intx=0;xn;x++){printf(%d\t,num[x]);}printf(\n比较的次数为:%d\t移动的次数为:%d,no,r);printf(\n===========================================================\n\n);}intmain(){intnum[100];intn=100;intno1,no2,no3,no4;intr1,r2,r3,r4;intno11,no22,no33,no44;intr11,r22,r33,r44;charname1[]=希尔正序;charname11[]=希尔逆序;charname2[]=冒泡正序;charname22[]=冒泡逆序;charname3[]=直接插入正序;charname33[]=直接插入逆序;charname4[]=直接选择正序;charname44[]=直接选择逆序;intitem1[100];intitem2[100];intitem3[100];intitem4[100];intitem22[100];intitem33[100];intitem44[100];no4=no3=no2=no1=0;r4=r3=r2=r1=0;no44=no33=no22=no11=0;r44=r33=r22=r11=0;printf(============初始的随机数据如下===========\n\n);for(inti=0;in;i++){num[i]=rand()%100;printf(%d\t,num[i]);}for(intx=0;xn;x++){item1[x]=num[x];item2[x]=num[x];item3[x]=num[x];item4[x]=num[x];item22[x]=num[x];item33[x]=num[x];item44[x]=num[x];}xiEr(num,n,no1,r1);ShuChu(num,n,no1,r1,name1);xiEr(item1,n,no11,r11);ShuChu(item1,n,no11,r11,name11);MaoPao(item2,n,no2,r2);ShuChu(item2,n,no2,r2,name2);MaoPaoUp(item22,n,no22,r22);ShuChu(item22,n,no22,r22,name22);ChaRu(item3,n,no3,r3);ShuChu(item3,n,no3,r3,name3);ChaRuUp(item33,n,no33,r33);ShuChu(item33,n,no33,r33,name33);XuanZe(item4,n,no4,r4);ShuChu(item4,n,no4,r4,name4);XuanZeUp(item44,n,no44,r44);ShuChu(item44,n,no44,r44,name44);printf(===========================================================\n);printf(===========================================================\n);printf(所有排序的比较次数和移动次数如下：\n\n);printf(%s:\t比较次数为：%d移动次数为:%d\n,name1,no1,r1);printf(%s:\t比较次数为：%d移动次数为:%d\n,name1,no11,r11);printf(%s:\t比较次数为：%d移动次数为:%d\n,name2,no2,r2);printf(%s:\t比较次数为：%d移动次数为:%d\n,name22,no22,r22);printf(%s:\t比较次数为：%d移动次数为:%d\n,name3,no3,r3);printf(%s:\t比较次数为：%d移动次数为:%d\n,name33,no33,r33);printf(%s:\t比较次数为：%d移动次数为:%d\n,name4,no4,r4);printf(%s:\t比较次数为：%d移动次数为:%d\n,name44,no44,r44);printf(\n===========================================================\n);getchar();return0;}