综合排序sort.docx
《综合排序sort.docx》由会员分享，可在线阅读，更多相关《综合排序sort.docx（19页珍藏版）》请在冰点文库上搜索。
综合排序sort
1问题要求及任务描述
1.1题目要求
利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。
要求：
1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。
并把排序后的结果保存在不同的文件中。
2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。
3）如果采用4种或4种以上的方法者，可适当加分。
1.2主要任务
分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。
从时间的角度来分析各种排序的性能。
通过测试多组数据来掌握各种排序的方法及适用场合，并能在解决实际问题灵活运用。
在编写代码的时候，有以下几个问题：
（1）建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功能。
并且要求能循环使用系统。
（2）分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。
（3）通过冒泡排序法来测试每组数据用那种排序算法最优。
2解决问题的主要思路和方法
2.1关键问题
核心问题:
排列组合
数据模型（逻辑结构）：
30000个随机数
存储结构:
保存在不同的文件
核心算法:
直接插入、直接选择、冒泡、快速排序、堆排序的算法
输入数据:
初始化数组：
rand（）%50000+1
输出数据：
排序内容到文件，排序所用时间
2.2拟采用解决问题的方法
把程序分为多个模块，有的是排序的算法如：
voidInsertSort（inta[],intp），有的是计算排序所用时间的函数如：
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<=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
#include
#include
#include
#include
#defineN30000
voidWrong（）
{
printf（"\n=====>按键错误!
\n"）;
getchar（）;
}
voidDisp（inta[]）
{
inti;
system（"cls"）;
for（i=0;i{
if（（i-1）%10==9）
printf（"\n"）;
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;
for（i=0;i{
k=i;
for（j=i+1;jif（a[j]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;i{
for（j=N-1;j>i;j--）/*比较,找出本趟最小关键字的记录*/
if（a[j]{
temp=a[j];/*进行交换,将最小关键字记录前移*/
a[j]=a[j-1];
a[j-1]=temp;
}
}
}
voidcreatheap（inta[],inti,intn）//创建堆
{
intj;
intt;
t=a[i];
j=2*（i+1）-1;
while（j<=n）
{
if（（jj++;
if（t{
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;i>=1;i--）
{
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{temp=a[low];
while（i!
=j）
{while（itemp）j--;
if（iwhile（iif（i}
a[i]=temp;
top++;st[top].low=low;st[top].high=i-1;
top++;st[top].low=i+1;st[top].high=high;
}
}
}
doubleTInsertSort（inta[],intp）
{
inti;
intb[N];
for（i=0;ib[i]=a[i];
LARGE_INTEGERm_liPerfFreq={0};
QueryPerformanceFrequency（&m_liPerfFreq）;
LARGE_INTEGERm_liPerfStart={0};
QueryPerformanceCounter（&m_liPerfStart）;
InsertSort（b,p）;
LARGE_INTEGERliPerfNow={0};
QueryPerformanceCounter（&liPerfNow）;
doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;
time/=m_liPerfFreq.QuadPart;
if（p!
=6）
{Disp（b）;getchar（）;}
printf（"\n用直接插入排序法用的时间为%f秒；",time）;
FILE*fp;
fp=fopen（"直接插入排序.txt","w"）;
for（i=0;ifprintf（fp,"%d",b[i]）;
fclose（fp）;
return（time）;
}
doubleTSelectSort（inta[],intp）
{
inti;
intb[N];
for（i=0;ib[i]=a[i];
LARGE_INTEGERm_liPerfFreq={0};
QueryPerformanceFrequency（&m_liPerfFreq）;
LARGE_INTEGERm_liPerfStart={0};
QueryPerformanceCounter（&m_liPerfStart）;
SelectSort（b,p）;
if（p!
=6）
{Disp（b）;getchar（）;}
LARGE_INTEGERliPerfNow={0};
QueryPerformanceCounter（&liPerfNow）;
doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;
time/=m_liPerfFreq.QuadPart;
printf（"\n用直接选择排序法用的时间为%f秒；",time）;
FILE*fp;
fp=fopen（"直接选择排序.txt","w"）;
for（i=0;ifprintf（fp,"%d",b[i]）;
fclose（fp）;return（time）;
}
doubleTBubbleSort（inta[],intp）
{
inti;
intb[N];
for（i=0;ib[i]=a[i];
LARGE_INTEGERm_liPerfFreq={0};
QueryPerformanceFrequency（&m_liPerfFreq）;
LARGE_INTEGERm_liPerfStart={0};
QueryPerformanceCounter（&m_liPerfStart）;
BubbleSort（b,p）;
LARGE_INTEGERliPerfNow={0};
QueryPerformanceCounter（&liPerfNow）;
doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;
time/=m_liPerfFreq.QuadPart;
if（p!
=6）
{Disp（b）;getchar（）;}
printf（"\n用冒泡排序法用的时间为%f秒；",time）;
FILE*fp;
fp=fopen（"冒泡排序.txt","w"）;
for（i=0;ifprintf（fp,"%d",b[i]）;
fclose（fp）;return（time）;
}
doubleTheapsort（inta[],intn,intp）
{
inti;
intb[N];
for（i=0;ib[i]=a[i];
LARGE_INTEGERm_liPerfFreq={0};
QueryPerformanceFrequency（&m_liPerfFreq）;
LARGE_INTEGERm_liPerfStart={0};
QueryPerformanceCounter（&m_liPerfStart）;
heapsort（b,N,p）;
LARGE_INTEGERliPerfNow={0};
QueryPerformanceCounter（&liPerfNow）;
doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;
time/=m_liPerfFreq.QuadPart;
if（p!
=6）
{Disp（b）;getchar（）;}
printf（"\n用堆排序法用的时间为%f秒；",time）;
FILE*fp;
fp=fopen（"堆排序.txt","w"）;
for（i=0;ifprintf（fp,"%d",b[i]）;
fclose（fp）;return（time）;
}
doubleTquicksort（inta[],intn,intp）
{
inti;
intb[N];
for（i=0;ib[i]=a[i];
LARGE_INTEGERm_liPerfFreq={0};
QueryPerformanceFrequency（&m_liPerfFreq）;
LARGE_INTEGERm_liPerfStart={0};
QueryPerformanceCounter（&m_liPerfStart）;
quicksort（b,N,p）;
LARGE_INTEGERliPerfNow={0};
QueryPerformanceCounter（&liPerfNow）;
doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;
time/=m_liPerfFreq.QuadPart;
if（p!
=6）
{Disp（b）;getchar（）;}
printf（"\n用快速排序法用的时间为%f秒；",time）;
FILE*fp;fp=fopen（"快速排序.txt","w"）;
for（i=0;ifprintf（fp,"%d",b[i]）;
fclose（fp）;return（time）;
}
voidBubleSort（doublea[]）//时间数组的冒泡排序
{
inti,j;
doubletemp;
for（i=1;i<6;i++）
{
for（j=4;j>=i;j--）
if（a[j+1]{
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
}
}
voidmenu（）
{
printf（"★☆**************欢迎来到综合排序系统!
****************★☆\n"）;
printf（"☆★☆★\n"）;
printf（"★☆★☆\n"）;
printf（"☆★☆★\n"）;
printf（"★☆★☆\n"）;
printf（"☆★☆★\n"）;
printf（"☆★※※※※※※※☆★\n"）;
printf（"★☆※菜单※★☆\n"）;
printf（"☆★※※※※※※※☆★\n"）;
printf（"☆★☆★\n"）;
printf（"★☆**************
（1）---直接插入排序******************★☆\n"）;
printf（"☆★**************
（2）---直接选择排序******************☆★\n"）;
printf（"★☆**************（3）---冒泡排序******************★☆\n"）;
printf（"☆★**************（4）---快速排序******************☆★\n"）;
printf（"★☆**************（5）---堆排序******************★☆\n"）;
printf（"☆★**************（6）---时间效率比较******************☆★\n"）;
printf（"★☆**************（7）---显示随机数******************★☆\n"）;
printf（"☆★**************（0）---退出******************☆★\n"）;
printf（"★☆★☆\n"）;
printf（"☆★****************************************************☆★\n"）;
printf（"\n====>请在上述序号中选择一个并输入:
"）;
}
voidmain（）
{
inti,p,a[N];
srand（（int）time（NULL））;/*随机种子*/
for（i=0;ia[i]=rand（）%50000+1;
while
（1）
{
system（"cls"）;
menu（）;
scanf（"%d",&p）;
if（p==0）
{
printf（"=====>谢谢使用!
\n"）;
getchar（）;
break;
}
doubleTIMES[5],TIMES1[5];//时间数组
switch（p）
{
case1:
TInsertSort（a,p）;printf（"\n请按任意键继续..."）;getchar（）;break;
case2:
TSelectSort（a,p）;printf（"\n请按任意键继续..."）;getchar（）;break;
case3:
TBubbleSort（a,p）;printf（"\n请按任意键继续..."）;getchar（）;break;
case4:
Tquicksort（a,N,p）;printf（"\n请按任意键继续..."）;getchar（）;break;
case5:
Theapsort（a,N,p）;printf（"\n请按任意键继续..."）;getchar（）;break;
case6:
system（"cls"）;
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）;getchar（）;
BubleSort（TIMES）;
printf（"\n\n"）;
{
printf（"排序这组数据两种较快的排序法分别是：
\n"）;
if（TIMES[1]==TIMES1[1]）printf（"直接插入排序:
%f秒!
\n",TIMES[1]）;
if（TIMES[1]==TIMES1[2]）printf（"直接选择排序:
%f秒!
\n",TIMES[1]）;
if（TIMES[1]==TIMES1[3]）printf（"冒泡排序:
%f秒!
\n",TIMES[1]）;
if（TIMES[1]==TIMES1[4]）printf（"快速排序:
%f秒!
\n",TIMES[1]）;
if（TIMES[1]==TIMES1[5]）printf（"堆排序:
%f秒!
\n",TIMES[1]）;
if（TIMES[1]!
=TIMES[2]）
{
if（TIMES[2]==TIMES1[1]）printf（"直接插入排序:
%f秒!
\n",TIMES[2]）;
if（TIMES[2]==TIMES1[2]）printf（"直接选择排序%f秒!
\n",TIMES[2]）;
if（TIMES[2]==TIMES1[3]）printf（"冒泡排序%f秒!
\n",TIMES[2]）;
if（TIMES[2]==TIMES1[4]）printf（"快速排序%f秒!
\n",TIMES[2]）;
if（TIMES[2]==TIMES1[5]）printf（"堆排序%f秒!
\n",TIMES[2]）;
}
}printf（"\n请按任意键继续..."）;srand（（int）time（NULL））;
for（i=0;icase7:
Disp（a）;FILE*fp;fp=fopen（"随机数.txt","w"）;
for（i=0;idefault:
Wrong（）;printf（"\n请按任意键继续..."）;getchar（）;break;
}
}
}
升级会员 