蓝桥杯第七讲--排序【例/习题】

简介: 蓝桥杯第七讲--排序【例/习题】

前言

蓝桥杯官网:蓝桥杯大赛——全国大学生TMT行业赛事

✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识,此博客为第七讲:排序【例/习题】

本博客是讲排序这一专题,在蓝桥杯中,我们常用的就是快排和归并排序,而对于快排而言,我们一般习惯调用sort函数,读者可以看博文:STL—algorithm(2),如果你是用的 C语言,那么对于快排而言可以手写快排,见博文:快速排序


💖有关快速排序模板见博文:快速排序算法模板

💖有关归并排序模板见博文:归并排序算法模板


本篇博客所包含习题有:

👊归并排序

👊逆序对的数量


博客内容以题代讲,通过讲解题目的做法来帮助读者快速理解算法内容,需要注意:学习算法不能光过脑,更要实践,请读者务必自己敲写一遍本博客相关代码!!!


归并排序

题目要求

题目描述:

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

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

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

输入格式:

image.png

输出格式:

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

数据范围:

1≤n≤100000

输入样例:

5

3 1 2 4 5

输出样例:

1 2 3 4 5

思路分析

image.png

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int a[N], backup[N];
void merge_sort(int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] < a[j]) backup[k ++ ] = a[i ++ ];
        else backup[k ++ ] = a[j ++ ];
    }
    while (i <= mid) backup[k ++ ] = a[i ++ ];
    while (j <= r) backup[k ++ ] = a[j ++ ];
    for (int i = l, j = 0; i <= r; i ++, j ++ ) 
        a[i] = backup[j];
}
int main()
{
    int n;
    scanf("%d", &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;
}

逆序对的数量

题目要求

题目描述:

image.png

输入格式:

image.png

输出格式:

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

数据范围:

image.png

输入样例:

6

2 3 4 5 6 1

输出样例:

5

思路分析

我们在上一题的模板基础上让归并排序具有一些特殊含义,比如我们的归并排序可以返回其中逆序对的个数,我们把一个大区间分成了两个子区间,然后现在,我们的逆序对就会分为如下三种情况:

  1. 左子区间上的两个数构成逆序对
  2. 右子区间上的两个数构成逆序对
  3. 左字区间的一个数和右子区间的一个数构成逆序对


对于 1  和 2 而言,因为我们现在给归并排序赋予了返回区间上逆序对的个数这个含义,所以,处理 1 , 2 如下代码可解决:

res = merge_sort(l, mid) + merge_sort(mid + 1, r);

image.png

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int a[N], backup[N];
LL res;
LL merge_sort(int l, int r)
{
    if (l >= r) return 0;
    int mid = l + r >> 1;
    res = (LL)merge_sort(l, mid) + merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j]) backup[k ++ ] = a[i ++ ];
        else   //因为j肯定是大于i的,所以证明此时是一个逆序对
        {
            backup[k ++ ] = a[j ++ ];
            res += mid - i + 1;
        }
    }
    while (i <= mid) backup[k ++ ] = a[i ++ ];
    while (j <= r) backup[k ++ ] = a[j ++ ];
    for (int i = l, j = 0; i <= r; i ++, j ++ )
        a[i] = backup[j];
    return res;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) 
        scanf("%d", &a[i]);
    printf("%lld\n", merge_sort(1, n));
    return 0;
}


目录
相关文章
|
移动开发 算法 机器人
[蓝桥杯] 二分与前缀和习题练习
又来更新了。二分与前缀和是蓝桥杯比较常考的内容,所以我们要多加练习这方面的习题。二分与前缀和的难度相对来说不算大,我们应该掌握其关键要点。
136 0
|
机器学习/深度学习 算法 搜索推荐
蓝桥杯丨高级排序
蓝桥杯丨高级排序
79 0
|
算法 搜索推荐
蓝桥杯丨简单排序
蓝桥杯丨简单排序
102 0
|
5月前
|
算法
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
|
5月前
|
人工智能 算法
蓝桥杯真题宝藏排序详解 | 冒泡排序 选择排序 插入排序
蓝桥杯真题宝藏排序详解 | 冒泡排序 选择排序 插入排序
|
9月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
10月前
蓝桥杯真题代码记录(数位排序
蓝桥杯真题代码记录(数位排序
72 0
|
10月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-493 合并排序数组
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-493 合并排序数组
58 0
|
10月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-97 排序
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-97 排序
39 0
|
10月前
|
算法 Java
②【Java 组】蓝桥杯省赛真题解析 [振兴中华] [三部排序] 持续更新中...
②【Java 组】蓝桥杯省赛真题解析 [振兴中华] [三部排序] 持续更新中...
70 0