C语言四种排序算法时间复杂度比较.doc

.
.页脚.
1、方案设计：
我这次实验通过随机生成30000个随机数，把随机数存到数组中，用这同一组随机数据分别进行四种排序，直接插入排序、直接选择排序、冒泡排序和快速排序。还通过了调用txt文件把运算所需时间导出，分别输出各个算法所需用时并对用时时长再进行冒泡排序算出用时最短的算法。
2、程序代码：
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<windows.h>
#include<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("\n");
printf("%-7d",a[i]);
}
}

voidInsertSort(inta[],intp)//直接插入排序算法
{
inti,j,temp;
for(i=1;i<N;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<N-1;i++)
{
k=i;
for(j=i+1;j<N;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;i<N-1;i++)
{
for(j=N-1;j>i;j--)//比较,找出本趟最小关键字的记录
if(a[j]<a[j-1])
{
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<high)
{
temp=a[low];
while(i!=j)
{
while(i<j&&a[j]>temp)j--;
if(i<j)
{
a[i]=a[j];
i++;
}
while(i<j&&a[i]<temp)i++;
if(i<j)
{
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;i<N;i++)
b[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;i<N;i++)
fprintf(fp,"%d",b[i]);

fclose(fp);
return(time);
}