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

.
1、方案设计：
我这次实验通过随机生成30000个随机数，把随机数存到数组中，用这同一组随机数据分别进行四种排序，直接插入排序、直接选择排序、冒泡排序和快速排序。还通过了调用txt文件把运算所需时间导出，分别输出各个算法所需用时并对用时时长再进行冒泡排序算出用时最短的算法。
2、程序代码：
#include
#include
#include
#include
#include
#define N 30000

void Wrong() //输入错误
{
printf("\n语法错误，请重新输入！\n");
getchar();
}
void Disp(int a[]) //清屏
{
int i;
system("cls");
for(i=0; iint a[],int p) //直接插入排序算法
{
int i,j,temp;
for(i=1; i0&&a[j-1]>temp; j--)
a[j]=a[j-1];
a[j]=temp;
}

}

void SelectSort(int a[],int p) //选择排序算法
{

int i,j,k;

for(i=0; i
k=i;
for(j=i+1; jtemp;

for (i=0; ii; j--) //比较,找出本趟最小关键字的记录
if (a[j]n,int p) //快速排序算法
{

int i,j,low,high,temp,top=-1;

struct node
{
int low,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;
jhigh;
if(lowtemp)j--;
if(ii]1;
st[top].high=high;
}
}
}

double TInsertSort(int a[],int p)//计算直接插入排序算法用时
{
int i;
int b[N];
for(i=0; i {0};
QueryPerformanceCounter(&m_liPerfStart);
InsertSort(b,p);
LARGE_INTEGER liPerfNow= {0};
QueryPerformanceCounter(&liPerfNow);
double time=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
b[i]=a[i];
LARGE_INTEGER m_liPerfFreq= {0};
QueryPerformanceFrequency(&m_liPerfFreq);
LARGE_INTEGER m_liPerfStart= {0};
QueryPerformanceCounter(&m_liPerfStart);
SelectSort(b,p);
if(p!=6)
{
Disp(b);
getchar();
}
LARGE_INTEGER liPerfNow= {0};
QueryPerformanceCounter(&liPerfNow);
double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart;
time/=m_liPerfFreq.QuadPart;
printf("\n用直接选择排序法用的时间为%f秒；",time);

FILE *fp;
fp=fopen("直接选择排序.txt","w");

for(i=0; i
fclose(fp);
return(time);
}

double TBubbleSort(int a[],int p)//计算冒泡排序算法用时
{
int i;
int b[N];
for(i=0; irformanceCounter(&m_liPerfStart);
BubbleSort(b,p);
LARGE_INTEGER liPerfNow= {0};
QueryPerformanceCounter(&liPerfNow);
double time=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]=a[i];
LARGE_INTEGER m_liPerfFreq= {0};
QueryPerformanceFrequency(&m_liPerfFreq);
LARGE_INTEGER m_liPerfStart= {0};
QueryPerformanceCounter(&m_liPerfStart);
quicksort(b,N,p);
LARGE_INTEGER liPerfNow= {0};
QueryPerformanceCounter(&liPerfNow);
double time=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 return(time);
}

void BubleSort(double a[]) //时间数组的冒泡排序
{
int i,j;
double temp;
for(i=1; i<6; i++)
{
for(j=4; j>=i; j--)
if(a[j+1] }
}
}

void menu()
{
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");
}

void main()
{
int i,p,a[N];
srand((int)time(NULL)); //随机种子
for(i=0; i printf("谢谢使用!\n");
getchar();
break;
}
double TIMES[5],TIMES1[5];//时间数组

switch(p)
{

case 1:
Disp(a);
FILE *fp;
fp=fopen("随机数.txt","w");
for(i=0; i[i]);
fclose(fp);
getchar();
printf("\n请按任意键继续!");
getchar();
break;
case 2:
TInsertSort(a,p);
printf("\n请按任意键继续!");
getchar();
break;
case 3:
TSelectSort(a,p);
printf("\n请按任意键继续!");
getchar();
break;
case 4:
TBubbleSort(a,p);
printf("\n请按任意键继续!");
getchar();
break;
case 5:
Tquicksort(a,N,p);
printf("\n请按任意键继续!");
getchar();
break;
case 6:
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