您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

AcWing 787. 归并排序

AcWing 787. 归并排序

  • 一、题目链接
  • 二、题目分析
    • (一)算法标签
    • (二)解题思路
  • 三、AC代码
  • 四、其它题解


一、题目链接

AcWing 787. 归并排序


二、题目分析

(一)算法标签

归并排序

(二)解题思路


三、AC代码

解法一:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int a[N];
int tmp[N];

void merge_sort(int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    
    int i = l, j = mid + 1, k = 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j])
            tmp[k ++ ] = a[i ++ ];
        else
            tmp[k ++ ] = a[j ++ ];
    }
    while (i <= mid) tmp[k ++ ] = a[i ++ ];
    while (j <= r) tmp[k ++ ] = a[j ++ ];
    for (int i = l, k = 1; i <= r; i ++, k ++ ) a[i] = tmp[k];
}
int main()
{
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
    merge_sort(1, n);
    
    for (int i = 1; i <= n; i ++ ) printf("%d ", a[i]);
    return 0;
}

四、其它题解

AcWing 787. 归并排序 1
AcWing 787. 归并排序 2


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进