广东华业建设有限公司网站/怎样把个人介绍放到百度

基本思想：

归并排序（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.icourse163.org/learn/PKU-1001894005?tid=1002160011#/learn/content?type=detail&id=1002874892&cid=1003295301&replay=true

归并部分详解：

代码：

#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;
}