蓝桥杯 归并排序 acwing版

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

上次题目答案

先公布一下上次内容的留的题目的答案吧,我相信看了并练习之后的人那个题目不成问题。

题目在上讲里面有,这里不再放出来了。

#include<iostream>
using namespace std;
bool check(int i){
	for(int a = 1;a<=i;a++){
			for(int b = 0;b < a;b++){
				if(a*a-b*b==i){
					return true;
				}
			}
	}
	return false;
}
int main(){
	int ans = 0;
	for(int i = 1;i <= 2021;i++){
		if(check(i)){
			ans++;
		}
	}
	cout << ans;
	return 0;
}

答案:1516
分析
n = a*a-b*b

b的范围是(0,a)

a的范围是[1,n],为什么a至多能取到n呢?

        以n=9为例:假设a=9,为了让a*a-b*b=9,就算b取最大值8,9*9-8*8仍然远大于9,所以a永远不会超过n(1例外)

下面开始讲解归并排序内容了:

1.归并排序介绍:

简单来说,我们可以说合并排序的过程是将数组分成两半,对每一半进行排序,然后将排序后的两半合并在一起。重复此过程,直到对整个数组进行排序。

蓝桥杯 归并排序 acwing版,蓝桥杯,算法,职场和发展

2.动画展示过程

可以看出来现在不是跟之前一样一味的代数法了。其实代数法是为了能更好的理解函数递归的过程,除此之外无非就是验证程序的对错,所以还是希望大家能从本质上理解一个算法的思路,这样省时省力,我初学算法的时候就是一直不明白程序傻傻的老实想用代数法理解为什么这么写的,我现在的评价是大可不必,理解原理,模仿别人的写出代码,别跟自己过不去。不多bb了上内容。

合并排序是如何工作的?

合并排序是一种递归算法,它连续地将数组分成两半,直到无法进一步分割,即数组只剩下一个元素(具有一个元素的数组总是排序)。然后,将排序的子数组合并为一个排序的数组。

请参阅下图以了解合并排序的工作原理。

插图:

让我们考虑一个数组 arr[] = {38, 27, 43, 10}

  • 最初将数组分成相等的两半:

蓝桥杯 归并排序 acwing版,蓝桥杯,算法,职场和发展

合并排序:将数组分成两半

  • 这些子阵列进一步分为两半。现在,它们成为无法再分割的单位长度数组,并且单位长度数组始终被排序。

蓝桥杯 归并排序 acwing版,蓝桥杯,算法,职场和发展

合并排序:将子数组分成两半(此处为单位长度子数组)

这些排序的子数组合并在一起,我们得到更大的排序子数组。

蓝桥杯 归并排序 acwing版,蓝桥杯,算法,职场和发展

合并排序:将单位长度子数组合并到排序的子数组中

此合并过程将一直持续到从较小的子数组构建排序后的数组。

蓝桥杯 归并排序 acwing版,蓝桥杯,算法,职场和发展

合并排序:合并排序后的子数组,得到排序后的数组

3.算法模板

void merge_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;

    //第一步:分成子问题
    int mid = l + r >> 1;

    //第二步:递归处理子问题
    merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);

    //第三步:合并子问题
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    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(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}

4.讲解模板例题

讲算法模板

一个题目,这个题目也就是比模板多了传入数据的过程,也是便于大家更好的应用吧

题目:

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤100000

