#i n c l u d e<i o s t r e a m.h>
#include <stdlib.h>
#include <iomanip.h>
#include <time.h>
#include <stdio.h>
const int N=1000;//数据量，用于检测算法质量
const int M=1000;//执行次数
//冒泡排序（递增）
void Bubblesort(int r[],int n)
{
int flag=1;//flag为0停止排序
for(int i=1;i<n;i++)
{
flag=0;
for(int j=n-1;j>=i;j--)
if(r[j]<r[j-1])
{
int t=r[j];
r[j]=r[j-1];
r[j-1]=t;
flag=1;
}
if(flag==0)
return;
}
}
//快速排序
void quicksort(int r[],int left,int right)
{
int i,j;
int swap;
i=left;j=right;
swap=r[left];
while(i<j)
{
while((i<j)&&(swap<r[j]))j--;
if(i<j)
{
r[i]=r[j];
i++;
}
while((i<j)&&(swap>r[i]))i++;
if(i<j)
{
r[j]=r[i];
j--;
}
}
r[i]=swap;
if(i>left)
quicksort(r,left,i-1);
if(i<right)
quicksort(r,i+1,right);
return;
}
//堆排序先建立堆
void creatheap(int r[],int i,int n) {
int j;
int t;
t=r[i];j=2*i;
while(j<n)
{
if((j<n)&&(r[j]<r[j+1]))j++;
if(t<r[j])
{
r[i]=r[j];
i=j;j=2*i;
}
else j=n;
r[i]=t;
}
}
//堆排序
void heapsort(int r[],int n)
{
int t;
for(int i=n/2;i>=0;i--)
creatheap(r,i,n);
for(i= n-1;i>=0;i--)
{
t=r[0];
r[0]=r[i];
r[i]=t;
creatheap(r,0,i-1);
}
}
//二路归并
void merge(int r[],int r1[],int low,int mid,int high)//进行二合一的函数
{
int i=low,j=mid+1,k=low;
while((i<=mid)&&(j<=high))
{
if(r[i]<=r[j])
r1[k++]=r[i++];
else
r1[k++]=r[j++];
}
while(i<=mid)
r1[k++]=r[i++];
while(j<=high)
r1[k++]=r[j++];
}
void mergepass(int r[],int r1[],int length)//用来区分填入merge函数的变量计算式{
int i=0,j;
while(i+2*length<=N)
{
merge(r,r1,i,i+length-1,i+2*length-1);
i=i+2*length;
}
if(i+length-1<N-1)
merge(r,r1,i,i+length-1,N-1);
else
for(j=i;j<N;j++)
r1[j]=r[j];
}
void mergesort(int r[])//二路并归总算法
{
int length=1;
int r1[N+1];
while(length<N)
{
mergepass(r,r1,length);
length=2*length;
mergepass(r1,r,length);
length=2*length;
}
}
//进行输出
void print(int r[],int n)
{
for(int i=0;i<=n-1;i++)
{
if(i%10==0){cout<<endl;}
cout<<r[i]<<setw(6);
}
cout<<endl;
}
//主函数
void main()
{
int i,j,k;
int r[N],a[N];
clock_t start, finish;
double duration;
cout<<"请选择排序方式,1、冒泡法；2、快速排序法；3、堆排序法；4、二路并归法"<<endl;
cin>>j;
srand((unsigned)time(NULL));
for(i=0;i<N;i++)
{
a[i]=rand()%10000;
}
switch(j)
{
case(1):
{
cout<<"冒泡法";
start = clock();
for(i=0;i<M;i++)
{
k=N-1;
while(k+1)
{
r[k]=a[k];
k--;
}
Bubblesort(r,N);//冒泡法
}
finish = clock();
duration = (double)(finish - start)/1000;
print(r,N);
printf( "%f seconds\n", duration );
}break;
case(2):
{
cout<<"快速排序法";
start = clock();
for(i=0;i<M;i++)
{
k=N-1;
while(k+1)
{
r[k]=a[k];
k--;
}
quicksort(r,0,N-1);//快速排序法
}
finish = clock();
duration = (double)(finish - start)/1000; print(r,N);
printf( "%f seconds\n", duration );
}break;
case(3):
{
cout<<"堆排序法";
start = clock();
for(i=0;i<M;i++)
{
k=N-1;
while(k+1)
{
r[k]=a[k];
k--;
}
heapsort(r,N);//堆排序法
}
finish = clock();
duration = (double)(finish - start)/1000; print(r,N);
printf( "%f seconds\n", duration );
}break;
case(4):
{
cout<<"二路并归法";
start = clock();
for(i=0;i<M;i++)
{
k=N-1;
while(k+1)
{
r[k]=a[k];
k--;
}
mergesort(r);//二路并归法
}
finish = clock();
duration = (double)(finish - start)/1000;
print(r,N);
printf( "%f seconds\n", duration );
}break;
}
}。