【algorithm】算法基础课---排序算法(附笔记 | 建议收藏)

🚀write in front🚀
📝个人主页:认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏:AcWing算法学习笔记
💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🖊
✉️如果无聊的话,就来逛逛我的博客栈吧stack-frame.cn

文章目录

  • 前言
  • 一、快速排序
    • 1.1快速排序的知识讲解
    • 1.2快速排序的习题讲解
    • 1.3对于快排的总结
  • 二、归并排序
    • 2.1归并排序的知识讲解
    • 2.2归并排序的习题讲解
    • 2.3对于归并的总结
  • 总结


前言

在这里插入图片描述

之前其实做过关于快速排序以及归并排序的博客笔记,但是我觉得我讲解的是不到位,所以我打算重新写一篇博客来帮助自己和大家梳理一下这两个算法模板以及配套的习题。


其实就是把元素放到x的两侧

一、快速排序

1.1快速排序的知识讲解

快速排序的核心思想基于分治
快速排序主要的内容就是:

  • 确定分界点:q[L],q[(L+R)/2],q[R] 其实就是分为左边界,中间值和右边界,甚至随机一个数

  • 调整区间,其实就是把元素放到x的两侧

  • 递归处理左右两段
    在这里插入图片描述
    下面就是具体讲解步骤二的调整区间
    在这里插入图片描述

  • 两个指针,i,j不断在这里面移动

  • 当指针i指向的元素<=x的时候就指针向右移动同理指针j遇到>=x的时候就指针向左移动

  • 当i指针指向的元素>=x的时候停下来,等到j指针指向的元素<=x的时候就也停下来

  • 最后使得这两个元素进行swap交换一下

在这里插入图片描述
以上就是快速排序的基础知识啦,下面就要讲解一些习题来巩固和练习我们所讲解的知识点啦

快排思想图:
在这里插入图片描述

1.2快速排序的习题讲解

在这里插入图片描述
C语言实现:

#include<stdio.h>
int arr[100010];void quick_sort(int arr[],int l,int r)
{if(l>=r) return;int i=l-1,j=l+1,x=arr[l];while(i<j){do i++;while(arr[i]>x);do j--;while(arr[j]<x);if(i<j){int tmp=arr[i];arr[i]=arr[j];arr[j]=tmp;}}quick_sort(arr,l,j);quick_sort(arr,j+1,r);}int main()
{int n;scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&arr[i]);quick_sort(arr,0,n-1);for(int i=0;i<n;i++) printf("%d ",arr[i]);return 0;
}

C++实现:

#include <iostream>using namespace std;const int N = 1000010;int q[N];void quick_sort(int q[],int l,int r)
{if (l>=r) return;int i=l-1, j=r+1,x=q[l+r>>1];while (i<j){do i++; while (q[i]<x);do j--; while (q[j]>x);if (i<j) swap(q[i], q[j]);}quick_sort(q,l,j);quick_sort(q,j + 1,r);
}int main()
{int n;scanf("%d", &n);for (int i=0; i<n; i++) scanf("%d", &q[i]);quick_sort(q,0,n-1);for (int i=0; i<n;i ++) printf("%d ", q[i]);return 0;
}

在这里插入图片描述

#include<stdio.h>
void quick_sort(int arr[],int l,int r)
{if(l>=r) return;int i=l-1,j=r+1,x=arr[l];while(i<j){do i++;while(arr[i]<x);do j--;while(arr[j]>x);if(i<j){int tmp=arr[i];arr[i]=arr[j];arr[j]=tmp;}}quick_sort(arr,l,j);quick_sort(arr,j+1,r);
}
int main()
{int arr[100010];int n,k;scanf("%d %d",&n,&k);for(int i=0;i<n;i++) scanf("%d",&arr[i]);quick_sort(arr,0,n-1);for(int i=0;i<n;i++) {if(i+1==k) printf("%d",arr[i]);}return 0;
}

其实C++和这个差不多,这里不再赘述了。

1.3对于快排的总结

其实就是自己要多练习几遍,反复敲打上几次就可以啦,然后隔一段时间再写一次看看自己是否可以再次写出来这个模板。

二、归并排序

2.1归并排序的知识讲解

归并排序的核心思想基于分治
归并排序主要的内容就是:

  • 确定分界点mid=(left+right)/2
  • 递归排序left,right
  • 归并,合二为一
    在这里插入图片描述
    下面就讲解一下,归并排序的大致思路
  • 先比较两个指针所指向的元素谁大谁小
  • 谁小就拿下来放到新的保存数组里面,然后指针向后挪动一位依次类推
  • 直到其中一个指针走向了终点的位置为止,就可以把没有走完的直接补充到我们的保存数组里面

在这里插入图片描述
归并排序的原理动图:
在这里插入图片描述

2.2归并排序的习题讲解

在这里插入图片描述

