数据结构课程设计(排序综合)第四次实验(2)

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 creatheap(int a[],int i,int n) //{

int j; int t;

t=a[i];

j=2*(i+1)-1; while(j<=n) {

if((j a[i]=a[j]; i=j;

j=2*(i+1)-1; } else

j=n+1; }

a[i]=t; }

void heapsort(int a[],int n,int p) // {

int i; int t;

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);} }

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]=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

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(\用直接插入排序法用的时间为%f秒；\FILE *fp;

fp=fopen(\直接插入排序.txt\

for(i=0;i

fprintf(fp,\

fclose(fp); return(time); }

double TSelectSort(int a[],int p) {

int i; int b[N];

for(i=0;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(\用直接选择排序法用的时间为%f秒；\

FILE *fp;

fp=fopen(\直接选择排序.txt\

for(i=0;i

fprintf(fp,\fclose(fp);return(time); }

double TBubbleSort(int a[],int p) {

int i; int b[N];

for(i=0;i

LARGE_INTEGER m_liPerfFreq={0};

QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart={0};

QueryPerformanceCounter(&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(\用冒泡排序法用的时间为%f秒；\

FILE *fp;

fp=fopen(\冒泡排序.txt\

for(i=0;i

fprintf(fp,\fclose(fp);return(time); }

double Theapsort(int a[],int n,int p) {

int i; int b[N];

for(i=0;i

LARGE_INTEGER m_liPerfFreq={0};

QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart={0};

QueryPerformanceCounter(&m_liPerfStart); heapsort(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(\用堆排序法用的时间为%f秒；\

FILE *fp;

fp=fopen(\堆排序.txt\

for(i=0;i

fprintf(fp,\fclose(fp);return(time); }

double Tquicksort(int a[],int n,int p) {

int i; int b[N];

for(i=0;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(\用快速排序法用的时间为%f秒；\

FILE *fp;fp=fopen(\快速排序.txt\ for(i=0;i

fprintf(fp,\

fclose(fp); return(time); }