内部排序算法比较实验报告c语言版Word下载.docx
《内部排序算法比较实验报告c语言版Word下载.docx》由会员分享，可在线阅读，更多相关《内部排序算法比较实验报告c语言版Word下载.docx（29页珍藏版）》请在冰点文库上搜索。
操作结果：
恢复最后一次用RandomizeList随机打乱得到的可排序表。
ListLength（）
返回可排序表的长度。
ListEmpty（）
若可排序表为空表，则返回Ture，否则返回False。
BubbleSort（&
c,&
s）
进行起泡排序，返回关键字比较次数c和移动次数s。
InsertSort（&
进行插入排序，返回关键字比较次数c和移动次数s。
SelectSort（&
进行选择排序，返回关键字比较次数c和移动次数s。
QuickSort（&
进行快速排序，返回关键字比较次数c和移动次数s。
ShellSort（long&
c,long&
进行希尔排序，返回关键字比较次数c和移动次数s。
HeapSort（&
进行堆排序，返回关键字比较次数c和移动次数s。
ListTraverse（visit（））
依次对L中的每个元素调用函数visit（）。
}ADTOrderableList
2．本程序包含两个模块：
1）主程序模块
voidmain（）{
初始化；
do{
接受命令；
处理命令；
}while（“命令”！
=“退出”）；
}
2）可排序表单元模块——实现可排序表的抽象数据类型；
各模块之间的调用关系如下：
主程序模块
可排序表单元模块
三、详细设计
1．根据题目要求和可排序表的基本操作特点，可排序表采用整数顺序表存储结构。
//可排序表的元素类型
#defineMAXSIZE10000//用作示例的顺序表的最大长度
typedefintBOOL;
typedefstruct{
intkey;
//关键字项
}RedType;
//记录类型
typedefstructLinkList{
RedTyper[MAXSIZE];
intLength;
//顺序表长度
}LinkList;
intRandArray[MAXSIZE];
//内部操作
voidRandomNum（）{
inti;
srand（20000）;
for（i=0;
i<
MAXSIZE;
i++）
RandArray[i]=（int）rand（）;
//构建随机序列
voidInitLinkList（LinkList*L）{//建立表
memset（L,0,sizeof（LinkList））;
RandomNum（）;
L->
r[i].key=RandArray[i];
//赋值
Length=i;
boolLT（inti,intj,int*CmpNum）{//比较i与j大小，返回0或1
（*CmpNum）++;
if（i<
j）
returnTRUE;
else
returnFALSE;
voidDisplay（LinkList*L）{//存储表到SortRes.txt文件中
FILE*f;
if（（f=fopen（"
SortRes.txt"
"
w"
））==NULL）{
printf（"
can'
topenfile\n"
）;
exit（0）;
}
Length;
fprintf（f,"
%d\n"
L->
r[i].key）;
fclose（f）;
//部分操作的伪码算法
//希尔排序
voidShellInsert（LinkList*L,intdk,int*CmpNum,int*ChgNum）{
inti,j;
RedTypeTemp;
for（i=dk;
i++）{
if（LT（L->
r[i].key,L->
r[i-dk].key,CmpNum））{
memcpy（&
Temp,&
L->
r[i],sizeof（RedType））;
for（j=i-dk;
j>
=0&
&
LT（Temp.key,L->
r[j].key,CmpNum）;
j-=dk）{
（*ChgNum）++;
r[j+dk],&
r[j],sizeof（RedType））;
Temp,sizeof（RedType））;
voidShellSort（LinkList*L,intdlta[],intt,int*CmpNum,int*ChgNum）{
intk;
for（k=0;
k<
t;
k++）
ShellInsert（L,dlta[k],CmpNum,ChgNum）;
//快速排序
intPartition（LinkList*L,intlow,inthigh,int*CmpNum,int*ChgNum）{
intPivotKey;
r[low],sizeof（RedType））;
PivotKey=L->
r[low].key;
while（low<
high）{
high&
r[high].key>
=PivotKey）{
high--;
r[low],&
r[high],sizeof（RedType））;
r[low].key<
low++;
r[high],&
returnlow;
voidQSort（LinkList*L,intlow,inthigh,int*CmpNum,int*ChgNum）{
intPivotLoc=0;
if（low<
PivotLoc=Partition（L,low,high,CmpNum,ChgNum）;
QSort（L,low,PivotLoc-1,CmpNum,ChgNum）;
QSort（L,PivotLoc+1,high,CmpNum,ChgNum）;
voidQuickSort（LinkList*L,int*CmpNum,int*ChgNum）{
QSort（L,0,L->
Length-1,CmpNum,ChgNum）;
//堆排序
voidHeapAdjust（LinkList*L,ints,intm,int*CmpNum,int*ChgNum）{
intj=0;
s++;
r[s-1],sizeof（RedType））;
for（j=2*s;
j<
=m;
j*=2）{
if（j<
m&
LT（L->
r[j-1].key,L->
r[j].key,CmpNum））
++j;
if（!
LT（Temp.key,L->
r[j-1].key,CmpNum））
break;
r[s-1],&
r[j-1],sizeof（RedType））;
s=j;
voidHeapSort（LinkList*L,int*CmpNum,int*ChgNum）{
inti=0;
for（i=L->
Length/2-1;
i>
=0;
i--）
HeapAdjust（L,i,L->
Length,CmpNum,ChgNum）;
1;
i--）{
r[0],sizeof（RedType））;
r[0],&
r[i-1],sizeof（RedType））;
r[i-1],&
HeapAdjust（L,0,i-1,CmpNum,ChgNum）;
//冒泡排序
voidBubbleSort（LinkList*L,int*CmpNum,int*ChgNum）{
RedTypetemp;
for（i=1;
=MAXSIZE;
for（j=1;
=MAXSIZE-i;
j++）{
LT（L->
r[j].key,L->
r[j+1].key,CmpNum））{
temp,&
r[j],&
r[j+1],sizeof（RedType））;
r[j+1],&
temp,sizeof（RedType））;
//选择排序
intSelectMinKey（LinkList*L,intk,int*CmpNum）{
intMin=k;
for（;
k++）{
r[Min].key,L->
r[k].key,CmpNum））
Min=k;
returnMin;
voidSelSort（LinkList*L,int*CmpNum,int*ChgNum）{
j=SelectMinKey（L,i,CmpNum）;
if（i!
=j）{
r[i],&
3．函数的调用关系图反映了演示程序的层次结构：
main
srand
BubbleSortInsertSortSelectSortQuickSortShellSortHeapSort
InitLinkListRandomNumLTDisplay
四、调试分析
1．对正序、逆序和若干不同程度随机打乱的可排序表，进行各种排序方法的比较测试，得到的测试数据具有较好的典型性和可比较性。
通过设计和实现指定程序的随机乱序算法，对伪随机数序列的产生有了具体的认识和实践。
2．将排序算法中的关键字比较和交换分别由Less和Swap两个内部操作实现，较好的解决了排序算法的关键字比较次数和移动次数的统计问题。
而赋值是直接统计的。
3．本实习作业采用循序渐进的策略，首先设计和实现可排序表的建立和随机操作，然后用插入排序验证各种内部辅助操作的正确性，进而逐个加入其他排序算法，最后完成对测试结果的显示。
调试能力有了提高。
五、用户手册
1．本程序的运行环境为DOS操作系统，执行文件为：
内部排序算法比较.exe。
2．进入程序后即显示文本方式的用户界面：
3．输入1回车，即得直接插入排序的排序结果及其关键字比较次数和移动次数及时间
输入2回车，即得希尔排序的排序结果及其关键字比较次数和移动次数及时间
输入3回车，即得快速排序的排序结果及其关键字比较次数和移动次数及时间
输入4回车，即得堆排序的排序结果及其关键字比较次数和移动次数及时间
输入5回车，即得冒泡排序的排序结果及其关键字比较次数和移动次数及时间
输入6回车，即得选择排序的排序结果及其关键字比较次数和移动次数及时间
输入7回车，即得以上所有排序的排序结果及其关键字比较次数和移动次数及时间
输入8回车，即退出该程序
六、测试结果
对结果的截屏如下：
对各种表长和测试组数进行了测试，程序运行正常。
分析实测得到的数值，6种排序算法（快速排序采用“比中法”）的特点小结如下：
测试
插入排序
希尔排序
快速排序
堆排序
冒泡排序
选择排序
比较次数
第三多
越乱（逆）越多
少
乱否差异小
稍多
乱否差异很小
最多
第二多
与乱否无关
移动次数
约为快速排序的两倍
第二少
乱否差异较小
最少
正和逆序少
七、附录
源程序文件名清单：
052376_李明_内部排序算法比较.cpp//主程序
#include<
stdio.h>
stdlib.h>
string.h>
time.h>
windows.h>
winbase.h>
#defineMAXSIZE5000
#defineTRUE1
#defineFALSE0
RedTyper[MAXSIZE+1];
intRandArray[MAXSIZE+1];
srand（2000）;
voidInitLinkList（LinkList*L）{
boolLT（inti,intj,int*CmpNum）{
voidDisplay（LinkList*L）{
r[i-1
升级会员 