#include<stdio.h>
const int N=100010;
int arr[N],tmp[N];void merge_sprt(int arr[],int l,int r)
{if(l>=r) return;int mid=(l+r)/2;merge_sprt(arr,l,mid),merge_sprt(arr,mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(arr[i]<=arr[j]) tmp[k++]=arr[i++];else tmp[k++]=arr[j++];}while(i<=mid) tmp[k++]=arr[i++];while(j<=r) tmp[k++]=arr[j++];for(int i=l,j=0;i<=r;i++,j++) arr[i]=tmp[j];}
int main()
{int n;scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&arr[i]);merge_sprt(arr,0,n-1);for(int i=0;i<n;i++) printf("%d ",arr[i]);return 0;
}

2.3对于归并的总结

主要对于逆序对问题很重要归并排序。

总结

今天重新写了一篇关于AcWing算法基础课的一篇博客,其实我第一次看的时候会觉得很难,但是今天又看了一遍,发现,简单了很多,或许我们曾经不会的,或许以后就会慢慢掌握,希望遇到困难的时候第一想到的不是退缩和放弃,而是拼尽全力试一试看看到底自己能不能行。
在这里插入图片描述
我是夏目浅石,希望和你一起学习进步,刷题无数!!!希望各位大佬能一键三连支持一下博主,hhhh~我们下期见喽

在这里插入图片描述
如果无聊的话,就来逛逛我的博客栈吧stack-frame.cn

原创不易,还希望各位大佬支持一下 \textcolor{blue}{原创不易,还希望各位大佬支持一下} 原创不易,还希望各位大佬支持一下

👍 点赞,你的认可是我创作的动力! \textcolor{9c81c1}{点赞,你的认可是我创作的动力!} 点赞,你的认可是我创作的动力!

⭐️ 收藏,你的青睐是我努力的方向! \textcolor{ed7976}{收藏,你的青睐是我努力的方向!} 收藏,你的青睐是我努力的方向!

✏️ 评论,你的意见是我进步的财富! \textcolor{98c091}{评论,你的意见是我进步的财富!} 评论,你的意见是我进步的财富!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/269323.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

(3)(3.2) MAVLink2数据包签名(安全)

文章目录 前言 1 配置 2 使用 3 MAVLink协议说明 前言 ArduPilot 和任务计划器能够通过使用加密密钥添加数据包签名&#xff0c;为空中 MAVLink 传输增加安全性。这并不加密数据&#xff0c;只是控制自动驾驶仪是否响应 MAVLink 命令。 当自动驾驶仪处于激活状态时&#x…

【C语言】Leetcode 206.反转链表

博主主页&#xff1a;17_Kevin-CSDN博客 收录专栏&#xff1a;《Leetcode》 题目 解决思路 思路一&#xff1a;翻转链表 struct ListNode* reverseList(struct ListNode* head) {if(head NULL){return NULL;}struct ListNode* n1 NULL,*n2 head,*n3 n2 -> next;while(…

Dell R730 2U服务器实践2:VMWare ESXi安装

缘起 刚到手边的一台Dell R730是三块硬盘raid0 &#xff0c;把我惊出一身冷汗&#xff0c;准备把它们改组成raid1 或者raid5 。 但是舍不得里面的ESXi 8 &#xff0c;寻找能否把raid0改成raid1 还不掉WSXi的方法&#xff0c;很遗憾没有找到。那样只能重装ESXi了。 ESXi软件下…

MyCAT学习——在openEuler22.03中安装MyCAT2(网盘下载版)

准备工作 因为MyCAT 2基于JDK 1.8开发。也需要在虚拟机中安装JDK&#xff08;JDK官网就能下载&#xff0c;我这提供一个捷径&#xff09; jdk-8u401-linux-x64.rpmhttps://pan.baidu.com/s/1ywcDsxYOmfZONpmH9oDjfw?pwdrhel下载对应的tar安装包,以及对应的jar包 安装程序包…

Tomcat概念、安装及相关文件介绍

目录 一、web技术 1、C/S架构与B/S架构 1.1 http协议与C/S架构 1.2 http协议与B/S架构 2、前端三大核心技术 2.1 HTML&#xff08;Hypertext Markup Language&#xff09; 2.2 css&#xff08;Cascading Style Sheets&#xff09; 2.3 JavaScript 3、同步和异步 4、…

如何使用 ArcGIS Pro 统计四川省各市道路长度

在某些时候&#xff0c;我们需要进行分区统计&#xff0c;如果挨个裁剪数据再统计&#xff0c;不仅步骤繁琐、耗时&#xff0c;还会产生一些多余的数据&#xff0c;这里教大家如何在不裁剪数据的情况下统计四川各市的道路长度&#xff0c;希望能对你有所帮助。 数据来源 教程…

苹果发布新款 MacBook Air 13/15升级M3售8999元起

苹果官网发布新款 MacBook Air&#xff0c;13 英寸和 15 英寸同时升级。 搭载 M3 芯片&#xff0c;性能更强&#xff0c;续航最长可达 18 小时&#xff0c;最多可连接两台外接显示器。 这是一次常规的芯片升级&#xff0c;外观相比上代没有变化。拥有午夜色、星光色、深空灰和银…

在vue前端开发中基于refreshToken和axios拦截器实现token的无感刷新

