归并排序（分治）

曾经终败给现在 2022-06-10 14:19 237阅读 0赞

**基本思想：**

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

参考网址：[http://www.cnblogs.com/chengxiao/p/6194356.html][http_www.cnblogs.com_chengxiao_p_6194356.html]

视频地址：[http://www.icourse163.org/learn/PKU-1001894005?tid=1002160011\#/learn/content?type=detail&id=1002874892&cid=1003295301&replay=true][http_www.icourse163.org_learn_PKU-1001894005_tid_1002160011_learn_content_type_detail_id_1002874892_cid_1003295301_replay_true]

![20170821180902055][]

![20170821180718020][]

![20170821181107783][]

**归并部分详解：**

![20170821181410535][]

**代码：**

#include<iostream>
    using namespace std;
    void Merge(int a[],int s,int m,int e,int tmp[])//治 
    //将数组a的局部a[s,m]和a[m+1,e]合并到tmp,并保证tmp有序，然后再拷贝回a[s,e]
    //归并操作的时间复杂度：O(e-m+1),即O(n) 
    {
    	int pb=0;
    	int p1=s,p2=m+1;
    	while(p1<=m&&p2<=e)
    	{
    		if(a[p1]<a[p2]) tmp[pb++]=a[p1++];
    		else tmp[pb++]=a[p2++]; 
    	}
    	while(p1<=m) tmp[pb++]=a[p1++];//p1还未指向末尾 
    	while(p2<=e) tmp[pb++]=a[p2++];
    	for(int i=0;i<e-s+1;i++) a[s+i]=tmp[i];
    } 
    void MergeSort(int a[],int s,int e,int tmp[]) //分。tmp[]做中转，对a数组s-e区间归并排序 
    {
    	if(s<e)
    	{
    		int m=s+(e-s)/2;//中点 
    		MergeSort(a,s,m,tmp);//前一半归并排序
    		MergeSort(a,m+1,e,tmp);//后一半归并排序
    		Merge(a,s,m,e,tmp);//将a[]中将s-m,m+e-e归并起来 
    	}
    } 
    int a[10]={13,27,19,2,8,12,2,8,30,89};
    int b[10];
    int main()
    {
    	int size=sizeof(a)/sizeof(int);
    	MergeSort(a,0,size-1,b);//0和size-1表示待排序数组的起始和终点下标，b表示中间数组 
    	for(int i=0;i<size;i++) cout<<a[i]<<" ";
    	cout<<endl;
    	return 0;
    }

![20170821181526833][]

[http_www.cnblogs.com_chengxiao_p_6194356.html]: http://www.cnblogs.com/chengxiao/p/6194356.html
[http_www.icourse163.org_learn_PKU-1001894005_tid_1002160011_learn_content_type_detail_id_1002874892_cid_1003295301_replay_true]: http://www.icourse163.org/learn/PKU-1001894005?tid=1002160011#/learn/content?type=detail&id=1002874892&cid=1003295301&replay=true
[20170821180902055]: /images/20220610/66d74cbf70e740caae31884194c2d188.png
[20170821180718020]: /images/20220610/a9100857ff164b23a483ba08c5721beb.png
[20170821181107783]: /images/20220610/8ea68c54a43a4978871ed604dc2049c6.png
[20170821181410535]: /images/20220610/f23189b495c04716920195f37f01c485.png
[20170821181526833]: /images/20220610/a8f0b9f1d3b849ffa90bbcb69ed04a1c.png