内部排序算法比较C语言.docx
《内部排序算法比较C语言.docx》由会员分享，可在线阅读，更多相关《内部排序算法比较C语言.docx（15页珍藏版）》请在冰点文库上搜索。
内部排序算法比较C语言
课题：
内部排序算法比较
第一章问题描述
排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！
该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！
排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。
比较的结果用一个直方图表示。
第二章系统分析
界面的设计如图所示：
|******************************|
|-------欢迎使用---------|
|-----
（1）随机取数-------|
|-----
（2）自行输入-------|
|-----（0）退出使用-------|
|******************************|
请选择操作方式：
如上图所示该系统的功能有：
（1）：
选择1时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。
（2）选择2时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。
（3）选择0打印“谢谢使用！
！
”退出系统的使用！
！
第三章系统设计
（I）友好的人机界面设计：
（如图3.1所示）
|******************************|
|-------欢迎使用---------|
|-----
（1）随机取数-------|
|-----
（2）自行输入-------|
|-----（0）退出使用-------|
|******************************|
（3.1）
（II）方便快捷的操作：
用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！
如图（3.2所示）
|******************************|
|-------欢迎使用---------|
|-----
（1）随机取数-------|
|-----
（2）自行输入-------|
|-----（0）退出使用-------|
|******************************|
请选择操作方式：
（用户在此输入操作方式）
（3.2）
（III）系统采用定义结构体数组来存储数据。
（IV）功能介绍：
（1）操作功能：
a.当用户选择随即电脑随机取数时
系统将弹出——>请输入你要输入的个数：
（用户在此输入要电脑取数的个数）要是用户输入的数据过大系统将提醒错误——>超出范围重新输入!
!
!
b..当用户选择自行输入时
系统将弹出——>请输入你要输入的个数（不大于于30的整数）：
当用户输完元素的个数之后系统将提示用户依次输入各个元素。
——>请输入各个元素:
（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]）;
}
第五章系统测试
（一）随机取数的测试：
（二）自行输入的测试：
（三）退出系统：
（四）时间的估算：
排序方法
平均时间性能
最好时间性能
最坏时间性能
直接
O（n2）
O（n）
O（n2）
简单选择
O（n2）
O（n）
O（n2）
冒泡
O（n2）
O（n）
O（n2）
堆排序
O（nlog2n）
O（nlog2n）
O（nlog2n）
直接
O（nlog2n）
O（nlog2n）
O（nlog2n）
快速
O（nlog2n）
O（nlog2n）
O（nlog2n）
参考文献
1.作者:
张晓莉王苗《数据结构与算法》机械工业出版社2008年7月
2.作者：
杨升《数据结构》厦门大学出版社2009年6月
教师评语和成绩
2010年6月
升级会员 