0

```我的合并排序代码是：

#include<iostream>
#include<iomanip>
#include<ctime>
using namespace std;
void merge(int A[], int p, int q, int r)
{
int len1=q-p+1;
int len2=r-q;
int *L=new int[len1+1];
int *R=new int[len2+1];

for (int i=0;i<len1;i++)
{
L[i]=A[p+i];
}
for (int j=0;j<len2;j++)
{
R[j]=A[q+1+j];
}

L[len1]=R[len2]=INT_MAX;

int i=0,j=0;
for (int k=p;k<=r;k++)
{
if (L[i]<R[j])
{
A[k]=L[i];
i++;
}
else
{
A[k]=R[j];
j++;
}
}
}
void mergeSort(int A[], int p, int r)
{
if (p<r)
{
int	q;
q=(r+p)/2;
mergeSort(A,p,q);
mergeSort(A,q+1,r);
merge(A,p,q,r);
}
}
int main()
{
clock_t start,finish;
start=clock();
cout<<"This is merge sort!"<<endl;
cout<<endl;
int n;
cout<<"How many numbers to sort: ";
cin>>n;
int *a=new int[n];
cout<<"Please input "<<n<<"nonnegative numbers:";
for (int i=0; i<n;i++)
{
cin>>a[i];
}
mergeSort(a,0,n-1);
for(int j=0;j<n;j++)
{
cout<<setw(7)<<a[j];
}
cout<<endl;
finish=clock();
cout<<"It takes "<<(finish-start)<<" millisecond!"<<endl;
return 0;
}

How many numbers to sort?    10000(我输入的)
For increasingly order, it will take 12senconds to sort 10000 numbers;
For decreasingly order, it will take 13 seconds to sort 10000 numbers;
For random order, it will take 14 seconds to sort 10000 numbers.

<无标签>

ayumily51