输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
#include<iostream>
using namespace std;
const int N = 1000010;
int n;// 数组元素个数
int q[N];//待排序的数组
int tmp[N];// 用来存放合并左右两边结果的数组
void merge_sort()
{
    // 当前区间只有一个数或者没有数
    if(l>=r) return ;
    // 确定分界点为数组中点
    int mid = l+r>>1;

    // 对左右两边进行递归排序
    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];
           k++;
           i++;
        }
        else
        {
            tmp[k]=q[j];
            k++;
            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);
    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;
}
  1. 确定分界点为中间位置,mid=(l+r)/2
  2. 递归排序左右两边
  3. 归并两个排好序的数组,合二为一(最难的部分),时间复杂度是O(n)
    双指针算法
    两个指针分别指向两个数组的开头,比较两个指针对应数值大小,小的放进新数组,该指针后移,直到一个指针到达数组末尾,将另外一个数组剩下的部分添加到新数组中。
    1 3 5 7 9
    2 4 5 8 10
    i=0,j=0;p[i]=p[0]=1<q[j]=q[1]=2,s[0]=p[0]=1;i++;i=1,j=0;
    i=1,j=0;p[i]=p[1]=3>q[j]=q[0]=2,s[1]=q[0]=2;j++;i=1,j=1;
    i=1,j=1;p[i]=p[1]=3<q[j]=q[1]=4,s[2]=p[1]=3;i++;i=2,j=1;
    i=2,j=1;p[i]=p[2]=5>q[j]=q[1]=4,s[3]=q[1]=4;j++;i=2,j=2;
    i=2,j=2;p[i]=p[2]=5<=q[j]=q[2]=5,s[4]=p[2]=5;i++;i=3,j=2;
    i=3,j=2;p[i]=p[3]=7>q[j]=q[2]=5,s[5]=q[2]=5;j++;i=3,j=3;
    i=3,j=3;p[i]=p[3]=7<q[j]=q[3]=8,s[6]=p[3]=7,i++;i=4,j=3;
    i=4,j=3;p[i]=p[4]=9>q[j]=q[3]=8,s[7]=q[3]=8,j++;i=4,j=4;
    i=4,j=4;p[i]=p[4]=10>q[j]=q[4]=9,s[8]=q[4]=9,j++;i=4,j=5
    s[9]=p[4]=10

原序列中两个值相同的数,排序后相对位置不发生变化。

5.习题

这里面我只找到了一个习题,给大家放出来吧,做练习,历年题没有,所以大家学习一下这个思想吧

题目描述:

给定一个长度为n的整数数列,请你计算数列中的逆序对的数量。

逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i] > a[j],则其为一个逆序对;否则不是。

输入格式

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

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

输出格式

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

数据范围

1≤n≤100000

输入样例:

6
2 3 4 5 6 1
输出样例:

5
 分析:

本题与AcWing 65 数组中的逆序对是同一题,再次写个题解以加深印象。

与归并排序类似,分而治之。

第一步:将原问题递归的划分为两个子问题L和R;

第二步:递归的求出子问题L和R中逆序对的个数;

第三步:合并子问题的解得到总问题的解。

唯一的问题在于子问题解的合并上,比如L上有x个逆序对,R上有y个逆序对,则LR上的逆序对并不是x与y简单的相加,还要加上两边的逆序对,比如L排好序后是1 3 5,R排好序后是2 4 6,L的排序消除了x个逆序对,R的排序消除了y个逆序对,此时原问题的状态变为1 3 5 2 4 6,可见还是有逆序对存在的,剩下的逆序对需要合并操作来消除。同样比较两个子问题指针指向元素的大小,1 < 2,1是最小的元素,不会存在逆序对,3 > 2,子问题L为1 3 5,既然3都大于2,则有序序列L 3右边的数也都必然大于2,所以L中大于2的数为L的右边界mid减去指向3的指针i加上1,即由2构成逆序对的数目。

本题代码只需在归并排序代码上稍作修改即可得到答案,总的代码如下:

代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100005;
typedef long long ll;
int a[maxn], temp[maxn],n;
ll merge_sort(int *a, int l, int r) {
	if (l >= r)		return 0;
	int mid = l + r >> 1;
	ll res = merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);
	int k = 0,i = l,j = mid + 1;
	while (i <= mid && j <= r) {
		if (a[i] <= a[j])	temp[k++] = a[i++];
		else
		{
			temp[k++] = a[j++];
			res += mid - i + 1;
		}
	}
	while (i <= mid)	temp[k++] = a[i++];
	while (j <= r)	temp[k++] = a[j++];
	for (i = l,j = 0; i <= r; i++,j++)	a[i] = temp[j];
	return res;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)    scanf("%d", &a[i]);
	printf("%lld\n", merge_sort(a, 0, n - 1));
	return 0;
}

6、浅谈时间复杂度、稳定性

O(nlogn)
归并排序是稳定的

如何看一个排序稳定不稳定?

