题目描述

1.确定分界点
2.递归处理左右两边的子问题
3.合体
本质思想是分治
分治：逐个击破，分而治之。类比于分封制。将一个问题分解为n个相互独立的子问题，通过逐个解决小问题，从而解决整个问题
blablabla

样例

#include<iostream>
using namespace std;
const int N=100010;
int q[N];
int temp[N];//临时变量用于存放结果
void merge_sort(int q[],int l,int r){
    if(l>=r) return;//相似的子问题得到解决
    int mid=(l+r)/2;//利用mid将q,分解成左右两边
    int i=l;
    int j=mid+1;
    int k=0;//计数器
    merge_sort(q,l,mid),
    merge_sort(q,mid+1,r);//递归处理
    while(i<=mid&&j<=r)//循环成立的条件
    if(q[i]>=q[j])temp[k++]=q[j++];
    else 
        temp[k++]=q[i++];
    while (i <= mid) temp[k ++ ] = q[i ++ ];//处理完结果之后，如果左边元素，有剩余则加入到数组中
    while (j <= r) temp[k ++ ] = q[j ++ ];//如果右边元素有剩余，则加入到数组中去
    for(int i=l,j=0;i<=r;i++,j++) q[i]=temp[j];//物归原主
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i;i<n;i++) scanf("%d",&q[i]);
    merge_sort(q,0,n-1);
    for(int i=0;i<n;i++) printf("%d ",q[i]);
}


blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla