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

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; i

{

if((i-1)%10==9)

printf("\n");

printf("%-7d",a[i]);

}

}

void InsertSort(int a[],int p) //直接插入排序算法

{

int i,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;

}

}

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

{

int i,j,k;

for(i=0; i

{

k=i;

for(j=i+1; j

if(a[j]

k=j;

if(k!=i)

{

int temp;

temp=a[k];

a[k]=a[i];

a[i]=temp;

}

}

}

void BubbleSort(int a[],int p) //冒泡排序算法

{

int i,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;

}

}

}

void quicksort(int a[],int 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;

j=high;

if(low

{

temp=a[low];

while(i!=j)

{

while(itemp)j--;

if(i

{

a[i]=a[j];

i++;

}

while(i

if(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;

}

}

}

double TInsertSort(int a[],int p)//计算直接插入排序算法用时{

int i;

int b[N];

for(i=0; i

b[i]=a[i];

LARGE_INTEGER m_liPerfFreq= {0};

QueryPerformanceFrequency(&m_liPerfFreq);

LARGE_INTEGER m_liPerfStart= {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

fprintf(fp,"%d ",b[i]);

fclose(fp);

return(time);

}

double TSelectSort(int a[],int p)//计算选择排序用时

{

int i;

int b[N];

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)

{