AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
  • 吐槽
  • 登录/注册

AcWing 787. 归并排序    原题链接    简单

作者: 作者的头像   米多奇香米饼 ,  2023-01-25 10:35:15 ,  所有人可见 ,  阅读 15


0


# include<iostream>
using namespace std;

const int N = 1e5 + 5;
int q[N], t[N];
void merge_Sort(int p[],int l,int r){
    if(l >= r)return;
    int mid = (l+r)>>1;

    merge_Sort(p,l,mid);
    merge_Sort(p,mid+1,r);

    //count记录在数组t中元素的个数
    int count = 0,i = l,j = mid+1;
    while(i <= mid && j <= r){
        //如果第一段的元素小于第二段的元素,那么将第一段的元素赋值到临时数组t中,并将count++,i++
        if(q[i]<=q[j])t[count++] = q[i++];
        //如果第二段的元素小于第一段的元素,那么将第二段的元素赋值到临时数组t中,并将count++,j++
        else t[count++] = q[j++];
    }
    while(i <= mid)t[count++] = q[i++];
    while(j <= r)t[count++] = q[j++];
    //将临时数组t中的元素依次赋值到原数组q中
    for ( int i = l, j = 0; i <= r; i++, j++ ) q[i] = t[j];
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n;i++)scanf("%d",&q[i]);
    merge_Sort(q,0,n-1);
    for(int i = 0;i < n;i++)printf("%d ",q[i]);

    return 0;
}

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息