分治算法
一、基本概念
分治法就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题…直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
分治法的基本步骤
分治法在每一层递归上都有三个步骤
分解：将原问题分解为若干个规模较小，相互独立，玉原问题形式相同的子问题
解决：若子问题规模较小容易被解决则直接解，否则递归地解各个子问题
合并：将各个子问题合并为原问题的解。
归并排序
归并排序时间复杂度O（n)
#includeusing namespace std;const int N = 1e4+10;int is1[N],is2[N];//归并 void merge(int low,int mid,int high){int i = low,j = mid + 1,k = low;while(i <= mid && j <= high){if(is1[i] < is1[j]){is2[k++] = is1[i++];}else{is2[k++] = is1[j++];}} while(i <= mid){is2[k++] = is1[i++];}while(j <= high){is2[k++] = is1[j++];}for(int i = low;i <= high; i++){is1[i] = is2[i];}}void mergesort(int a,int b){if(a >= b) return;int mid = (a + b)/2;mergesort(a,mid);mergesort(mid + 1,b);merge(a,mid,b);}int main(){int n;cin >> n;for(int i = 1; i <= n; i++){cin >> is1[i];}mergesort(1,n);for(int i = 1; i <= n; i++){cout << is1[i] <<" ";}}
C++自带归并函数
merge(first1,last1,first2,last2,result,compare);有序的序列。