0
回答
求助c++合并排序的一个问题
滴滴云服务器,限时包月0.9元,为开发者而生>>>   
我的合并排序代码是:

#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;
}
代码运行没问题,是输入了N个数字之后,自动排序,而且算了运行时间。
我现在的问题是,要写一个附加程序,这个C++程序可以只让你输入你要排序的数据的个数N,从1到100万都可以,然后这个程序可以内部生成这N个数的三个数组,分别是升序,降序和无序,最后的output是这三个升序,降序和无序数组使用我上面那个排序代码所需要的运行时间,以便比较;
比如如果写出来了,黑框框出现的是:
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
发帖于4年前 0回/89阅
顶部