内部算法排序.docx
《内部算法排序.docx》由会员分享，可在线阅读，更多相关《内部算法排序.docx（12页珍藏版）》请在冰点文库上搜索。
内部算法排序
内部算法排序报告
1．需求分析
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间，存在一定的却缺陷。
我们将通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
所设计的程序应能够将产生的随机数据同时用不同的内部排序算法排序，并列出关键字比较次数与移动次数，方便比较。
待排序表的表长不少于100，为方便起见，我们令表长等于100，用5组随机的数据排序的结果作比较。
2．概要设计
排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！
该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！
排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。
比较的结果用一个直方图表示。
3．详细设计
程序设计如下：
（一）定义结构体数组：
typedefstruct
{intkey;
}datatype;
datatypeR[MAXNUM];//定义结构体数组
（二）直接排序：
voidD_InsertSort（datatypeR[],intn）//直接排序
{
inti,j;
for（i=2;i<=n;i++）
{cn[0]++;
if（R[i].key{R[0]=R[i];mn[0]++;
for（j=i-1;R[0].keyR[j+1]=R[j];
R[j+1]=R[0];mn[0]+=2;
}
}
}
（三）简单选择排序：
voidSelect_Sort（datatypeR[],intn）//简单选择排序
{
inti,j,k;
for（i=1;i{k=i;
for（j=i+1;j<=n;j++）
{
cn[1]++;
if（R[j].keyk=j;
}
if（i=k）
{R[0]=R[k];
R[k]=R[i];
R[i]=R[0];mn[1]+=3;}
}
}
（四）冒泡排序：
voidBubble_Sort（datatypeR[],intn）//冒泡排序
{
inti,j;
intswap;
for（i=1;i{swap=0;
for（j=1;j<=n-i;j++）
{
cn[2]++;
if（R[j].key{R[0]=R[j];
R[j]=R[j+1];
R[j+1]=R[0];mn[2]+=3;
swap=1;
}}
if（swap==0）break;
}
}
（五）堆排序：
voidHeapAdjust（datatypeR[],ints,intt）
{
datatyperc;
inti,j;
rc=R[s];
i=s;
for（j=2*i;j<=t;j=2*j）
{cn[3]++;
if（jif（rc.key>R[j].key）break;
R[i]=R[j];mn[3]++;
i=j;
}
R[i]=rc;
}
voidHeapSort（datatypeR[],intn）//堆排序
{
inti;
for（i=n/2;i>0;i--）
HeapAdjust（R,i,n）;
for（i=n;i>1;i--）
{R[0]=R[1];
R[1]=R[i];
R[i]=R[0];mn[3]+=3;
HeapAdjust（R,1,i-1）;
}
}
（六）归并排序：
voidMerge（datatypeR[],datatypeR1[],ints,intm,intt）
{
inti,j,k;
i=s;j=m+1;k=s;
while（i<=m&&j<=t）
{
cn[4]++;
if（R[i].key{R1[k++]=R[i++];mn[4]++;}
else
{R1[k++]=R[j++];mn[4]++;}
}
while（i<=m）{R1[k++]=R[i++];mn[4]++;}
while（j<=t）{R1[k++]=R[j++];mn[4]++;}
}
voidMSort（datatypeR[],datatypeR1[],ints,intt）
{
intm;
if（s==t）{R1[s]=R[s];mn[4]++;}
else{m=（s+t）/2;
MSort（R,R1,s,m）;
MSort（R,R1,m+1,t）;
Merge（R1,R,s,m,t）;
}
}
voidMergeSort（datatypeR[],datatypeR1[],intn）//归并排序
{
MSort（R,R1,1,n）;
}
intPartition（datatypeR[],intlow,inthigh）
{
R[0]=R[low];mn[5]++;
while（low{while（low=R[0].key）{cn[5]++;high--;}
if（lowwhile（lowif（low}
R[low]=R[0];mn[5]++;
returnlow;
}
（七）快速排序：
voidQuick_Sort（datatypeR[],ints,intt）//快速排序
{
inti;
if（s{
i=Partition（R,s,t）;
Quick_Sort（R,s,i-1）;
Quick_Sort（R,i+1,t）;
}
}
voidprin（datatypeR[],intn）
{
inti;
printf（"排序的结果为：
"）;
for（i=1;i<=n;i++）
printf（"%d",R[i]）;
printf（"\n"）;
}
（八）电脑随机取数：
voidsui_ji（）
{
inti,n;
datatypeR[MAXNUM]={0};
a:
printf（"请输入你要输入的个数:
"）;
scanf（"%d",&n）;
if（n>25）
{
printf（"超出范围重新输入!
!
!
\n"）;
gotoa;
}
addlist（R,n）;
printf（"排序前元素顺序为:
"）;
for（i=1;iprintf（"\n"）;
D_InsertSort（R,n）;//直接排序
prin（R,n）;
Select_Sort（R,n）;//简单选择排序
Bubble_Sort（R,n）;//冒泡排序
HeapSort（R,n）;//堆排序
datatypeR1[MAXNUM]={0};
MergeSort（R,R1,n）;//二路归并排序
Quick_Sort（R,0,n）;//快速排序
}
（九）用户自行输入：
voidzixing_input（）
{intn,i;
datatypeR1[MAXNUM]={0};
printf（"请输入你要输入的个数（不大于于30的整数）:
"）;
scanf（"%d",&n）;
printf（"请输入各个元素:
"）;
for（i=1;iscanf（"%d",&R1[i].key）;
printf（"排序前元素顺序为:
"）;
for（i=1;iprintf（"\n"）;
D_InsertSort（R1,n）;//直接排序
prin（R1,n）;
Select_Sort（R1,n）;//简单选择排序
Bubble_Sort（R1,n）;//冒泡排序
HeapSort（R1,n）;//堆排序
datatypeR2[MAXNUM]={0};
MergeSort（R1,R2,n）;//二路归并排序
Quick_Sort（R1,0,n）;//快速排序
}
（十）主函数调用：
intmain（void）
{
ints;
printf（"|******************************|\n"）;
printf（"|-------欢迎使用-----------------|\n"）;
printf（"|-----
（1）随机取数-------------|\n"）;
printf（"|-----
（2）自行输入-------------|\n"）;
printf（"|-----（0）退出使用-------------|\n"）;
printf（"|******************************|\n"）;
printf（"请选择操作方式：
"）;
scanf（"%d",&s）;
switch（s）
{
case1:
system（"cls"）;sui_ji（）;break;
case2:
system（"cls"）;zixing_input（）;break;
case0:
printf（"谢谢使用！
！
"）;exit（0）;break;
}
printf（"\n"）;
printf（"比较结果\n"）;
printf（"\n"）;
printf（"排序方式比较次数移动次数\n"）;
printf（"\n"）;
printf（"直接%d%d\n",cn[0],mn[0]）;
printf（"\n"）;
printf（"简单选择%d%d\n",cn[1],mn[1]）;
printf（"\n"）;
printf（"冒泡%d%d\n",cn[2],mn[2]）;
printf（"\n"）;
printf（"堆排序%d%d\n",cn[3],mn[3]）;
printf（"\n"）;
printf（"二路归并%d%d\n",cn[4],mn[4]）;
printf（"\n"）;
printf（"快速%d%d\n",cn[5],mn[5]）;
}
4．调试分析
调试过程主要是运行编制好的程序，然后遇到错误后根据系统的提示，找到相关的问题所在。
本系统调试过程中遇到的主要问题、原因和解决方法如下面介绍。
（1）问题：
用条形图表示时，不能根据数据而表示出星号的多少。
解决办法：
选择要表示的数据最小的一种排序作为基数，每种排序所要比较的数据可运用数学运算计算出是基数的多少倍，从而输出几个星号。
（2）问题：
输入数据数目为2个时程序运行错误。
原因：
待比较的数据为2个时，作为基数的那种排序的数据为0，不能做分母，所以会出现运行错误。
解决方法：
输入较大的数，使要用条形图表示出来的数据不为0即可。
5．用户手册
（1）操作功能：
a .当用户选择随即电脑随机取数时 系统将弹出——>请输入你要输入的个数 ：
（用户在此输入要电脑取数的个数） 要是用户输入的数据过大系统将提醒错误——>超出范围重新输入!
!
!
b . .当用户选择自行输入时 系统将弹出——>请输入你要输入的个数（不大于于30的整数）：
当用户输完元素的个数之后系统将提示用户依次输入各个元素。
——>请输入各个元素:
（2）排序功能：
系统有 简单选择排序，冒泡排序，堆排序，二路归并排序，快速排序的功能。
（3）打印清晰：
系统会打印出在排序操作之前电脑随机取数或者用户输入的原始排列顺序；并将排序操作之后的有序数据打印在原始数据的下面以便用户的对比。
在排序操作结束之后系统将以直方图的形式打出排序过程中比较和移动次数让客户一目了然地看到排序的结果
6．测试结果
升级会员 