归并排序详解 和逆序数计算
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。（摘自baidu）
归并排序的核心思想是将两个已经排序的序列合并成一个序列，那如何得到两个已经排序的序列呢？我们知道， 如果一个序列只有一个元素，那该序列是已经排序的，这样我们就可以利用分治的思想，将未排序的序列划分成更小的序列，只到我们可以很方便的对小序列进行排序（比如划分到序列只有一个元素， 或者序列很小可以方便的使用其它排序算法进行排序），然后再将小序列逐次合并，得到最后的排序结果。（csdn）
归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。（白话经典算法）
第一步是递归实现数组的不断分割知道只有一个元素；
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；
成对成对的合并
一直到原来的数组大小，长度是非偶数时，假设为3，会被分成一个长度为1的和一个长度为2的数组；
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;//这是求比较次数
}本代码顺便把常见的两种问题，求逆序数和比较次数给带入了，可以看看。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-06-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
