考研算法31天：归并排序【归并排序，分治】

这篇具有很好参考价值的文章主要介绍了考研算法31天：归并排序【归并排序，分治】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

算法介绍

归并算法其过程分为三步：

1.分：递归到最下面

2.治：两个元素之间排序。

3。归：递归到最下层然后返回，从两个元素变成四个元素再排序。

如下图所示：

考研算法31天：归并排序【归并排序，分治】

动态图如下：

考研算法31天：归并排序【归并排序，分治】

算法题目

考研算法31天：归并排序【归并排序，分治】

算法ac代码:文章来源地址https://www.toymoban.com/news/detail-505468.html

#include <iostream>

using namespace std;

const int N = 1000010;
int q[N], w[N];

void merge_sort(int left,int right){
    //向下递归
    if(left>=right) return;
    int mid = (left + right)>>1;
    merge_sort(left,mid),merge_sort(mid+1,right);
//分到只有两个的的时候开始递回
    int l = left, r = mid+1;
    int i=0,j;
//将排序好的数组片段先放到其他数组中去
    while(l<=mid&&r<=right){
        // cout<<"q[l]:"<<q[l]<<"q[r]:"<<q[r]<<endl;
        if(q[l]<q[r]) w[i++] = q[l++];
        else w[i++] = q[r++];
        
    }
//如果左边或者是右边没有全部放入证明是最大的几个数，依次放入即可
    while(l<=mid) w[i++] = q[l++];
    while(r<=right) w[i++] = q[r++];
//将排序好的数组片段放回原先的数组中去，片段数组排序结束
    for(i=0,j=left;j<=right;i++){
        q[j++] = w[i];
    }
    return;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    merge_sort(0,n-1);
    for(int i=0;i<n;i++)printf("%d ",q[i]);
    return 0;
}

到了这里，关于考研算法31天：归并排序【归并排序，分治】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！