【归并排序】归并排序/逆序对的数量

简介: 【归并排序】归并排序/逆序对的数量

目录

算法思想

例题

题目:acwing.787. 归并排序

题目:acwing.787.


image.gif


算法思想

归并排序———分治(合二为一)

1.确定分界点(mid=(l+r)/2)

image.gif

2.递归排序左边和右边

image.gif

3.归并将左边和右边合二为一

image.gif


例题

题目:acwing.787. 归并排序

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行,第一行包含整数 n。

第二行包含 n个整数(所有整数均在 1∼1091∼109 范围内),表示整个数列。

输出格式

输出共一行,包含 n个整数,表示排好序的数列。

数据范围

1≤n≤100000

输入样例:

5
3 1 2 4 5
image.gif

输出样例:

1 2 3 4 5
image.gif

原题链接 :AcWing 787. 归并排序

#include<iostream>
using namespace std;
const int N = 1e6 + 10;//数据范围1≤n≤100000
int n;
int q[N], tmp[N];//tmp临时数组
void merge_sort(int q[], int l, int r)
{
  if (l >= r)
    return;
  int mid = l + r >> 1;//确定分界点(mid=(l+r)/2)
  merge_sort(q, l, mid);//递归排序左边
  merge_sort(q, mid + 1, r);//递归排序右边
  /*归并*/
  int k = 0, i = l, j = mid + 1;//i指向左边的起点,j指向右边的起点
  while (i <= mid && j <= r)
    if (q[i] <= q[j])   //左右比大小,小的存在临时数组中
      tmp[k++] = q[i++];
    else 
      tmp[k++] = q[j++];
  while(i<=mid) tmp[k++] = q[i++];
  while(j<=r)   tmp[k++] = q[j++];
  for (i = l, j = 0; i <= r; i++, j++)//将临时数组赋回有序数组
    q[i] = tmp[j];
}
int main()
{
   scanf("%d", &n);//输入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;
}

image.gif

题目:acwing.787.逆序对的数量

给定一个长度为 n 的整数数列,请你计算数列中的逆序对的数量逆序对的定义如下: 对于数列的第i个和第 j个元素,如果满足i< i且a [i]>a[j],则其为一个逆序对;否则不是。

输入格式

第一行包含整数n,表示数列的长度

第二行包含n 个整数,表示整个数列。

输出格式

输出一个整数,表示逆序对的个数。

数据范围

1 < n < 100000

数列中的元素的取值范围[1,10^9]

输入样例:

6
2 3 4 5 6 1
image.gif

输出样例:

5
image.gif

原题链接 :AcWing 788. 逆序对的数量

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6+10;//1 < n < 100000
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r)
{
    if (l >= r) return 0;
    int mid = (l + r) >> 1; // 确定分界点
    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    /*归并*/
    int k = 0,i = l, j = mid + 1 ;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) tmp[k++] = q[i++]; 
        else
        {
            res += mid - i + 1;
            tmp[k++] = q[j++];
        }
    }
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    return res;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    LL res = merge_sort(a, 0, n - 1);
    cout << res << endl;
    return 0;
}

image.gif


image.gif

好了,本篇学习笔记就到此为止了,如有问题欢迎指正,感谢各位佬的支持!

相关文章
|
存储 SQL 分布式计算
《离线和实时大数据开发实战》(三)Hadoop原理实战
《离线和实时大数据开发实战》(三)Hadoop原理实战
715 0
《离线和实时大数据开发实战》(三)Hadoop原理实战
|
12月前
|
存储 移动开发 网络协议
【实战指南】从零构建嵌入式远程Shell,提升跨地域协作效率(2)
本文《从零构建嵌入式远程Shell》的第二部分,介绍了如何通过模块化设计和功能增强来优化远程Shell,包括支持阻塞命令、增加用户主动结束Shell进程的能力等,提升了跨地域协作效率。文中提供了详细的代码示例和验证步骤,适合开发者深入学习。
133 88
|
10月前
|
敏捷开发 人工智能 监控
可视化工具在B端需求管理中的应用与优势
在快速变化的商业环境中,B端企业需精准把握客户需求,构建高效的需求管理体系。本文探讨了需求管理的核心要素与策略,包括需求收集、分析、规划、跟踪与反馈,以及优化流程与团队协作的方法。推荐使用板栗看板等工具,提升需求管理的智能化和可视化水平,助力企业在竞争中脱颖而出。
|
10月前
|
弹性计算 Serverless 数据安全/隐私保护
针对【图像生成 - ComfyUI】使用的深度评测
ComfyUI 是一款支持自定义工作流的图像生成工具,适用于创意设计、游戏开发和电商等多个行业。它能根据项目需求灵活调整图像生成流程,提高创意实现效率,同时具备成本效益和弹性伸缩能力,适应业务量变化。尽管如此,ComfyUI 在技术门槛和数据安全方面仍存在挑战,需注意非专业用户的学习曲线和敏感数据保护。
|
11月前
|
移动开发 小程序 开发工具
Demo发布- ClkLog客户端集成 uni-app
在上一期推文中,我们与大家分享了 React Native 的集成 demo。本期,我们将继续介绍 ClkLog 集成 uni-app 的 demo。 uni-app 允许开发者编写一套代码,然后可以编译到 iOS、Android、H5 以及各种小程序等多个平台。因此,本次 demo 中将涵盖上述所有平台,并且我们会详细说明集成过程中遇到的难点及解决方案。
|
存储 编解码
【头歌·计组·自己动手画CPU】一、计算机数据表示(讲解版) 【计算机硬件系统设计】
【头歌·计组·自己动手画CPU】一、计算机数据表示(讲解版) 【计算机硬件系统设计】
500 1
|
并行计算 Java API
Java8实战-CompletableFuture:组合式异步编程
Java8实战-CompletableFuture:组合式异步编程
191 0
|
Java
【Java开发指南 | 第二十七篇】Java抽象类
【Java开发指南 | 第二十七篇】Java抽象类
103 0
|
Java 数据库连接 mybatis
Mybatis源码细节探究:sqlSessionFactory.openSession()这个方法到底发生了什么?
Mybatis源码细节探究:sqlSessionFactory.openSession()这个方法到底发生了什么?
|
项目管理
PMP备考之路 - 视频教程第四讲(范围管理)(一)
PMP备考之路 - 视频教程第四讲(范围管理)
80 0