实验2_物联1301班_刘悦_201308080112
- 格式：docx
- 大小：36.67 KB
- 文档页数：4
算法分析与设计实验报告
第 2次实验
由于数据结构与算法分析已经学习过归并排序，所以这里可以直接进行代
附录：完整代码
#include<iostream>
#include<time.h>
#include<iomanip>
#include<stdlib.h>
using namespace std;
int a[999999];
int b[999999];
void ran(int *a, int n)
{
int i;
srand(time(0));
for (i = 0; i < n; i++)
a[i] = rand();
a[i] = '\0';
}
void mergesort(int a[],int temp[],int left,int right) {
if(left==right) return;
int mid=(right+left)/2;
mergesort(a,temp,left,mid);
mergesort(a,temp,mid+1,right);
for(int i=left;i<=right;i++)
temp[i]=a[i];
int i1=left;
int i2=mid+1;
for(int curr=left;curr<=right;curr++)
{
if(i1==mid+1)
a[curr]=temp[i2++];
else if(i2>right)
a[curr]=temp[i1++];
else if(temp[i1]<temp[i2])
a[curr]=temp[i1++];
else a[curr]=temp[i2++];
}
}
int main()
{
int n[5]={1,3,9999,99999,999998};
for(int i=0;i<5;i++)
{
ran(a,n[i]);
clock_t start,end,over;
start=clock();
end=clock();
over=end-start;
start=clock();
cout<<"规模："<<n[i]<<endl;
int j;
if(n[i]<10)
{
cout<<"排序前："<<endl;
for(j=0;j<n[i];j++)
cout<<a[j]<<" ";
cout<<endl;
}
mergesort(a,b,0,n[i]-1);
if(n[i]<10)
{
cout<<"排序后："<<endl;
for(j=0;j<n[i];j++)
cout<<a[j]<<" ";
cout<<endl;
}
end=clock();
printf("The time is %6.3f\n",(double)(end-start-over)/CLK_TCK);
cout<<endl;
}
return 0;
}。