文章目录 一、需求背景二、token刷新的方案1、根据过期时间重新获取2、定时刷新token接口3、使用了RefreshToken 三、关于RefreshToken四、Refresh Token的优点五、Refresh Token的工作原理六、Refresh Token的使用流程七、Refresh Token的实现步骤1、登录成功后保存AccessToke…

机器人顶刊IJRR近期国人新作(2024)

一、IJRR简介 The International Journal of Robotics Research&#xff08;IJRR&#xff09;是机器人领域的高水平学术期刊&#xff0c;专注于发布关于机器人技术和相关领域的最新研究成果。IJRR创刊于1982年&#xff0c;是该领域的第一本学术刊物&#xff0c;2022-2023最新影…

销量王者!三一新能源搅拌车助力商砼运输走向低碳未来

2023年,在国家扩大内需和“双碳战略”的双重推进下,新老基建项目开工速度纷纷加快,各个行业对应用于工程基建、房地产等中短途混凝土运输的新能源搅拌车有了更大的需求量。 终端上牌数据显示,2023年1-12月新能源重卡累计销售23560辆,同比增长35.65%。其中,搅拌车销量暴涨,实销…

Kafka面经

1.Kafka如何保证消息不丢失 生产者&#xff1a; 1.Producer 默认是异步发送消息&#xff0c;这种情况下要确保消息发送成功&#xff0c;有两个方法 a. 把异步发送改成同步发送&#xff0c;这样 producer 就能实时知道消息发送的结果。 b. 添加异步回调函数来监听消息发送的结…

C++模拟揭秘刘谦魔术,领略数学的魅力

新的一年又开始了&#xff0c;大家新年好呀~。在这我想问大家一个问题&#xff0c;有没有同学看了联欢晚会上刘谦的魔术呢&#xff1f; 这个节目还挺有意思的&#xff0c;它最出彩的不是魔术本身&#xff0c;而是小尼老师“念错咒语”而导致他手里的排没有拼在一起&#xff0c;…

新手想玩硬件,买单片机还是树莓派好?

新手想玩硬件&#xff0c;买单片机还是树莓派好&#xff1f; 在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「单片机的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#x…

前端食堂技术周刊第 114 期:Interop 2024、TS 5.4 RC、2 月登陆浏览器的新功能、JSR、AI SDK 3.0

美味值&#xff1a;&#x1f31f;&#x1f31f;&#x1f31f;&#x1f31f;&#x1f31f; 口味&#xff1a;凉拌鸡架 食堂技术周刊仓库地址&#xff1a;https://github.com/Geekhyt/weekly 大家好&#xff0c;我是童欧巴。欢迎来到前端食堂技术周刊&#xff0c;我们先来看下…

一本书讲透ChatGPT——理论与实践的完美结合,大模型技术工程师的必备指南

写在前面 OpenAI 在 2022 年 11 月推出了人工智能聊天应用—ChatGPT。它具有广泛的应用场景&#xff0c;在多项专业和学术基准测试中表现出的智力水平&#xff0c;不仅接近甚至有时超越了人类的平均水平。这使得 ChatGPT 在推出之初就受到广大用户的欢迎&#xff0c;被科技界誉…

Centos 9 安装 k8s

为了尽可能契合生产环境的部署情况&#xff0c;这里用kubeadm安装集群&#xff0c;同时方便跟随笔记一步步实践的过程&#xff0c;也更加了解k8s的一些特性和基础知识。 先决条件 这里将通过虚拟机安装3台centos stream 9服务器&#xff0c;并组成kubeneters集群&#xff08;…

蓝桥杯练习题——dp

五部曲&#xff08;代码随想录&#xff09; 1.确定 dp 数组以及下标含义 2.确定递推公式 3.确定 dp 数组初始化 4.确定遍历顺序 5.debug 入门题 1.斐波那契数 思路 1.f[i]&#xff1a;第 i 个数的值 2.f[i] f[i - 1] f[i - 2] 3.f[0] 0, f[1] 1 4.顺序遍历 5.记得特判 …

SAP HANA中PAL算法使用入门

1 应用场合 SAP HANA作为一款内存数据库产品, 使得数据常驻内存, 物理磁盘的存储作为数据备份与日志记录, 以防断电内存中数据丢失. 这种构架大大的缩短了数据存取的时间, 使得SAP HANA很”高速”. 在传统数据模型中,数据库只是作为存取数据一个工具,对于类似下图所示的应用, 客…

5分钟速成渐变色css

色彩的分支——渐变色定义&#xff1a;按照一定规律做阶段性变化的色彩&#xff08;抽象&#xff01;&#xff01;&#xff01;&#xff09; 我们可以将图片分为两块 以中心线为参考&#xff0c;再来看渐变色的定义&#xff1a;按照一定规律做阶段性变化的色彩 既然是按一定的…

京津冀光伏展

京津冀光伏展是中国在京津冀地区举办的一项光伏产业展览活动。该展览旨在展示京津冀地区光伏产业的最新发展成果&#xff0c;促进光伏行业的交流与合作&#xff0c;推动光伏产业的可持续发展。 光伏产业是指利用太阳能将光能转化为电能的产业。作为一种清洁能源&#xff0c;光伏…