插入排序的设计与实现.docx
- 文档编号:3542273
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:16
- 大小:298.66KB
插入排序的设计与实现.docx
《插入排序的设计与实现.docx》由会员分享,可在线阅读,更多相关《插入排序的设计与实现.docx(16页珍藏版)》请在冰点文库上搜索。
插入排序的设计与实现
课程设计任务书
学生姓名:
专业班级:
件0802班
指导教师:
夏红霞工作单位:
计算机科学与技术学院
题目:
插入排序的设计与实现
课程设计要求:
1、熟练掌握基本的数据结构;
2、熟练掌握各种算法;
3、运用高级语言编写质量高、风格好的应用程序。
课程设计任务:
1、系统应具备的功能:
(1)随机产生1000个整数
(2)实现直接插入排序、二路插入排序、二分插入排序和SHELL排序
(3)比较各种插入排序的优劣
2、数据结构设计;
3、主要算法设计;
4、编程及上机实现;
5、撰写课程设计报告,包括:
(1)设计题目;
(2)摘要和关键字;
(3)正文,包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等;
(4)结束语;
(5)参考文献。
时间安排:
2010年7月5日-9日(第19周)
7月5日查阅资料
7月6日系统设计,数据结构设计,算法设计
7月7日-8日编程并上机调试
7月9日撰写报告
7月10日验收程序,提交设计报告书。
指导教师签名:
2010年7月4日
系主任(或责任教师)签名:
2010年7月4日
设计题目插入排序的设计与实现
摘要:
该程序直接实现了产生1000个随机数,并对其进行4种排列的功能
关键字:
随机数直接插入排序二分排序二路排序SHELL排序
一引言:
在各行各业中,大规模的数据处理会经常出现,对数据进行一定规律的排序有利于更方便地对数据进行处理,方便人们处理实际问题。
更好的排序方法可以节省更多的工作时间,无疑可以大大提高实际生产的效率
二需求分析:
对于大量数据的分析与处理,更好的排序方法会大大提高效率,节省工作时间
三数据结构设计:
主要为顺序表
四算法设计:
#include
#include
#include
#include
usingnamespacestd;
constintN=1000;
#defineElemTypeint
//以下为直接插入排序
voidinsertsort(ElemTypeR[],intn)
{
inti,j;
for(i=2;i<=n;i++)
{
R[0]=R[i];
j=i-1;
while(R[0] { R[j+1]=R[j]; j--; } R[j+1]=R[0]; } } //以下为二分插入排序 voidBinaryInsertSort(ElemTypeR[],intn) { inti,j,low,high,mid; for(i=2;i<=n-1;i++) { R[0]=R[i]; low=1; high=i-1; while(low<=high) { mid=(low+high)/2; if(R[0] high=mid-1; else low=mid+1; } for(j=i-1;j>=high+1;--j) R[j+1]=R[j]; R[high+1]=R[0]; } } //以下为SHELL排序 voidShellSort(ElemTypeR[],intn) { inti,j; for(intd=n/2;d>=1;d/=2)//d表示增量大小,增量每次整除二,第一次为n/2 { for(i=d;i {//对每个元素直接插入到相应子序列的序列表中 ElemTypetemp=R[i];//将待插入对象暂存temp for(j=i-d;j>=0;j-=d) {//在组内向前顺序进行比较和移动 if(temp>R[j]) R[j+d]=R[j]; else break; } R[j+d]=temp; } } } //以下为二路插入排序 intmy_sort(ElemTypeR[],intn) { intfirst,final;//头尾指针 intcache[128];//中转站 inti,j,k=0;//i,j循环变量k计数器 for(i=0;i { if(0==i) { first=0; final=0; cache[0]=R[0]; } else { if(R[i]>=cache[final]) { final++; cache[final]=R[i]; k++; } elseif(R[i]<=cache[first]) { if(first==0)first=n; first--; cache[first]=R[i]; k++; } else { for(j=first;R[i]>cache[j];) { if(0==j) cache[n-1]=cache[0]; else cache[j-1]=cache[j]; k++;j++; if(j==n)j=0; } if(0==first)first=n-1; elsefirst--; if(0==j)j=n; cache[j-1]=R[i]; k++; } } } for(i=first,j=0;j { R[j]=cache[i]; i++; if(i==n)i=0; } returnk; } //输出数组中的元素 voidprint(ElemTypeR[],intn) { for(inti=1;i<=n-1;i++) { if(i%10==0){cout< cout< } cout< } intmain() { charch; //doubledifftime(time_ttime2,time_ttime1); ElemTypeR[N],T[N]; time_tt1,t2; doublett1,tt2,tt3,tt4; srand(time(0)); for(inti=0;i<=N-1;i++) T[i]=rand();//产生随机数 print(T,N);//输出随机数 cout<<"直接插入排序开始: (Y/N)"; cin>>ch; if(ch=='Y') { for(inti=0;i R[i]=T[i]; t1=time(NULL);//直接插入排序开始前的时间 insertsort(R,N); t2=time(NULL);//直接插入排序结束后的时间 tt1=difftime(t2,t1);//直接插入排序所花费的时间 print(R,N); } cout<<"二分插入排序: (Y/N)"; cin>>ch; if(ch=='Y') { for(inti=0;i R[i]=T[i]; t1=time(NULL); BinaryInsertSort(R,N); t2=time(NULL); tt2=difftime(t2,t1); print(R,N); } cout<<"SHELL排序开始: (Y/N)"; cin>>ch; if(ch=='Y') { for(inti=0;i R[i]=T[i]; t1=time(NULL); ShellSort(R,N); t2=time(NULL); tt3=difftime(t2,t1); print(R,N); } cout<<"二路插入排序: (Y/N)"; cin>>ch; if(ch=='Y') { for(inti=0;i R[i]=T[i]; t1=time(NULL); BinaryInsertSort(R,N); t2=time(NULL); tt4=difftime(t2,t1); print(R,N); } cout<<"直接插入排序花费的时间为: "< cout<<"二分插入排序花费的时间为: "< cout<<"SHELL排序花费的时间为"< cout<<"二路插入排序花费的时间为: "< system("pause"); } 五程序运行结果: 图1 首先产生1000个随机数并询问是否进行直接插入排序(注: 由于1000个数据较多,截图并未全部显示,下同) 输入“Y”后按下回车进行下一步 图2 得出直接排序结果并询问是否进行二分插入排序 再输入“Y”按回车进行二分插入排序: 图3 二分插入排序结果 进行SHELL排序: 图4 SHELL排序结果 二路插入排序结果,并得出运行时间: 图5 六不足之处 由于程序自身的对运行时间的计算算法存在问题,以及计算机在对时间进行计算时,对较短的时间全部忽略为0,导致最终运算结果所有排序方法所得结果皆为0 七设计体会 我在制作这个程序时,本来准备采取书上的算法,后来为了更好地嵌入程序,将其改为了纯数组的方法。 在写程序的过程,由于一些细节问题处理不当,导致开始调试时出现了问题,尤其是对于循环条件的把握,进行了多次修改,达到成功运行。 经过这些时日的设计,调试与运行,很好的锻炼了我的编程能力,主要是经过对实际问题的编程训练,大大拓宽了我的思路,不再拘泥于书上的一些算法,可以自己总结比较一些其他的算法,对自己编程思想的锻炼起了很大的作用。 亦提升了自己对计算机的兴趣,对将来的更深远的学习无疑是有利的。 八结束语 本程序就数据的多种插入排序方法进行了直接实现,通过不同的方法达到了排序的目的,但由于自身问题已经程序运行较快等问题,在不同排序方法的比较上略有欠佳。 参考文献 严蔚敏吴伟民: 《数据结构》清华大学出版社 谭浩强: C++程序设计
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 插入 排序 设计 实现