归并排序+例题

归并排序+例题

归并排序（Merge-Sort）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

以下图片转载自：简书 图解归并排序

一、图示过程

1、归并排序的过程

2、合并两个有序数组的过程

3、动图展示

二、C++代码实现

#include
using namespace std;
int n,a[500005],temp[500005]; void merge(int s[],int start,int end,int mid)
{int i = start;int j = mid+1;int k = start;// 找出较小值元素依次放入temp数组中while(i<=mid && j<=end){if(s[i]<s[j])temp[k++] = s[i++];elsetemp[k++] = s[j++];}// 处理较长部分,剩下的都是比前已经合并的数更大的数 while(i<=mid)temp[k++] = s[i++]; 	while(j<=end)temp[k++] = s[j++];//将合并好的数组赋值到原数组a[]中for(int p=start;p<=end;p++)a[p]=temp[p];  	
}
void mergesort(int s[],int start,int end)
{if(start<end){int mid=(start+end)>>1;//右移相当于除以2 mergesort(s,start,mid);mergesort(s,mid+1,end);merge(s,start,end,mid);}
}
//主函数
int main()
{scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);mergesort(a,0,n-1);for(int i=0;i<n;i++)cout<<a[i]<<" "; return 0;
}

三、复杂度

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)，归并需要一个与原数组相同长度的数组做辅助来排序
• 稳定性：稳定

四、例题

洛谷：P1908逆序对

这道题起初我直接暴搜，后面几个测试点全部超时，然后经过题解的提示才发现，归并排序才是正道。

#include
using namespace std;
int n,a[500005],temp[500005]; 
long long ans;
void merge(int s[],int start,int end,int mid)
{int i = start;int j = mid+1;int k = start;while(i<=mid && j<=end){if(s[i]<=s[j]){temp[k++] = s[i++];}	else{temp[k++] = s[j++];ans=ans+mid-i+1; //每次只加后面合并进来的数}		}while(i<=mid){temp[k++] = s[i++];}    	while(j<=end){temp[k++] = s[j++];}for(int p=start;p<=end;p++)a[p]=temp[p];  	
}
void mergesort(int s[],int start,int end)
{if(start<end){int mid=(start+end)>>1;//右移除以2 mergesort(s,start,mid);mergesort(s,mid+1,end);merge(s,start,end,mid);}
}
int main()
{scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);mergesort(a,0,n-1);cout<<ans ;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！