快排和归并

#include<stdio.h>
#include<time.h>
#include<windows.h>
int num[100000005];
void ss(int *p,int left,int right)
{
int i=left,j=right,k=p[i];
if(left>=right) return;
while(i<j)
{
while(i<j&&p[j]>k) --j;
if(i<j) p[i++]=p[j];
while(i<j&&p[i]<k) ++i;
if(i<j) p[j--]=p[i];
}
p[i]=k;
ss(p,left,i-1);
ss(p,i+1,right);
}
int main()
{
freopen("in","r",stdin);
int n,i;
scanf("%d",&n);
for(i=0;i!=n;++i) scanf("%d",&num[i]);
clock_t lll=clock();
ss(num,0,n-1);
printf("%d",clock()-lll);
return 0;
}

#include<stdio.h>
#include<time.h>
int source[100000005],temp[100000005];
void mymerge(int *s,int *t,int start,int mid,int end);
void mymergrsort(int *s,int *t,int start,int end);
void mymerge(int *s,int *t,int start,int mid,int end)
{
int i=start,j=mid+1,k=start;
while(i!=mid&&j!=end)
{
if(s[i]<s[j]) t[k++]=s[i++];
else t[k++]=s[j++];
}
while(i!=mid+1) t[k++]=s[i++];
while(j!=end+1) t[k++]=s[j++];
for(i=start;i<=end;++i) s[i]=t[i];
}
void mymergesort(int *s,int *t,int start,int end)
{
int mid=(start+end)/2;
if(start<end)
{
mymergesort(s,t,start,mid);
mymergesort(s,t,mid+1,end);
mymerge(s,t,start,mid,end);
}
}
int main()
{
freopen("in","r",stdin);
int n,i;
scanf("%d",&n);
for(i=0;i!=n;++i) scanf("%d",&source[i]);
clock_t lll=clock();
mymergesort(source,temp,0,n-1);
printf("%d",clock()-lll);
return 0;
}

在1亿个随机数的测试下，快排16555ms，归并25160