一个排序算法是稳定的并不是说它的时间效率是稳定的。稳定是指如果原序列中的两个值相同的,经过排序之后,它们的位置没有发生变化,那么这个排序就是稳定的。它们的位置如果可能会发生变化,那么这个排序就是不稳定的。
 

蓝桥杯 归并排序 acwing版,蓝桥杯,算法,职场和发展

那么明天见!文章来源地址https://www.toymoban.com/news/detail-770045.html

到了这里,关于蓝桥杯 归并排序 acwing版的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【初阶算法4】——归并排序的详解,及其归并排序的扩展

    目录 前言 学习目标: 学习内容: 一、介绍归并排序 1.1 归并排序的思路 1.2 归并排序的代码 1.2.1 mergesort函数部分  1.2.2 process函数部分  1.2.3 merge函数部分  二、AC两道经典的OJ题目 题目一:逆序对问题 题目二:小和问题  三、练习一道LeetCode的题目 四、总结在什么情况下使

    2024年02月08日
    浏览(40)
  • 算法基础15 —— 分治算法(归并排序 + 快速排序)

    分治法的基本概念、思想 分治法是一种很重要的算法。 字面解释,分治分治,分而治之。就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 不难发现,分

    2024年02月03日
    浏览(53)
  • 排序算法:归并排序(非递归)

    先赞后看,养成习惯!!!^ _ ^3 ❤️ ❤️ ❤️ 码字不易,大家的支持就是我坚持下去的动力。点赞后不要忘了 关注 我哦! 所属专栏:排序算法 步骤如下: 1.先两两归并,两个为一组 2.然后根据每组的距离gap,分配组数进行排序 3.gap每次扩大2的倍数 4.注意一些细节:首先注

    2024年03月24日
    浏览(38)
  • 深度理解排序算法——归并排序

    ………………………………………………………………………………… 给定一段无序数组,将数组拆分成 两段 ,使得 左右两段 得数组均呈现有序状态,再借助 临时数组 将两段数组归并至一块呈现有序,最后 拷贝 回原数组即得到有序数组。 从逻辑上理解,就是一颗 二叉

    2024年02月03日
    浏览(37)
  • 排序算法之【归并排序】

    📙 作者简介:  清水加冰,目前大二在读,正在学习C/C++、Python、操作系统、数据库等。 📘 相关专栏: C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正! ✨每一次努力都

    2024年02月07日
    浏览(46)
  • 排序算法之归并排序

    归并排序,是创建在归并操作上的一种有效的排序算法。算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。归并排序思路简单,速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。 1. 基本思想

    2024年02月03日
    浏览(33)
  • 排序算法:归并排序

            约翰·冯·诺伊曼在 1945 年提出了归并排序。在讲解归并排序之前,我们先一起思考一个问题:如何将两个有序的列表合并成一个有序的列表?         这太简单了,笔者首先想到的思路就是,将两个列表拼接成一个列表,然后之前学的冒泡、选择、插入、希尔

    2024年02月11日
    浏览(37)
  • 归并排序--排序算法

    归并排序和快速排序一样,都是基于分治思想的应用。 通过递归,不断将原数列分为两个数列,然后再分别使其有序,最后通过归并将两个有序子数列合并为新的有序数列。 值得注意的是,与快速排序不同,归并排序是稳定的。 和快速排序先排序后递归不同,归并排序是先

    2024年02月06日
    浏览(38)
  • 排序算法二 归并排序和快速排序

    目录 归并排序 快速排序 1 挖坑法​编辑 2 Hoare法 快排的优化 快排的非递归方法 七大排序算法复杂度及稳定性分析 归并排序是建立在归并操作上的一种有效的排序算法,将以有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,在使子序列段间有序.若将两个有序的

    2024年02月07日
    浏览(40)
  • 【算法系列 | 4】深入解析排序算法之——归并排序

    你只管努力,其他交给时间,时间会证明一切。 文章标记颜色说明: 黄色 :重要标题 红色 :用来标记结论 绿色 :用来标记一级论点 蓝色 :用来标记二级论点 决定开一个算法专栏,希望能帮助大家很好的了解算法。主要深入解析每个算法,从概念到示例。 我们一起努力

    2024年02月08日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包