# 归并排序详解 和逆序数计算

```void mergesort(int a[], int first, int last)
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid);    //左边有序
mergesort(a, mid+1, last); //右边有序
merge(a, first, mid, last); //再将二个有序数列合并
}
}```

要注意的是mid+1这个细节

1+1=2

2+2=4；

```void merge(int a[], int first, int mid, int last)
{
int i = first, j = mid + 1;
int m = mid,   n = last;
int k = 0;
int temp[maxn];
while (i <= m && j <= n)
{
ope_num++;
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}

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

while (j <= n)
temp[k++] = a[j++];

for (i = 0; i < k; i++)
a[first + i] = temp[i];
}```

要注意把剩下的的归并进去；

```#include <bits/stdc++.h>
using namespace std;
#define maxn 200000
int n;
int ope_num=0;
int wosort_num=0;
void merge(int a[], int first, int mid, int last)
{
int i = first, j = mid + 1;
int m = mid,   n = last;
int k = 0;
int l=mid-first;
int temp[maxn];
while (i <= m && j <= n)
{
ope_num++;
if (a[i] <= a[j])
temp[k++] = a[i++];
else
{
temp[k++] = a[j++];
wosort_num+=(l-i+first);
}

}

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

while (j <= n)
temp[k++] = a[j++];

for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last)
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid);    //左边有序
mergesort(a, mid+1, last); //右边有序
merge(a, first, mid, last); //再将二个有序数列合并
}
}
int main()
{
int a[maxn];
memset(a,0,sizeof(a));
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n);
for(int i=1;i<=n;i++)
{
if(i-1) cout<<" ";
cout<<a[i];
}
cout<<endl;
cout<<wosort_num<<endl;//这是求逆序数
cout<<ope_num<<endl;//这是求比较次数
}```

本代码顺便把常见的两种问题，求逆序数和比较次数给带入了，可以看看。

60 篇文章38 人订阅

0 条评论

## 相关文章

50230

362150

### 13（01）总结StringBuffer,StringBuilder,数组高级，Arrays，Integer，Character

1:StringBuffer(掌握) (1)用字符串做拼接，比较耗时并且也耗内存，而这种拼接操作又是比较常见的，为了解决这个问题，Java就提供了 一...

43450

31270

24270

8920

242100

22380

61910