排序算法比较.docx
《排序算法比较.docx》由会员分享，可在线阅读，更多相关《排序算法比较.docx（15页珍藏版）》请在冰点文库上搜索。
排序算法比较
《数据结构的课程设计》
报告
题目：
排序算法比较
班级：
1612401
学号：
161240113
姓名：
张修鸣
指导老师：
孙涵
完成日期：
2014.1.3
目录
一.需求分析.
二.程序主要功能.
三.程序运行平台.
四.程序类说明.
五.模块分析.
六.存在的不足与对策.
七．体验感悟
八.程序源代码.
需求分析
利用随机函数产生N个随机整数（N=500，1000，1500，2000，2500，…,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（即比较次数）。
程序主要功能
（1）原始数据存在文件中，每个整数一行，方便读入。
（2）屏幕显示每种排序所花的比较次数。
程序运行平台
该程序是用VC++6.0制做的，使用MicrosoftVisualC++6.0运行该程序，具体操作是：
打开MicrosoftVisualC++6.0，菜单栏里点文件→打开工作区→找到“图书管理系统.dsw”这个文件→打开，或者在资源管理器中双击该文件，此时，VC++6.0会自动打开，并载入该系统相关资源，点击Run命令菜单或者或用快捷键Ctrl+F5运行该程序。
trl计分析能_________________________________________________________________________________________________________________________
程序类说明
函数分析：
intBubbleSort（inta[]）//冒泡排序
intSelectionSort（inta[]）//选择排序
intinsertsort（inta[]）//直接插入排序
intBInsertSort（inta[]）//折半插入排序
intPartitoin（inta[],intlow,inthigh）//快速排序
intradixsort（intdata[],intn）//基数排序
voidheapsort（int*heap,intlow,inthigh）//堆排序
模块分析
当随机生成20000个数时
程序运行分析
随机生成数
排序后
存在的不足与对策
由于自身能力有限，所以没有设计的堆排序和快排序差距较大。
在设计过程中由于设计者的编程功底欠缺，因此学习过程较为艰辛，需要解决的问题也比较多。
在以后的学习中，应该循序渐进，不可急于求成，先打好基础，这样才能更好地发展。
体验感悟
在编写程序的过程中，深切的体会到自身能力还有待提高，通过大规模的查询网上资料与相关书籍我学习到了很多以前不知道的编程方法与各种奇妙的函数语句时，提高了自己对程序设计本身的兴趣，更加乐意去学习这方面的新的东西，并在不断地自我挑战中收获着，或知识技能，或信心勇气。
希望自己在今后的学习中可以更好的完善自我。
程序源代码
#include
usingnamespacestd;
#include
#include
#include
#defineSIZE20000
voidcreatData（）
{
inti,m;
fstreamfile;
file.open（"data.txt",ios:
:
out|ios:
:
trunc）;
if（file.fail（））
{
cout<<"打开文件失败!
\n";
exit（0）;
}
srand（time（0））;
for（i=0;i{
m=rand（）;
file<}
file.close（）;
}
intBubbleSort（inta[]）//冒泡排序
{
inti,j,t,count=0;
for（i=0;ifor（j=0;jif（a[j]>a[j+1]）
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
count++;
}
returncount;
}
intSelectionSort（inta[]）//选择排序
{
inti,j,t,minIndex,count=0;
for（i=0;i{
minIndex=i;
for（j=i+1;jif（a[j]minIndex=j;
if（minIndex!
=i）
{
t=a[minIndex];
a[minIndex]=a[i];
a[i]=t;
count++;
}
}
returncount;
}
intinsertsort（inta[]）//直接插入排序
{
intcount=0;
for（inti=1;i{
inttemp=a[i];
intj=i-1;
for（;j>=0&&temp{
a[j+1]=a[j];count++;
}
a[j+1]=temp;
}
returncount;
}
intBInsertSort（inta[]）//折半插入排序
{
inti,j,high,low,m,count=0;
for（i=2;i<=SIZE;++i）
{
a[0]=a[i];
low=1;
high=i-1;
while（low<=high）
{
m=（low+high）/2;
if（a[0]elselow=m+1;
count++;
}
for（j=i-1;j>=high+1;--j）a[j+1]=a[j];
a[high+1]=a[0];
}
returncount;
}
intquicksort=0;
intPartitoin（inta[],intlow,inthigh）//快速排序
{
a[0]=a[low];
intpivotkey=a[low];
while（low{
while（low=pivotkey）--high;
a[low]=a[high];
while（lowa[high]=a[low];
quicksort++;
}
a[low]=a[0];
returnlow;
}
voidQSort（inta[],intlow,inthigh）
{
intprvotloc;
if（low{
prvotloc=Partitoin（a,low,high）;
QSort（a,low,prvotloc-1）;
QSort（a,prvotloc+1,high）;
}
}
intmaxbit（intdata[],intn）//求数据的最大位数
{
inti,p,max=0;
int*temp;
temp=newint[n];
for（i=0;ifor（i=0;i{
p=1;
while（temp[i]/10>0）
{
p++;temp[i]=temp[i]/10;
}
if（p>max）max=p;
}
delete[]temp;
returnmax;
}
intradixsort（intdata[],intn）//基数排序
{
int*temp,count1=0;
temp=newint[n];
inti,j,k;
intcount[10];
intradix=1;
for（i=radix;i<=maxbit（data,n）;i++）
{
for（j=0;j<10;j++）count[j]=0;
for（j=0;j{
k=（data[j]/radix）%10;
count[k]++;
}
for（j=1;j<10;j++）
count[j]+=count[j-1];
for（j=n-1;j>=0;j--）
{
k=（data[j]/radix）%10;
count[k]--;
temp[count[k]]=data[j];
count1++;
}
for（j=0;jdata[j]=temp[j];
radix=radix*10;
}
delete[]temp;
returncount1;
}
intheapsort=0;
voidheapAdjust（int*heap,intlow,inthigh）//堆排序
{
inti,temp=heap[low];
for（i=low*2+1;i<=high;i*=2）
{
if（ii++;
if（heap[i]<=temp）
break;
heap[low]=heap[i];
low=i;
heapsort++;
}
heap[low]=temp;
}
voidheapSort（int*heap）
{inttemp;
inti,count=0;
for（i=SIZE/2-1;i>=0;--i）
heapAdjust（heap,i,SIZE-1）;
for（i=SIZE-1;i>0;--i）
{
temp=heap[0];
heap[0]=heap[i];
heap[i]=temp;
heapAdjust（heap,0,i-1）;
}
}
intmain（）
{
inti=0,a[SIZE],b[SIZE];
fstreamfile,fp1,fp2,fp3,fp4,fp5,fp6,fp7;
file.open（"data.txt",ios:
:
in）;
fp1.open（"a1.txt",ios:
:
trunc|ios:
:
out）;
fp2.open（"a2.txt",ios:
:
trunc|ios:
:
out）;
fp3.open（"a3.txt",ios:
:
trunc|ios:
:
out）;
fp4.open（"a4.txt",ios:
:
trunc|ios:
:
out）;
fp5.open（"a5.txt",ios:
:
trunc|ios:
:
out）;
fp6.open（"a6.txt",ios:
:
trunc|ios:
:
out）;
fp7.open（"a7.txt",ios:
:
trunc|ios:
:
out）;
if（file.fail（）||fp1.fail（）||fp2.fail（）||fp3.fail（）||fp4.fail（）||fp5.fail（）||fp6.fail（）||fp7.fail（））
{
cout<<"打开文件失败!
\n";
exit（0）;
}
creatData（）;
while（!
file.eof（））
{
file>>a[i];
b[i]=a[i];
i++;
}
cout<<"直接插入排序的比较次数为:
"<for（i=0;ifp1<for（i=0;ia[i]=b[i];
cout<<"冒泡排序的比较次数为:
"<for（i=0;ifp2<for（i=0;ia[i]=b[i];
cout<<"选择排序的比较次数为:
"<for（i=0;ifp3<for（i=0;ia[i]=b[i];
heapSort（a）;
cout<<"堆排序的比较次数为:
"<for（i=0;ifp4<intc[SIZE+1];
for（i=0;ia[i]=b[i];
cout<<"折半插入排序的比较次数为:
"<for（i=1;ifp5<for（i=0;ic[i+1]=b[i];
QSort（c,1,SIZE）;
cout<<"快速排序的比较次数为:
"<for（i=1;ifp6<for（i=0;ic[i+1]=b[i];
cout<<"基数排序的比较次数为:
"<for（i=0;ifp7<file.close（）;fp1.close（）;fp2.close（）;fp3.close（）;fp4.close（）;fp5.close（）;fp6.close（）;fp7.close（）;
return0;
}
升级会员 