数据结构 内部排序算法比较.docx
《数据结构 内部排序算法比较.docx》由会员分享，可在线阅读，更多相关《数据结构 内部排序算法比较.docx（33页珍藏版）》请在冰点文库上搜索。
数据结构内部排序算法比较
内部排序算法比较
目录
摘要1
1绪论1
2系统分析1
2.1功能需求1
2.2数据需求1
2.3性能需求2
3总体设计2
3.1系统设计方案2
3.2功能模块设计2
4详细设计3
4.1数据结构定义3
4.2伪随机产生数据模块4
4.3简单选择排序模块6
4.4起泡排序模块7
4.5直接插入排序模块8
4.6希尔排序模块9
4.7快速排序模块10
4.8归并排序模块11
4.9条形图模块12
5调试与测试13
5.1调试13
5.2测试13
6结论14
结束语14
参考文献15
附录1－用户手册16
附录2－源程序18
1绪论
随着科技的快速发展，越来越多的企业不再浪费人力财力去计算一些统计性结果，而是应用一些简单的程序或系统来完成这些任务。
随着学习数据结构课程的深入，了解了不同排序算法的不同排序方法，每种排序对数据的比较次数、移动次数和排序用时都是不同的，本程序实现了六种内部排序算法的比较，并用条形图直观的显示出各种算法的优劣。
运用伪随机产生的数据，调用六种排序算法，记录其比较次数、移动次数和排序时间，再分别用条形图（星号表示）表示出来。
2系统分析
2.1功能需求
（1）对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、归并排序算法进行比较。
（2）待排序的元素的关键字为整数，其中数据要用伪随机产生程序产生，并且至少用5组的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。
（3）演示程序以人机对话的形式进行，每次测试完毕显示各种比较指标值，比较次数、移动次数和排序时间的列表，并用条形图即星号表示出来，以便比较各种排序的优劣。
2.2数据需求
抽象数据类型：
线性表、排序算法
（1）输入数据：
需要比较的数据数目
（2）输出数据：
不同算法的比较次数、移动次数、排序时间的数据以及对应的条形图。
2.3性能需求
在运行本程序时，只要按照正确的操作方法不会出现无法运行的情况，系统稳定性好，安全，可靠，响应速度由需比较的数字数目多少来决定。
3总体设计
3.1系统设计方案
（1）输入要排序的数据数目
（2）抽象数据类型定义
typedefstruct
{
intkey;
}ElemType;//关键字
typedefstruct
{
ElemType*elem;
intlength;
}SqList;//分配顺序存储结构
（3）存储结构：
本程序采用了线性表的顺序存储结构。
（4）算法设计：
简单选择排序：
运用顺序表。
时间复杂度O（n2），空间复杂度O
（1）。
起泡排序：
时间复杂度O（n2），空间复杂度O
（1）
直接插入排序：
时间复杂度O（n2），空间复杂度O
（1）
希尔排序：
时间复杂度O（n1.3），空间复杂度O
（1）
快速排序：
时间复杂度O（nlog2n），空间复杂度O（nlog2n）
归并排序：
时间复杂度O（nlog2n），空间复杂度O（n）
3.2功能模块设计
根据分析整个程序主要划分为8个功能模块，分别执行要求中的功能。
1个产生伪随机数据模块、6个内部排序算法模块以及1个形成条形图模块。
功能模块图如图1所示
图1功能模块图
（1）伪随机产生数据模块：
本程序要求数据是要用伪随机产生程序产生，再用不同排序算法进行排序。
（2）简单选择排序模块：
运用简单选择排序法对伪随机产生的数据进行排序。
（3）起泡排序模块：
运用起泡排序法对伪随机产生的数据进行排序。
（4）直接插入排序模块：
运用直接插入排序法对伪随机产生的数据进行排序。
（5）希尔排序模块：
运用希尔排序法对伪随机产生的数据进行排序。
（6）快速排序：
运用快速排序法对伪随机产生的数据进行排序。
（7）归并排序：
运用归并排序法对伪随机产生的数据进行排序。
（8）条形图表示比较结果：
统计6种排序算法的比较结果，用条形图表示出来。
4详细设计
4.1数据结构定义
typedefstruct
{intkey;
}ElemType;//关键字
typedefstruct
{
ElemType*elem;
intlength;
}SqList;//分配顺序存储结构
4.2伪随机产生数据模块
伪随机产生数据模块可实现伪随机产生不同数目的数据以供排序，运用顺序存储结构来实现的。
该模块具体实现程序流程如图2所示。
图2伪随机产生数据模块
4.3简单选择排序模块
简单选择排序模块可实现用简单排序法对产生的数据进行排序。
该模块具体实现程序流程如图3所示。
图3简单选择模块
4.4起泡排序模块
起泡排序模块可实现运用起泡排序法对数据进行排序，该模块具体实现程序流程如图4所示。
图4起泡排序模块
4.5直接插入排序模块
直接插入排序模块可实现运用直接插入排序法对数据进行排序，该模块具体实现程序流程如图5所示。
图5直接插入排序模块
4.6希尔排序模块
希尔排序模块可实现运用希尔排序法对数据进行排序，该模块具体实现程序流程如图6所示。
图6希尔排序模块
4.7快速排序模块
快速排序模块可实现用快速排序法对数据进行排序，该模块具体实现程序流程如图7所示。
图7快速排序模块
4.8归并排序模块
归并排序模块可实现用归并排序法对数据进行排序，该模块具体实现程序流程如图8所示。
图8归并排序模块
4.9条形图模块
条形图模块可用星号显示出各种算法排序的比较结果，该模块具体实现程序流程如图9所示。
图9条形图模块
5调试与测试
5.1调试
调试过程主要是运行编制好的程序，然后遇到错误后根据系统的提示，找到相关的问题所在。
本系统调试过程中遇到的主要问题、原因和解决方法如下面介绍。
（1）问题：
用条形图表示时，不能根据数据而表示出星号的多少。
解决办法：
选择要表示的数据最小的一种排序作为基数，每种排序所要比较的数据可运用数学运算计算出是基数的多少倍，从而输出几个星号。
（2）问题：
输入数据数目为2个时程序运行错误。
原因：
待比较的数据为2个时，作为基数的那种排序的数据为0，不能做分母，所以会出现运行错误。
解决方法：
输入较大的数，使要用条形图表示出来的数据不为0即可。
5.2测试
软件测试是软件生存期中的一个重要阶段，是软件质量保证的关键步骤从用户的角度来看，普遍希望通过软件测试暴露软件中隐藏的错误和缺陷，所以软件测试应该是“为了发现错误而执行程序的过程”。
或者说，软件测试应该根据软件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例（即输入数据及其预期的输出结果），并利用这些测试用例去运行程序，以发现程序错误或缺陷。
过度测试则会浪费许多宝贵的资源。
到测试后期，即使找到了错误，然而付出了过高的代价。
测试数据过程如下。
（1）输入功能测试
输入数据1：
100
预期结果：
输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。
运行结果：
输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。
说明：
预期和运行结果相同。
输入数据2：
25000
预期结果：
输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。
运行结果：
超出范围重新输入!
说明：
不能输入比25000大的数。
（2）输出功能测试
输入数据1：
200
预期结果：
输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。
运行结果：
输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。
说明：
：
预期和运行结果相同。
输入数据2：
4
预期结果：
输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。
运行结果：
在输出移动次数比较的条形图时出现运行错误。
说明：
不能输入比5小的数。
6结论
经过这一段时间的程序设计，该课设任务书中题目所要求的功能也都一一实现。
可以伪随机产生不同的数据，六种内部排序算法对其数据进行排序，记录比较次数、移动次数和排序用时，并用条形图直观的表示出不同算法的优劣。
不过本程序还可以添加细节，例如：
可输出个选择排序方法的菜单，挑选不同排序方法对数据进行比较，也可以再循环选择并用条形图表示出来。
结束语
为期两个星期的课程设计终于顺利完成，这段时间让我对数据结构这门课程有更多的了解和认识，同时也从编程中所遇到的挫折和困难中吸取更多有价值的经验。
编程需要耐心和信心，要有缜密的心思来全面考虑问题，否则编出的程序不能完全满足题目要求或运行错误。
通过这次课设，我更深入了解了六种内部排序算法的排序方法和时间复杂度，从而还算顺利的完成了本次课程设计。
编程的道路不好走，不过我会更加努力的学习，让编程不再那么困难辛苦，让以后自己能有信心的轻松面对。
参考文献
[1]谭浩强.C语言程序设计（第三版）.清华大学出版社，2007
[2]姜灵芝，余健.C语言课程设计案例精编.清华大学出版社，2008
[3]吴伟民，严蔚敏.数据结构.清华大学出版社，2008
[4]吕映芝.编译原理.清华大学出版社，2008
附录1－用户手册
点击运行，首先出现的是要输入伪随机产生数据的数目，如图9所示。
图9输入界面
输入数据个数然后回车，可显示出不同排序算法的比较次数、移动次数和排序用时。
如图10所示。
图10显示比较结果界面
显示比较次数的条形图。
如图11所示。
图11比较次数条形图界面
显示移动次数条形图。
如图12所示
图12移动次数条形图界面
显示排序用时条形图。
如图13所示
图13排序用时条形图界面
附录2－源程序
主要模块源代码清单：
#include
#include
#include
#include
#include
#defineLIST_INIT_SIZE30000
intbj1,yd1,n,com,mov;
longintA[5],B[5];
doublet0,t1,t2,t3,t4,t5,C[5];
clock_tstart_t,end_t;
typedefstruct
{
intkey;
}ElemType;
typedefstruct
{
ElemType*elem;
intlength;
}SqList;
voidaddlist（SqList&L）
{
inti;
a:
printf（"请输入你要输入的个数:
"）;
scanf（"%d",&n）;
if（n>20000）
{
printf（"超出范围重新输入!
!
!
\n"）;
gotoa;
}
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）exit（0）;
L.length=0;
for（i=1;i{
b:
L.elem[i].key=rand（）;
if（L.elem[i].key>20000）gotob;
++L.length;
}
}
voidSelectSort（SqList&L）//简单选择排序
{
start_t=clock（）;
inti,j,k,com=0,mov=0;
for（i=1;i{
k=i;
for（j=i+1;j{
com++;
if（L.elem[j].key}
if（i!
=k）
{
L.elem[0].key=L.elem[i].key;
L.elem[i].key=L.elem[k].key;
L.elem[k].key=L.elem[0].key;
mov+=3;
}
}
end_t=clock（）;
printf（"比较次数为%d移动次数为%d\n",com,mov）;
t0=（double）（end_t-start_t）/CLK_TCK;
printf（"排序用时为%f\n",t0）;
A[0]=com;
B[0]=mov;
C[0]=t0;
}
voidbubblesort（SqList&L）//起泡排序
{
start_t=clock（）;
inti=1,j,com=0,mov=0;
while（i{
for（j=1;j{
com++;
if（L.elem[j].key>L.elem[j+1].key）
{
L.elem[0].key=L.elem[j].key;
L.elem[j].key=L.elem[j+1].key;
L.elem[j+1].key=L.elem[0].key;
mov+=3;
}
}
i++;
}
end_t=clock（）;
printf（"比较次数为%d移动次数为%d\n",com,mov）;
t1=（double）（end_t-start_t）/CLK_TCK;
printf（"排序用时为%f\n",t1）;
A[1]=com;
B[1]=mov;
C[1]=t1;
}
voidInsertSort（SqList&L）//直接插入排序
{
start_t=clock（）;
inti,j,com=0,mov=0;
for（i=2;i<=L.length;i++）
{
if（L.elem[i].key{
L.elem[0].key=L.elem[i].key;
mov++;
j=i-1;
com++;
while（L.elem[0].key{
L.elem[j+1].key=L.elem[j].key;
j--;
mov++;
com++;
}
L.elem[j+1].key=L.elem[0].key;
mov++;
}
}
end_t=clock（）;
printf（"比较次数为%d移动次数为%d\n",com,mov）;
t2=（double）（end_t-start_t）/CLK_TCK;
printf（"排序用时为%f\n",t2）;
A[2]=com;
B[2]=mov;
C[2]=t2;
}
voidxier（SqList&L）//希尔排序
{
start_t=clock（）;
inti,d=L.length/2,j,w=0,k,com=0,mov=0;
while（w{
w=1;
for（i=w;i{
k=i;
for（j=i+d;j{
if（L.elem[i].key>L.elem[j].key）
{
k=j;
com++;
}
}
if（i!
=k）
{
L.elem[0].key=L.elem[i].key;
L.elem[i].key=L.elem[k].key;
L.elem[k].key=L.elem[0].key;
mov+=3;
}
w++;
}
d=d/2;
w=1;
}
end_t=clock（）;
printf（"比较次数为%d移动次数为%d\n",com,mov）;
t3=（double）（end_t-start_t）/CLK_TCK;
printf（"排序用时为%f\n",t3）;
A[3]=com;
B[3]=mov;
C[3]=t3;
}
voidBeforeSort（）
{
yd1=0,bj1=0;
}
voiddisplay（intm,intn）
{
printf（"比较次数为%d移动次数为%d\n",m,n）;
}
intPartition（SqListL,intlow,inthigh）//快速排序
{
intpivotkey;
L.elem[0]=L.elem[low];
yd1++;
pivotkey=L.elem[low].key;
while（low{
yd1++;
while（low=pivotkey）
{
--high;
L.elem[low]=L.elem[high];
bj1++;
yd1++;
}
while（low{
++low;
L.elem[high]=L.elem[low];
bj1++;
yd1++;
}
}
L.elem[low]=L.elem[0];
yd1++;
returnlow;
}
voidQSort（SqList&L,intlow,inthigh）
{
intpivotloc;
if（low{
pivotloc=Partition（L,low,high）;
QSort（L,low,pivotloc-1）;
QSort（L,pivotloc+1,high）;
}
}
voidQuickSort（SqList&L）
{
start_t=clock（）;
BeforeSort（）;
QSort（L,1,L.length）;
display（bj1,yd1）;
end_t=clock（）;
t4=（double）（end_t-start_t）/CLK_TCK;
printf（"排序用时为%f\n",t4）;
A[4]=bj1;
B[4]=yd1;
C[4]=t4;
}
voidMerge（ElemTypeR[],ElemTypeR1[],intlow,intm,inthigh）//归并排序
{
inti=low,j=m+1,k=low;
while（i<=m&&j<=high）
{
if（R[i].key<=R[j].key）
{
bj1++;
R1[k]=R[i];
yd1++;
i++;
k++;
}
else
{
bj1++;
R1[k]=R[j];
yd1++;
j++;
k++;
}
}
while（i<=m）
{
R1[k]=R[i];
yd1++;
i++;
k++;
}
while（j<=high）
{
R1[k]=R[j];
yd1++;
j++;
k++;
}
}
voidMergePass（ElemTypeR[],ElemTypeR1[],intlength,intn）
{
inti=0,j;
while（i+2*length-1{
Merge（R,R1,i,i+length-1,i+2*length-1）;
i=i+2*length;
}
if（i+length-1Merge（R,R1,i,i+length-1,n-1）;
else
for（j=i;jR1[j]=R[j];
}
voidMSort（ElemTypeR[],ElemTypeR1[],intn）
{
intlength=1;
while（length{
MergePass（R,R1,length,n）;
length=2*length;
MergePass（R1,R,length,n）;
length=2*length;
}
}
voidMergeSort（SqList&L）
{
start_t=clock（）;
BeforeSort（）;
MSort（L.elem,L.elem,L.length）;
display（bj1,yd1）;
end_t=clock（）;
t5=（double）（end_t-start_t）/CLK_TCK;
printf（"排序用时为%f\n",t5）;
A[5]=bj1;
B[5]=yd1;
C[5]=t5;
}
voidprintf（SqList&L）
{
longintd[6];
inti,n;
printf（"\n★★★★★★比较次数★★★★★★\n"）;
printf（"\n=====================\n"）;
for（i=0;i<5;i++）
d[i]=sqrt（A[i]/A[5]）;
printf（"\n归并排序：
*"）;
printf（"\n=====================\n"）;
printf（"选择排序：
"）;
for（n=0,i=0;n<=d[i];n++）
{
printf（"*"）;
}
printf（"\n=====================\n"）;
printf（"冒泡排序：
"）;
for（n=0,i=1;n<=d[i];n++）
{
printf（"*"）;
}
printf（"\n=====================\n"）;
printf（"直插排序：
"）;
for（n=0,i=2;n<=d[i];n++）
{
printf（"*"）;
}
printf（"\n=====================\n"）;
printf（"希尔排序：
"）;
for（n=0,i=3;n<=d[i];n++）
{
printf（"*"）;
}
printf（"\n=====================\n"）;
printf（"快排排序：
"）;
for（n=0,i=4;n<=d[i];n++）
{
printf（"*"）;
}
printf（"\n=====================\n"）;
printf（"\n★★★★★★移动次数★★★★★★\n"）;
printf（"\n=====================\n"）;
doublee[6];
for（i=0;i<6;i++）
e[i]=sqrt（B[i]/B[3]）;
printf（"\n希尔排序：
*"）;
printf（"\n=====================\n"）;
printf（"选择排序：
"）;
for（n=0,i=0;n<=e[
升级会员 