用C语言编写一个复杂程序 急需

Question

急需一个C语言原创程序，该C语言编程题设计中尽可能的应用到：数组、函数、指针、结构体、文件包含、基本算法等知识，同时对本程序进行说明，既：
（1）本程序的题目
（2）本程序解决什么问题
（3）应用到了哪些知识点

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/**快速排序版本1*/

int PARTITION(int A[],int p,int r)///p,r是数组下标
{
int x=A[r];
int i=p-1;
int j;
int tmp;

for(j=p;j<r;j++)
{
if(A[j]<x)
{
i++;
tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}
}

i++;
tmp=A[i];
A[i]=A[r];
A[r]=tmp;

return i;
}
void QUICKSORT(int A[],int p,int r)
{
int q;
if(p<r)
{
q=PARTITION(A,p,r);
QUICKSORT(A,p,q-1);
QUICKSORT(A,q+1,r);
}
}

/**快速排序版本2*/
int findpivot( int i, int j ,int A[])
{
int firstkey;
int k;
firstkey = A[i];

for ( k=i+1; k<=j; k++ )
{
if ( A[k] > firstkey )
{
return k;
}
else if ( A[k] < firstkey )
{
return i;
}
}
return -1; //注意这个函数什么时候返回-1
}
int partion ( int i, int j, int pivot ,int A[]) //以中点pivot 为界交换
{
int L, R;
L = i;
R = j; //两个移动游标
int temp;
do
{
temp = A[L];
A[L] = A[R];
A[R] = temp;

while ( A[L] < pivot )
L = L +1 ;
while ( A[R] >= pivot )
R = R -1 ;
}
while ( L <= R );
return L;
}
void quicksort( int i, int j ,int A[])
{
int pivot ;
int pivotindex , k;
pivotindex = findpivot( i, j ,A); //pivotindex可以就选第一个，可这是怎么判断结束呢，根据快排的段长
if (pivotindex!=-1)
{
pivot = A[pivotindex];
k = partion ( i, j, pivot ,A) ;
quicksort( i, k-1, A);
quicksort( k, j , A);
}
}

/**归并排序*/
void merge ( int l , int m, int n, int A[], int B[] )
{
int i, j, k, t ;
i = l ; //i是前段下标计数器
k = l ;
j = m+1 ; //后段开始下标 j是后段下标计数器
while (( i <= m ) && ( j <= n )) //应该将两段归并到一段（l 至 n），这个循环只是找到了“一段”的较小的一半
{
if ( A[i] <= A[j] )
B[k++] = A [i++] ;
else
B[k++] = A[j++] ;
}
if ( i > m ) //这是处理对称两段 这时k已经等于后段的起始地址了
for ( t = j ; t <= n ; t++ )
B[k+t-j] = A[t] ;
else //处理非对称两段 这时i已经等于后段的起始地址了
for ( t = i ; t <= m ; t++ )
B[k+t-i] = A[t] ;
}

void mpass ( int n,int l,int A[],int B[])
{
int i, t;
i = 0;
while ( i <= (n-2*l+1) ) //不足两段时终止
{
merge( i,i+l-1,i+2*l-1,A,B); //参数：起始下标 前段终止下标 后段终止下标 （两个段长都是 l ）
i = i + 2*l; //计算出下一个起始下标
}
if ((i+l-1)<n ) //余下的一段有余 既是不对称两段，但还能合并
merge ( i, i+l-1, n, A, B);
else //余下的不足一段 已不能合并
for ( t = i; t <= n; t++)
B[t] = A[t];
}

void mergesort( int n,int A[])
{
int l ;
int *B = (int *)malloc(n*sizeof(int));
l =1 ;
while ( l < n )
{
mpass( n, l, A, B) ;
l = 2*l;
mpass( n, l, B, A) ;
l = 2*l;
}
}

/**希尔排序*/
void Shellsort ( int n,int A[] )
{
int i,j,k,x;
for ( k = n/2; k >= 1; k /= 2 )
{
for ( i=k+1; i<=n; i++ )
{
x = A[i];
j = i-k;
while ( (j>=0) && (x<A[j]) )
{
A[j+k] = A[j];
j -= k;
}
A[j+k] = x;
}
}
}

