数据结构课程设计之综合排序代码及使用方法

题目1：

利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 要求：

1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。

2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

代码如下：

#include //标准输入输出头文件

#include //定义杂项函数及内存分配函数 #include //字符串处理 #include //定义关于时间的函数 #define N 20000

clock_t Start,Now;//时钟 void Wrong()//错误输出

{

printf(\按键错误!请重新输入*****\\n\getchar();//从标准输入获取字符并返回下一个字符 }

void change(int a[])//十个一行输出 { int i;

system(\清除之前的操作 for(i=0;i

if((i-1)==9)

printf(\ printf(\ }

}

//二分插入排序

void Sort_efcr (int a[],int p) {

int t,i,j,low,high,mid; for(i=2;i

high=i-1;

while(low<=high)

{ }

for(j=i-1;j>=low;j--) a[j+1]=a[j]; a[low]=t; } }

//插入排序

void Sort_charu (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 sort_xz(int a[],int p) {

int i,j,k;

for(i=0;i

k=i;

for(j=i+1;j

int temp; temp=a[k]; a[k]=a[i]; a[i]=temp; }//交换 }

}

void sort_mp(int a[],int p) {

mid=(low+high)/2; if(a[mid]>t) high=mid-1; else low=mid+1;

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;

}//a[j]往堆顶方向移 else j=n+1;

}

a[i]=t;

}//不移动，返回堆顶

void sort_d(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--)//n-1次筛选 { t=a[0]; a[0]=a[i]; a[i]=t;

creatheap(a,0,i-1);} }

//插入排序时间

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

int i;double time;

int b[N];

for(i=0;i

b[i]=a[i];//函数值的调用 Start=clock();

Sort_charu(b,p); //执行算法

Now=clock();

time=((double)(Now- Start))/CLK_TCK;//执行算法前后的时间差

if(p!=6)

{change(b);getchar();}//如果用户输入选择不为计算时钟，则要选择换行输出 printf(\用直接插入排序法用的时间为%f秒；\

FILE *fp;

fp=fopen(\直接插入排序.txt\在f盘保存一个文本文件 for(i=0;i

//选择排序时间

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

int i;double time; int b[N];

for(i=0;i

Start=clock();

sort_xz(b,p);//执行函数 if(p!=6)

{change(b);getchar();} Now=clock();

time=((double)(Now- Start))/CLK_TCK;//执行算法前后的时间差 printf(\用直接选择排序法用的时间为%f秒；\ FILE *fp;//文件指针

fp=fopen(\直接选择排序.txt\存档 for(i=0;i

fprintf(fp,\读写一个文档 fclose(fp); return(time);