归并排序算法

算法排序介绍

归并排序算法采用分治的策略，先将问题划分为若干部分然后递归求解，治就是将分的各部分答案和在一起，即分而治之。

算法原理

归并排序分为划分，排序，合并三个步骤，划分时我们取一个中点将待排序序列分为左右两部分，然后排序左右两边，然后合并左右两边，过程递归进行，递归深度为longn。

算法实现

#include<iostream>
using namespace std;
const int N=1e5+5;
int arr[N];
int tmp[N];
void merge_sort(int q[],int l,int r){
	if(l>=r) return;
	int mid=l+r>>1;
	merge_sort(q,l,mid);
	merge_sort(q,mid+1,r);
	int i=l,j=mid+1,k=0;
	while(i<=mid&&j<=r){
		if(arr[i]>arr[j]) tmp[k++]=arr[j++];
		else tmp[k++]=arr[i++];
	}
	while(i<=mid) tmp[k++]=arr[i++];
	while(j<=r) tmp[k++]=arr[j++];
	for(int i=l,j=0;i<=r;i++,j++) arr[i]=tmp[j];
} 
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];
	merge_sort(arr,0,n-1);
	for(int i=0;i<n;i++) cout<<arr[i]<<" ";
	return 0; 
}

算法特点与复杂度分析

归并排序是稳定的排序算法，他不会改变相同元素的相对位置。
归并排序非常高效，能利用完全二叉树特性的排序性能一般不会太差。java中Array.sort()采用了一种名为TimSot的排序算法，就是归并排序算法的优化版本。
合并操作的时间复杂度为O(n)，而完全二叉树的深度为logn,总的时间复杂度为O(nlogn）,归并排序的最好和最坏平均时间复杂度均为O(nlongn)。

归并排序算法

原文：https://www.cnblogs.com/zzjjblogs/p/14618815.html