/**插入排序*/
void insertsort ( int n, int A[] )
{
int i, j ;
int temp;
//A[0]= -1 ;
for (i=1; i<=n; i++)
{
j=i;
while (A[j]<A[j-1])
{
temp = A[j];
A[j] = A[j-1];
A[j-1] = temp;

j=j-1;
if (j==0)
break;
}
}
}

/**选择排序*/
void selectsort ( int n, int A[])
{
int i, j,lowindex;
int temp;
for (i=0; i<n; i++)
{
lowindex = i;
for ( j = i+1; j<=n; j++)
if ( A[j] < A[lowindex] )
lowindex = j;
temp = A[i];
A[i] = A[lowindex];
A[lowindex] = temp;
}
}

/**冒泡排序*/
void bubblesort(int n,int A[]) //n为元素个数
{
int i,j;
int temp;
for (i=0;i<n;i++)
for (j=n-1;j>=i+1;j--)
if (A[j]<A[j-1])
{
temp = A[j];
A[j] = A[j-1];
A[j-1] = temp;
}
}

/**读文件*/
void ReadFile(int a[])
{
FILE *fin;
int j;
if ((fin=fopen("data.txt","r"))==NULL)
{
printf("打开文件失败\n");
exit (2);
}
j=0;
while (fscanf(fin,"%d",&a[j])!=EOF)
j++;
fclose(fin);
}

/**写文件*/
void WriteFile(char *filename,int a[])
{
FILE *fout;
int j;
if ((fout=fopen(filename,"w"))==NULL)
{
printf("打开文件失败\n");
exit (2);
}
for (j=0;j<100000;j++)
{
fprintf(fout,"%d\n",a[j]);

}
fclose(fout);
}
int main()
{
clock_t s,f;
double dura;
FILE *fout;
int a[100000];
int j;

/*生成随机数写入文件*/
if ((fout=fopen("data.txt","w"))==NULL)
{
printf("打开文件失败\n");
exit (2);
}
for (j=0;j<100000;j++)
{
fprintf(fout,"%d\n",rand());
}
fclose(fout);

/*快速排序版本1*/
ReadFile(a);
s=clock();
QUICKSORT(a,0,99999);
f=clock();
dura=(double)(f-s)/CLOCKS_PER_SEC;
/*结果写入文件*/
WriteFile("QUICKSORT1.txt",a);
printf("快速排序1： %lf\n",dura);

/*快速排序版本2*/
ReadFile(a);
s=clock();
quicksort(0,99999,a);
f=clock();
dura=(double)(f-s)/CLOCKS_PER_SEC;
/*结果写入文件*/
WriteFile("quicksort2.txt",a);
printf("快速排序2： %lf\n",dura);

/*
* 归并排序
*从文件读出
*/
ReadFile(a);
s=clock();
mergesort(100000,a);
f=clock();
dura=(double)(f-s)/CLOCKS_PER_SEC;
/*结果写入文件*/
WriteFile("mergesort.txt",a);
printf("归并排序 ： %lf\n",dura);

/*
* 希尔排序
*/
ReadFile(a);
s=clock();
Shellsort(100000,a);
f=clock();
dura=(double)(f-s)/CLOCKS_PER_SEC;
/*结果写入文件*/
WriteFile("shellsort.txt",a);
printf("希尔排序 ： %lf\n",dura);

/*
* 选择排序*/

ReadFile(a);
s=clock();
selectsort(100000,a);
f=clock();
dura=(double)(f-s)/CLOCKS_PER_SEC;
/*结果写入文件*/
WriteFile("selectsort.txt",a);
printf("选择排序： %lf\n",dura);

/*
* 插入排序*/

ReadFile(a);
s=clock();
insertsort(100000,a);
f=clock();
dura=(double)(f-s)/CLOCKS_PER_SEC;
/*结果写入文件*/
WriteFile("insertsort.txt",a);
printf("插入排序： %lf\n",dura);

/*
* 气泡排序
*从文件读出*/

ReadFile(a);
s=clock();
bubblesort(100000,a);
f=clock();
dura=(double)(f-s)/CLOCKS_PER_SEC;
/*结果写入文件*/
WriteFile("bubblesort.txt",a);
printf("气泡排序： %lf\n",dura);

return 0;
}

排序算法时间效率的比较

归并排序，希尔排序，快速排序，选择排序，冒泡排序的时间效率的比较

上面说的全用了，而且算法包括各种排序算法