C语言四种排序算法时间复杂度比较.docx
《C语言四种排序算法时间复杂度比较.docx》由会员分享，可在线阅读，更多相关《C语言四种排序算法时间复杂度比较.docx（15页珍藏版）》请在冰点文库上搜索。
C语言四种排序算法时间复杂度比较
1、方案设计：
我这次实验通过随机生成30000个随机数，把随机数存到数组中，用这同一组随机数据分别进展四种排序，直接插入排序、直接选择排序、冒泡排序和快速排序。
还通过了调用txt文件把运算所需时间导出，分别输出各个算法所需用时并对用时时长再进展冒泡排序算出用时最短的算法。
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;
}
}
}
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（i{
a[i]=a[j];
i++;
}
while（iif（i{
a[j]=a[i];
j--;
}
}
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）;
}
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\n"）;
printf（"
（1）显示随机数\n"）;
printf（"
（2）直接插入排序\n"）;
printf（"（3）直接选择排序\n"）;
printf（"（4）冒泡排序\n"）;
printf（"（5）快速排序\n"）;
printf（"（6）时间效率比拟\n"）;
printf（"\n请在上述序号中选择一个并输入:
\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:
Disp（a）;
FILE*fp;
fp=fopen（"随机数.txt","w"）;
for（i=0;ifclose（fp）;
getchar（）;
printf（"\n请按任意键继续!
"）;
getchar（）;
break;
case2:
TInsertSort（a,p）;
printf（"\n请按任意键继续!
"）;
getchar（）;
break;
case3:
TSelectSort（a,p）;
printf（"\n请按任意键继续!
"）;
getchar（）;
break;
case4:
TBubbleSort（a,p）;
printf（"\n请按任意键继续!
"）;
getchar（）;
break;
case5:
Tquicksort（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）;
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]!
=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]）;
}
}
printf（"\n请按任意键继续!
"）;
srand（（int）time（NULL））;
for（i=0;i{
a[i]=rand（）%30000+1;
}
getchar（）;
break;
default:
Wrong（）;
printf（"\n请按任意键继续!
"）;
getchar（）;
break;
}
}
}
3、运行结果与分析：
通过屡次运行程序，均显示快速排序算法最快，时间复杂度最低，通过所学的知识来计算，快速排序平均时间复杂度是0（nlog2n），最好情况0（nlog2n），最坏情况0（n2），相对来说，这次实验符合理论规律。
升级会员 