归并排序

2014年3月6日2,6620

学了一下归并排序

#include<iostream>
#include<cstdio>
using namespace std;
int num[100001],n;
void merge(int *num,int *a,int l,int r)
{
     int i=l,j,k=l,m=(l+r)>>1;
     for(j=m+1;i<=m&&j<=r;k++)
     {
             if(num[i]<=num[j])a[k]=num[i++];
             else a[k]=num[j++];
             }
     while(i<=m)a[k++]=num[i++];
     while(j<=r)a[k++]=num[j++];
 }
void sort(int *num,int *a,int l,int r)
{
     if(l==r)a[l]=num[l];
     else 
     {
          int t[100001];
          int m=(l+r)>>1;
          sort(num,t,l,m);
          sort(num,t,m+1,r);
          merge(t,a,l,r); 
          } 
 }
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&num[i]);
    sort(num,num,1,n);
    for(int i=1;i<=n;i++)printf("%d ",num[i]);
    return 0;
}

#include<iostream>

#include<cstdio>

using namespace std;

int num[100001],n;

void merge(int *num,int *a,int l,int r)

{

int i=l,j,k=l,m=(l+r)>>1;

for(j=m+1;i<=m&&j<=r;k++)

{

if(num[i]<=num[j])a[k]=num[i++];

else a[k]=num[j++];

}

while(i<=m)a[k++]=num[i++];

while(j<=r)a[k++]=num[j++];

}

void sort(int *num,int *a,int l,int r)

{

if(l==r)a[l]=num[l];

else

{

int t[100001];

int m=(l+r)>>1;

sort(num,t,l,m);

sort(num,t,m+1,r);

merge(t,a,l,r);

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)scanf("%d",&num[i]);

sort(num,num,1,n);

for(int i=1;i<=n;i++)printf("%d ",num[i]);

return 0;

}

« 「CF400B」Inna and New Matrix of Candies 「CF401A」Vanya and Cards »

hzwer.com _ Home | http://hzwer.com

归并排序

分类目录

热门文章

Myfriends

近期评论