归并

归并算法

• 归并
• 归并排序的优点
• 归并排序的实现
• 归并排序的应用

假设现在的列表分两段有序，如何将其合成为一个有序列表。这种操作称为一次归并。

一般我们排序用到的，一般是冒泡 选择 插入等基础排序，有些时候追求运行时间时，可能会使用快排，但快排又是一个不稳定的排序，这时就有了归并排序，归并排序不仅稳定，速度也很快，但它是在拿空间来换时间，比一般排序的空间大了一倍。

先把一个无序的列表一直分，分成多个只有一个成员的列表，这时一个列表肯定是有序的，接下来就一个一个合并，最后就排好序了。

以下是代码实现

#include"stdio.h"
#include"string.h"
long long sum;
int gs;
long long a[101000],b[101000];//a是存放结果 b是存放暂时结果
int Merge(long long r[],long long r1[],int s,int m,int t)
{
int i=s;
int j=m+1;
int k=s;
while(i<=m&&j<=t)//规定它的范围
{
if(r[i]<=r[j])
{
r1[k++]=r[i++];
}
else
{
r1[k++]=r[j++];
}

}
while(i<=m)//如果有个列表的成员有多就把剩下的全部放进去
r1[k++]=r[i++];
while(j<=t)//同理
r1[k++]=r[j++];
for(int l=s; l r[l]=r1[l];
}

void MergeSort(long long r[],long long r1[],int s,int t)
{
if(s==t) //只有一个成员时停止
return;
else
{
int m=(s+t)/2;
MergeSort(r,r1,s,m);
MergeSort(r,r1,m+1,t);//一直调用自己 一直分
Merge(r,r1,s,m,t);
}
}
main()
{
int n,i;
while(scanf("%d",&n)!=EOF)
{
while(n--)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
while(scanf("%d",&gs)!=EOF)
{
int qw;
for(qw=0;qw scanf("%lld",a+qw);
MergeSort(a,b,0,gs-1);
for(i=0;i printf("%d ",a[i]) ;
printf("\n");
}
}

}
}

归并排序的应用

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。

比如 1 3 2 的逆序数就是1。

代码实现

#include"stdio.h"
#include"string.h"
long long sum;
int gs;
long long a[101000],b[101000];
int Merge(long long r[],long long r1[],int s,int m,int t)
{
int i=s;
int j=m+1;
int k=s;
while(i<=m&&j<=t)
{
if(r[i]<=r[j])
{
r1[k++]=r[i++];
}
else
{
r1[k++]=r[j++];
sum+=m-i+1;
}

}
while(i<=m)
r1[k++]=r[i++];
while(j<=t)
r1[k++]=r[j++];
for(int l=s; l r[l]=r1[l];
}

void MergeSort(long long r[],long long r1[],int s,int t)
{
if(s==t)
return;
else
{
int m=(s+t)/2;
MergeSort(r,r1,s,m);
MergeSort(r,r1,m+1,t);
Merge(r,r1,s,m,t);
}
}
main()
{
int n,i;
while(scanf("%d",&n)!=EOF)
{
while(n--)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
while(scanf("%d",&gs)!=EOF)
{
sum=0;
int qw;
for(qw=0;qw scanf("%lld",a+qw);
MergeSort(a,b,0,gs-1);
printf("%lld\n",sum);
}
}

}
}


• 
  
  点赞
  


• 
  
  收藏


• 
  
  分享


• 
  

  
  

  
  
  • 文章举报