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

#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=pj<rj++)

{

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+1k<=jk++ )

{

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 = it <= nt++)

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 >= 1k /= 2 )

{

for ( i=k+1i<=ni++ )

{

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=1i<=ni++)

{

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=0i<ni++)

{

lowindex = i

for ( j = i+1j<=nj++)

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=0i<ni++)

for (j=n-1j>=i+1j--)

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=0j<100000j++)

{

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=0j<100000j++)

{

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

}

排序算法时间效率的比较

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

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

从计算机的本质看有功能性和可编程性二个历液基本特性，以下哪个不属于功能性（）A

A. 编写复杂程序

B. 数据计算

C. 输入输出

D. 结果存储、

编写复杂程序属于计算机的可编程性

拓展

电脑的作用有哪些. 电脑，也称计算机（Computer），全称电子计算机，电脑是俗称。. 它是一种能够按照程序运行，自动、高速处理海岁烂让量数据的现代化智能电子乎局设备。. 由硬件和软件所组成，没有安装任何软件的计算机称为裸机。. 常见的形式有台式计算机、笔记本计算机、平板电脑和大型计算机等，较先进的计算机有生物计算机、光子计算机、量子计算机等。.

---