数据结构课程设计排序综合第四次实验Word文档格式.docx
《数据结构课程设计排序综合第四次实验Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计排序综合第四次实验Word文档格式.docx（19页珍藏版）》请在冰点文库上搜索。
doubleTInsertSort（inta[],intp），还有显示菜单的模块voidmenu（）和显示排序结果模块voidDisp（inta[]）等等，各个模块之间可以互相调用，节省了资源。
用case作为各个功能的入口。
用QueryPerformanceFrequency（）和QueryPerformanceCounte（）函数计时，精度比用clock（）高，避免了很多时候因排序速度太快而出现运行时间为0的现象。
用srand函数作为随机数发生器的初始化函数，用rand产生随机数。
把计算得的排序时间存入数组并经冒泡排序得出最快的两种排序法。
下面是所用排序法的算法思想：
（1）直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。
即将记录a[i]（2<
=i<
=n）插入到有序子序列a[1..i-1]中，使记录的有序序列从a[1..i-1]变为a[1..i]，最终使整个文件有序。
共进行n-1趟插入。
最坏时间复杂度是0（n2），平均时间复杂度是0（n2），空间复杂度是O
（1），是稳定排序。
（2）直接选择排序的基本思想是基于选择，开始有序序列长度为零，第i（1<
n）趟简单选择排序是，从无序序列a[i..n]的n-i+1记录中选出关键字最小的记录，和第i个记录交换，使有序序列逐步扩大，最后整个文件有序。
共进行n-1趟选择。
最坏时间复杂度是0（n2），平均时间复杂度是0（n2），空间复杂度是O
（1），是不稳定排序。
（3）冒泡排序：
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。
依此类推，直到第N-1和第N个记录的关键字进行过比较为止。
上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。
然后进行第二趟起泡排序，对前N-1个记录进行同样操作。
一共要进行N-1趟起泡排序。
（4）快速排序思想：
从待排序列中任取一个元素（例如取第一个）作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；
然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。
此时便为有序序列了。
（6）堆排序基本思想是：
堆是n个元素的序列，先建堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前n-1记录重新调整为堆（调堆的过程称为“筛选”），再将堆顶记录和当前堆序列的最后一个记录交换，如此反复直至排序结束。
优点是在时间性能与树形选择排序属同一量级的同时，堆排序只需要一个记录大小供交换用的辅助空间，调堆时子女只和双亲比较。
避免了过多的辅助存储空间及和最大值的比较。
2.3主要算法和处理流程图
3程序实现
3.1程序实现时应考虑的问题
模块化能使节约资源，也方便了程序的调试和增加功能。
3.2主要源代码及说明
#include<
stdio.h>
conio.h>
stdlib.h>
windows.h>
time.h>
#defineN30000
voidWrong（）
{
printf（"
\n=====>
按键错误!
\n"
）;
getchar（）;
}
voidDisp（inta[]）
inti;
system（"
cls"
for（i=0;
i<
N;
i++）
{
if（（i-1）%10==9）
printf（"
%-7d"
a[i]）;
}
voidInsertSort（inta[],intp）//插入排序
{
inti,j,temp;
for（i=1;
i++）
{
temp=a[i];
for（j=i;
j>
0&
&
a[j-1]>
temp;
j--）
a[j]=a[j-1];
a[j]=temp;
}
voidSelectSort（inta[],intp）//选择排序
inti,j,k;
N-1;
k=i;
for（j=i+1;
j<
j++）
if（a[j]<
a[k]）
k=j;
if（k!
=i）
inttemp;
temp=a[k];
a[k]=a[i];
a[i]=temp;
}
voidBubbleSort（inta[],intp）/*冒泡排序算法*/
inti,j,temp;
for（i=0;
for（j=N-1;
i;
j--）/*比较,找出本趟最小关键字的记录*/
if（a[j]<
a[j-1]）
temp=a[j];
/*进行交换,将最小关键字记录前移*/
a[j-1]=temp;
voidcreatheap（inta[],inti,intn）//创建堆
intj;
intt;
t=a[i];
j=2*（i+1）-1;
while（j<
=n）
if（（j<
n）&
（a[j]<
a[j+1]））
j++;
if（t<
a[j]）
{
a[i]=a[j];
i=j;
j=2*（i+1）-1;
}
else
j=n+1;
a[i]=t;
voidheapsort（inta[],intn,intp）//堆排序
inti;
intt;
for（i=n/2-1;
i>
=0;
i--）
creatheap（a,i,n-1）;
for（i=n-1;
=1;
t=a[0];
a[0]=a[i];
a[i]=t;
creatheap（a,0,i-1）;
voidquicksort（inta[],intn,intp）
inti,j,low,high,temp,top=-1;
structnode
intlow,high;
}st[N];
top++;
st[top].low=0;
st[top].high=n-1;
while（top>
-1）
{low=st[top].low;
high=st[top].high;
top--;
i=low;
j=high;
if（low<
high）
{temp=a[low];
while（i!
=j）
{while（i<
j&
a[j]>
temp）j--;
if（i<
j）{a[i]=a[j];
i++;
while（i<
a[i]<
temp）i++;
j）{a[j]=a[i];
j--;
st[top].low=low;
st[top].high=i-1;
st[top].low=i+1;
st[top].high=high;
doubleTInsertSort（inta[],intp）
intb[N];
b[i]=a[i];
LARGE_INTEGERm_liPerfFreq={0};
QueryPerformanceFrequency（&
m_liPerfFreq）;
LARGE_INTEGERm_liPerfStart={0};
QueryPerformanceCounter（&
m_liPerfStart）;
InsertSort（b,p）;
LARGE_INTEGERliPerfNow={0};
liPerfNow）;
doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;
time/=m_liPerfFreq.QuadPart;
if（p!
=6）
{Disp（b）;
\n用直接插入排序法用的时间为%f秒；
"
time）;
FILE*fp;
fp=fopen（"
直接插入排序.txt"
"
w"
fprintf（fp,"
%d"
b[i]）;
fclose（fp）;
return（time）;
doubleTSelectSort（inta[],intp）
for（i=0;
b[i]=a[i];
SelectSort（b,p）;
\n用直接选择排序法用的时间为%f秒；
FILE*fp;
直接选择排序.txt"
fclose（fp）;
doubleTBubbleSort（inta[],intp）
BubbleSort（b,p）;
\n用冒泡排序法用的时间为%f秒；
冒泡排序.txt"
doubleTheapsort（inta[],intn,intp）
heapsort（b,N,p）;
{Disp（b）;
\n用堆排序法用的时间为%f秒；
堆排序.txt"
doubleTquicksort（inta[],intn,intp）
quicksort（b,N,p）;
\n用快速排序法用的时间为%f秒；
fp=fopen（"
快速排序.txt"
return（time）;
voidBubleSort（doublea[]）//时间数组的冒泡排序
inti,j;
doubletemp;
6;
for（j=4;
=i;
if（a[j+1]<
a[j]）
{
temp=a[j+1];
a[j+1]=a[j];
}
voidmenu（）
★☆**************欢迎来到综合排序系统!
****************★☆\n"
☆★☆★\n"
★☆★☆\n"
☆★※※※※※※※☆★\n"
★☆※菜单※★☆\n"
★☆**************
（1）---直接插入排序******************★☆\n"
☆★**************
（2）---直接选择排序******************☆★\n"
★☆**************（3）---冒泡排序******************★☆\n"
☆★**************（4）---快速排序******************☆★\n"
★☆**************（5）---堆排序******************★☆\n"
☆★**************（6）---时间效率比较******************☆★\n"
★☆**************（7）---显示随机数******************★☆\n"
☆★**************（0）---退出******************☆★\n"
★☆★☆\n"
☆★****************************************************☆★\n"
\n====>
请在上述序号中选择一个并输入:
voidmain（）
inti,p,a[N];
srand（（int）time（NULL））;
/*随机种子*/
a[i]=rand（）%50000+1;
while
（1）
system（"
menu（）;
scanf（"
%d"
&
p）;
if（p==0）
=====>
谢谢使用!
getchar（）;
break;
doubleTIMES[5],TIMES1[5];
//时间数组
switch（p）
case1:
TInsertSort（a,p）;
\n请按任意键继续..."
break;
case2:
TSelectSort（a,p）;
case3:
TBubbleSort（a,p）;
case4:
Tquicksort（a,N,p）;
case5:
Theapsort（a,N,p）;
case6:
TIMES1[1]=TIMES[1]=TInsertSort（a,p）;
TIMES1[2]=TIMES[2]=TSelectSort（a,p）;
TIMES1[3]=TIMES[3]=TBubbleSort（a,p）;
TIMES1[4]=TIMES[4]=Tquicksort（a,N,p）;
TIMES1[5]=TIMES[5]=Theapsort（a,N,p）;
BubleSort（TIMES）;
\n\n"
printf（"
排序这组数据两种较快的排序法分别是：
if（TIMES[1]==TIMES1[1]）printf（"
直接插入排序:
%f秒!
TIMES[1]）;
if（TIMES[1]==TIMES1[2]）printf（"
直接选择排序:
if（TIMES[1]==TIMES1[3]）printf（"
冒泡排序:
if（TIMES[1]==TIMES1[4]）printf（"
快速排序:
if（TIMES[1]==TIMES1[5]）printf（"
堆排序:
if（TIMES[1]!
=TIMES[2]）
if（TIMES[2]==TIMES1[1]）printf（"
TIMES[2]）;
if（TIMES[2]==TIMES1[2]）printf（"
直接选择排序%f秒!
if（TIMES[2]==TIMES1[3]）printf（"
冒泡排序%f秒!
if（TIMES[2]==TIMES1[4]）printf（"
快速排序%f秒!
if（TIMES[2]==TIMES1[5]）printf（"
堆排序%f秒!
}
}printf（"
srand（（int）time（NULL））;
i++）{a[i]=rand（）%30000+1;
}getchar（）;
case7:
Disp（a）;
随机数.txt"
i++）fprintf（fp,"
default:
Wrong（）;
\n请按任意键继续..
升级会员 