归并排序基数排序算法比较.docx
《归并排序基数排序算法比较.docx》由会员分享，可在线阅读，更多相关《归并排序基数排序算法比较.docx（18页珍藏版）》请在冰点文库上搜索。
归并排序基数排序算法比较
课程设计任务书
学生姓名：
专业班级：
0908班
指导教师：
工作单位：
计算机科学系
题目:
归并排序、基数排序算法比较
初始条件：
试通过随机数据比较归并排序、基数排序各算法的关键字比较次数和关键字移动次数。
（1）待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
（2）最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。
（3）对归并排序应指出归并了多少趟。
要求完成的主要任务:
（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：
1、问题描述
简述题目要解决的问题是什么。
2、设计
存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；
3、调试报告
调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。
4、经验和体会（包括对算法改进的设想）
5、附源程序清单和运行结果。
源程序要加注释。
如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，
6、设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。
时间安排：
1、第19周完成。
2、7月1日14：
00到计算中心检查程序、交课程设计报告、源程序（CD盘）。
指导教师签名：
年月日
系主任（或责任教师）签名：
年月日
1问题描述
1.1题目内容
试通过随机数据比较归并排序、基数排序各算法的关键字比较次数和关键字移动次数。
1.2基本要求
（1）待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
（2）最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。
（3）对归并排序应指出归并了多少趟。
1.3测试数据
由函数rand随机产生5组伪随机数
{
constintMAX_SIZE=101;
intArray[MAX_SIZE],i,k;
for（k=0;k<=4;k++）
{
//srand（（unsigned）time（NUL
for（i=0;iArray[i]=rand（）%999;
}
2需求分析
2.1输入输出的形式和输入值的范围
由于程序中所需的数据都是有函数随机生成的整形数，不需要用户自己输入。
程序输出的是两种排序的随机数据以及比较后的有序排序，并且比较的结果输出，即输出两种排序各排序过程中所比较的数据的个数，交换的数据的次数和排序完成所用的时间。
两种排序的最终结果显示在计算机终端上，便于我们观察。
输入值的范围等价于程序中随机生成的数据的个数，即待排序表的表长不小于100，至少要用5组不同的输入数据体比较，比较的指标为：
有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次的移动）。
3概要设计
3.1程序所需的抽象数据类型
voidMSt（DataTypetheArray[],intfirst,intlast）{
if（firstintmid=（first+last）/2;
//以mid为中点将待排序数组平分成两部分，分别对两个部分使用递归思想进行排序
MS（theArray,first,mid）;
MS（theArray,mid+1,last）;
merge（theArray,first,mid,last）;//将整个序列归并为有序序列
}
}
voidRadixsort（intArray[],intn）
//基数排序
{
intcount[10];intkey;
for（inti=0;i<10;i++）
count[i]=0;
intj=1,k=0,a[10][MAX_SIZE+1],i=0;
for（intm=0;m<10;m++）
for（intn=0;na[m][n]=0;
for（i=0;i{
key=Array[i]%10;c1++;//数据的个位
count[key]++;
a[key][count[key]]=Array[i];m1++;
//把个位都为key的数放到a[key][count[key]]并
}
for（intk=0;k<10;k++）
a[k][0]=count[k];
back（a,Array）;
for（intm=0;m<10;m++）
for（intn=0;na[m][n]=0;
for（inti=0;i<10;i++）
count[i]=0;
for（i=0;i{
key=（Array[i]/10）%10;c1++;//十位数字
count[key]++;
a[key][count[key]]=Array[i];m1++;
}
for（intk=0;k<10;k++）
a[k][0]=count[k];
back（a,Array）;
for（intm=0;m<10;m++）
for（intn=0;na[m][n]=0;
for（inti=0;i<10;i++）
count[i]=0;
for（i=0;i{
key=（Array[i]/100）%10;c1++;//百位数字
count[key]++;
a[key][count[key]]=Array[i];m1++;
}
for（intk=0;k<10;k++）
a[k][0]=count[k];
back（a,Array）;
for（intk=0;k<10;k++）
a[k][0]=count[k];
back（a,Array）;
}
3.2系统功能模块
4.源代码及运行结果
源代码：
#include
#include
usingnamespacestd;
intm2=0,c2=0;
constintMAX_SIZE=101;
typedefintDataType;
voidback（inta[10][MAX_SIZE+1],intArray[]）;
voidmerge（DataTypetheArray[],intfirst,intmid,intlast）;
voidmergeSort（DataTypetheArray[],intfirst,intlast）;
voidRadixsort（intArray[],intn）;
intc1=0,m1=0;
intmain（）
intArray[MAX_SIZE],i,k;
for（k=0;k<=4;k++）//五组数据
{
for（i=0;iArray[i]=rand（）%999;//随机数
cout<<"thenumberstosort..."<for（intj=0;jcout<cout<cout<<"aftersorting..."<Radixsort（Array,MAX_SIZE）;
for（i=0;icout<cout<intfirst=0;
intlast=MAX_SIZE-1;
mergeSort（Array,first,last）;
for（intj=first;j<=last;j++）
cout<cout<cout<<"基数排序关键字参加的比较次数Compare1为"<<3*c1<<"关键字的移动次数Move1（关键字交换计为次移动）为"<cout<<"归并排序关键字参加的比较次数Compare2为"<<3*c2<<""<<"关键字的移动次数Move2（关键字交换计为次移动）为"<m2=0,c2=0;c1=0,m1=0;
}
return0;
}
voidback（inta[10][MAX_SIZE+1],intArray[]）
{
inti=0,j=0,k=0;
for（;i<10;i++）
{
for（j=1;j<=a[i][0];j++）
{
Array[k++]=a[i][j];m1++;
}
}
}
voidRadixsort（intArray[],intn）
{
intcount[10];intkey;
for（inti=0;i<10;i++）
count[i]=0;
intj=1,k=0,a[10][MAX_SIZE+1],i=0;
for（intm=0;m<10;m++）
for（intn=0;na[m][n]=0;
for（i=0;i{
key=Array[i]%10;c1++;
count[key]++;
a[key][count[key]]=Array[i];m1++;
}
for（intk=0;k<10;k++）
a[k][0]=count[k];
back（a,Array）;
for（intm=0;m<10;m++）
for（intn=0;na[m][n]=0;
for（inti=0;i<10;i++）
count[i]=0;
for（i=0;i{
key=（Array[i]/10）%10;c1++;
count[key]++;
a[key][count[key]]=Array[i];m1++;
}
for（intk=0;k<10;k++）
a[k][0]=count[k];
back（a,Array）;
for（intm=0;m<10;m++）
for（intn=0;na[m][n]=0;
for（inti=0;i<10;i++）
count[i]=0;
for（i=0;i{
key=（Array[i]/100）%10;c1++;
count[key]++;
a[key][count[key]]=Array[i];m1++;
}
for（intk=0;k<10;k++）
a[k][0]=count[k];
back（a,Array）;
for（intk=0;k<10;k++）
a[k][0]=count[k];
back（a,Array）;
}
voidmergeSort（DataTypetheArray[],intfirst,intlast）{
if（first//分成两部分进行排序
intmid=（first+last）/2;
mergeSort（theArray,first,mid）;//递归左半部分
/
mergeSort（theArray,mid+1,last）;//递归右半部分
merge（theArray,first,mid,last）;//合并
}
}
voidmerge（DataTypetheArray[],intfirst,intmid,intlast）{
DataTypetempArray[MAX_SIZE];
intfirst1=first;
intlast1=mid;
intfirst2=mid+1;
intlast2=last;
intindex=first1;//两个子数组不是空的，复制到临时数组中
for（;（first1<=last1）&&（first2<=last2）;index++）{
//tempArray[first1...index-1]已经是有序
if（theArray[first1]{
tempArray[index]=theArray[first1];m2++;c2++;
first1++;
}
else{
tempArray[index]=theArray[first2];c2++;
first2++;
}
}
//非空子数组完成
for（;first1<=last1;first1++,index++）
{tempArray[index]=theArray[first1];m2++;}
for（;first2<=last2;first2++,index++）
{tempArray[index]=theArray[first2];m2++;}
//复制的结果返回到原来的阵列
for（index=first;index<=last;index++）
{theArray[index]=tempArray[index];m2++;}
};
运行结果如下：
结果简析：
基数排序过程中先比较地位在比较高位就是体现关键字由地位优先字到高位优先字的思想。
由于所排序数字的范围在0-998之间，所以需要进行三趟分配和手机就可以使之基本有序。
时间复杂度为O（d（n+rd））,排序也比较稳定。
在内部排序的时候主要将关键字分成两部分，然后应用递归分别归并，最后在进行合并排序使之基本有序，时间复杂度为O（nlogn）。
上述五组数据进行归并排序的比较次数和关键字移动次数分别为：
第一组1095,1348。
；第二组1086,1357；第三组1092,1356；第四组：
1092,1353；第五组1083，1354。
5.总结
这次课程设计运用到了大学c语言和大二所学习到的数据结构知识点，课设题目要求不仅要求对课本知识有较深刻的了解，懂得了基数排序和归并排序的的基本思想和操作。
同时要求程序设计者有较强的思维和动手能力。
这次课设使我了解我编程思想和编程技巧。
在写程序的过程中遇到的麻烦很多，开始甚至不敢动手写算法怕出错，后来仔细看课本发现课本上都把最基本的算法写的很清楚，我们只需要去理解，把分散的知识聚拢来，用学过的知识把一个一个的排序恰当的连接起来就能写程序的主要部分，然后有不懂的在想同学请教并在调试中找出错误，是指正确运行。
做课程设计不仅让我修补了以前学习的漏洞，也让我知道一个道理：
编程需要兴趣和实际动手也需要虚心学习。
要敢于动手写出自己的程序，然后去耐心调试和修改。
本科生课程设计成绩评定表
班级：
计算机0908班 姓名：
颜兵情学号：
0120910340820
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
10
2
设计分析合理性
10
3
设计方案正确性、可行性、创造性
20
4
设计结果正确性
40
5
设计报告的规范性
10
6
设计验收
10
总得分/等级
评语：
注：
最终成绩以五级分制记。
优（90-100分）、良（80-89分）、中（70-79分）、
及格（60-69分）、60分以下为不及格
指导教师签名：
2011年 月 日
升级会员 