标签：分治

写在前面 这次是两种大家十分熟悉也是常见的东西，在中间的代码力玩花样的题并非没有，总而言之这是两种十分神奇的算法了qwq

归并排序

时间复杂度: O(n log(n)) 空间复杂度: O(n) 突然间想起几篇前的O(n^2)….真是感人 然后再看看前面的代码长度，在看看下面的… 也是很感人呢2333 我还不如等量子计算机出来直接冒泡

#include <cstdio>
using namespace std;
int n;
int result[110000];
int a[110000];
void marge(int *data,int start,int end,int *result){// 合并区间
    int left_start,result_start,right_start;
    left_start=result_start=start;
    right_start=(start+end+1)/2+1;
    while(left_start<=(start+end+1)/2&&right_start<=end){
        if(data[left_start]<data[right_start]) result[result_start++]=data[left_start++];
        else result[result_start++]=data[right_start++];
    }
    while(left_start<=(start+end+1)/2) result[result_start++]=data[left_start++];
    while(right_start<=end) result[result_start++]=data[right_start++];
}
void margesort(int *data,int start,int end,int *result){// 二分
    if(end-start==1){// 刚好差为1，那么这两个相邻，就可以排序
        if(data[start]>data[end]){
            int temp=data[end];
            data[end]=data[start];
            data[start]=temp;
        }
        return ;
    }
    else if(end-start==0) return ;//相同你排个瓜皮啊
    else {
        margesort(data,start,(start+end+1)/2,result);//继续二分排序
        margesort(data,(start+end+1)/2+1,end,result);
        marge(data,start,end,result);// 合并
        for(int i=start;i<=end;i++) data[i]=result[i];//排序完的总的回去吧233
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    margesort(a,1,n,result);
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}

我给你讲这个代码还是压过行的 上面的注释我觉得知道原理估计看不懂，说一下归并排序的原理:

1. 将一个长度为n的数列分成2/n的数列<分>
2. 分到只剩两个的时候排序<治>
3. 将每个区间进行合并<和>

所以这是一个分治算法，“分而治之”，“分完要和”。 建议思考两个问题 并不会公布答案，因为不自己想的话根本理解不了 如果你是dalao建议你左上角，这是一篇对你没有用的文章:

• 在二分排序的时候(start+end+1)/2与(start+end+1)/2+1是为了什么,可不可以替换？
• 中间几个<=是否可以换成<

快速排序

理论最优速度: O(n log(n)) 最差速度: O(n^2) 空间复杂度: O(n log(n)) 我们找出一个“哨兵”，然后找出比他大的和比他小的，然后分成两列<分>，知道最后只剩两个完成排序<治>，然后回溯输出<合> 又是一个分治算法 代码:

#include <cstdio>
using namespace std;
int n;
int a[110000];
void qsort(int *data,int s,int e){
    int o_l=s,o_r=e;
    int base=data[(s+e)/2];//取中快排
    do{
        while(data[s]<base) s++;// 比自己大的
        while(data[e]>base) e--;//比自己小的
        if(s<=e){//上面两个循环都被打断说明顺序不对，交换一下
            int temp=data[s];
            data[s]=data[e];
            data[e]=temp;
            s++;
            e--;
        }
    }while(s<=e);
    if(o_l<e) qsort(data,o_l,e);//确保不越界
    if(s<o_r) qsort(data,s,o_r);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    qsort(a,1,n);
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}

End

这两种算法是比较常见的排序算法，原理都是分治，不过归并相对稳定一些，不容易翻车 ]]>