各种内排序算法的实现及性能比较.docx
- 文档编号:4694846
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:29
- 大小:383.93KB
各种内排序算法的实现及性能比较.docx
《各种内排序算法的实现及性能比较.docx》由会员分享,可在线阅读,更多相关《各种内排序算法的实现及性能比较.docx(29页珍藏版)》请在冰点文库上搜索。
各种内排序算法的实现及性能比较
实验报告
(/学年第一学期)
课程名称
数据结构A
实验名称
各种内排序算法的实现及性能比较
实验时间
年
月
日
指导单位
指导教师
学生姓名
班级学号
学院(系)
专业
实验名称
各种内排序算法的实现及性能比较
指导教师
实验类型
上机
实验学时
2
实验时间
一、实验目的和要求
实验目的:
1、理解和掌握各种排序算法。
2、学会比较排序方法的性能。
内容和要求:
1、验证教材中的各种排序算法。
2、分析各种排序算法的时间复杂度。
3、改进教材中的快速排序算法,使得当子集合小于10个元素时改用直接插入排序。
4、使用随机数发生器产生大数据集合,运行上述各排序算法,使用系统时钟测量各算法所需的实际时间,并进行比较。
二、实验环境(实验设备)
硬件:
PC
软件:
Code:
:
Blocks(C++)
三、实验原理及内容
1、核心算法及思路
改进后的快速排序算法:
思路:
在原来快速排序算法的基础上加上一个if语句,当子集集合小于10个元素时改用直接插入排序,即(right-left+1)<10时改用直接插入排序。
代码:
template
voidInsertSort_2(TA[],intleft,intright)//用于改进快速排序的直接插入排序
{
for(inti=left+1;i { intj=i; Ttemp=A[i]; while(j>0&&temp { A[j]=A[j-1]; j--; } A[j]=temp; } } template voidQSort_2(TA[],intleft,intright) { if(left { if((right-left+1)>=10) { inti,j; i=left; j=right+1; do { do{i++;}while(A[i] do{j--;}while(A[j]>A[left]); if(i { Swap(A[i],A[j]); } }while(i Swap(A[left],A[j]); QSort_2(A,left,j-1); QSort_2(A,j+1,right); } else { InsertSort_2(A,left,right); } } } template voidQuickSort_2(TA[],intn)//改进后的快速排序 { QSort_2(A,0,n-1); } 生成数组的函数: 思路: 为了方便检验各个排序的性能,设置生成三种数组——顺序、逆序和随机数组,在生成随机数组中用rand函数来实现。 代码: template T*Produce(intchoose)//生成数组(顺序、逆序、随机) { T*p=newT[N]; switch(choose) { case1: for(inti=0;i { p[i]=i; }break; case2: for(inti=0;i { p[i]=N-1-i; }break; case3: srand(time(NULL)); for(inti=0;i { p[i]=rand()%N; }break; default: cout<<"error! "< } returnp; } 计算各个排序的时间的函数(以计算简单选择排序的时间为例) 思路: 设计计算的时间是数组元素个数为2000、重复进行100次的时间,用clock函数记录时间,time=(double)(finish-start)/CLOCKS_PER_SEC,以此得出时间间隔。 代码: template doubleSelectSort_time(intchoose)//计算简单选择排序的时间 { T*A; srand(time(NULL)); doubletime; clock_tstart,finish; start=clock(); for(inti=0;i<100;i++) { A=Produce SelectSort(A,N); delete[]A; } finish=clock(); time=(double)(finish-start)/CLOCKS_PER_SEC; returntime; } 2、程序流程图: 3、完整代码: #include #include #include #include usingnamespacestd; constintN=20; template voidSwap(T&a,T&b) { Ttemp=a; a=b; b=temp; } template voidSelectSort(TA[],intn)//简单选择排序 { ints; for(inti=0;i { s=i; for(intj=i+1;j { if(A[j] { s=j; } } Swap } } template voidInsertSort(TA[],intn)//直接插入排序 { for(inti=1;i { intj=i; Ttemp=A[i]; while(j>0&&temp { A[j]=A[j-1]; j--; } A[j]=temp; } } template voidBubbleSort(TA[],intn)//冒泡排序 { inti,j,last; i=n-1; while(i>0) { last=0; for(j=0;j { if(A[j+1] { Swap last=j; } } i=last; } } template voidQSort(TA[],intleft,intright) { inti,j; if(left { i=left; j=right+1; do { do{i++;}while(A[i] do{j--;}while(A[j]>A[left]); if(i { Swap(A[i],A[j]); } }while(i Swap(A[left],A[j]); QSort(A,left,j-1); QSort(A,j+1,right); } } template voidQuickSort(TA[],intn)//快速排序 { QSort(A,0,n-1); } template voidInsertSort_2(TA[],intleft,intright)//用于改进快速排序的直接插入排序 { for(inti=left+1;i { intj=i; Ttemp=A[i]; while(j>0&&temp { A[j]=A[j-1]; j--; } A[j]=temp; } } template voidQSort_2(TA[],intleft,intright) {
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 各种 排序 算法 实现 性能 比较