学习记录day18——数据结构 算法
算法的相关概念
程序 = 数据结构 + 算法
算法是程序设计的灵魂,结构式程序设计的肉体
算法:计算机解决问题的方法护额步骤
算法的特性
1、确定性:算法中每一条语句都有确定的含义,不能模棱两可
2、有穷性:程序执行一段时间后会自动结束
3、输入:有零个或多个输入
4、输出:至少一个输出,可输出多个
5、可行性:经济可行性、社会可行性、能够运行
算法的设计要求
1、正确性:给定合理的输入数据能够得到正确的结果
2、健壮性:对于给定的不合理的输入数据,能够给出相应的处理措施
3、可读性:程序核心代码写注释、程序代码有缩进、程序代码命名规范
4、高效率:要求设计复杂度尽可能低
5、低存储:要求空间复杂度尽可能低
时间复杂度
算法执行消耗时间的度量
计算公式:T(n) = O(f(n));
        T(n):时间复杂度
         n:表示问题的规模
         f(n):是问题规模与执行次数之间的函数
         O(f(n)):使用O阶记法,记录算法时间复杂度

常见的数据复杂度

排序算法
根据数据元素的关键字,按照升序或降序的方式将数据元素重新排列的过程称为排序
排序的分类
1、交换类:冒泡排序、快速排序
2、选择类:简单选择排序、堆排序
3、插入类:直接插入排序、折半插入排序
4、归并类:二路归并、多路归并
冒泡排序
1、在排序过程中,越大(小)的数据,经由交换后,会慢慢的“浮”到顶端,如同气泡一样
2、冒泡排序原理
1)比较相邻元素,如果第一个比第二个大(小)则交换
2)经过一趟排序后会使最大(最小)的元素落到最后 重复上面的步骤,直到没有任何一对 数字需要比较为止
3)当某一趟的排序过程中,出现没有数据交换的过程,则结束整个排序
3、算法
void bubble_sort(int *arr, int n)
{for (int i = 1; i < n; i++)         //外循环  控制趟数   {int flag = 0;                   //定义一个标志位  及   标准位重置for (int j = 0; j < n - i; j++) //内循环  交换位置{if (arr[j] > arr[j+ 1])     //判定是否交换(升序排列){flag = 1;               //标志位 置1int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}if (flag == 0)       //标志位为0 说明未进入if语句 即排列已完成 直接退出循环{break;}}printf("bubble_sort on\n");
}
 
选择排序
        每次从待排序序列中,找到最大(小)值,将其与待排序序列的第一个进行交换
1、排序步骤:
1)从待排序序列中选择最值
2)如果最值不是待排序序列的第一个,则进行交换
3)从剩余待排序序列中,继续重复前两次的操作,直到,待排序序列为空
2、算法
void select_sort(int *arr, int n)
{int min = 0;     //定义一个变量 存储最小值for (int i = 0; i < n; i++){min = i;    //记录下标for (int j = i + 1; j < n; j++){if (arr[min] > arr[j])  //更新最小值{min = j;}}if (min != i)          //如果最小值不是待排序序列第一个 则换置换{int temp = arr[min];arr[min] = arr[i];arr[i] = temp;}}printf("select_sort on\n");
}
 
直接插入排序
每次从待排序序列中,选择第一个,将其插入到已排序序列中
1、排序步骤
1)选取待排序序列中的第一个元素
2)跟前面的元素依次比较,如果前面的比当前元素大(小),则将前面的元素后移一位
3)直到出现前面的不比当前的大(小)或者已经到最前面了,将选取的元素,放入空位置上
4)对于待排序序列中的所有元素,重复上述操作
2、算法
void insert_sort(int *arr),int n
{int i,j;                     //需要在循环外使用for (i = 1; i < n; i++){int temp = arr[i];      //记录要移动的元素数值    for ( j = i-1; temp= < arr[j] && j >= 0;  j--)   //实现的效果:                                                                           {                                                //如果记录的数值小于等于已排列序列arr[j+1] = arr[j];                           //中的某个数,从那个数开始整体后移}                                                //但实际上是逐个比较,逐个后移arr[j+1] = temp;                                 //后移结束 插入记录的元素数值                                 }printf("insert_sort on\n");
} 
快速排序
快速排序是在序列元素与选定基准元素比较分割为大小两部分的交换排序
时间复杂度:O(nlog2n) n倍以2为底2的对数

1、排序步骤
1)从待排序列中任取一个基准元素
2)与基准元素比较将待排序列分割为大小两部分
3)再对各部分重新选择基准元素并依此规则排序 直到每个部分只剩一个元素为止
2、算法
int part(int *arr,int low ,int high)
{int X = arr[0];        //将第一个元素定为基准while(low < high)      //循环条件{while (low < high && arr[low] >= X)   //避免错位   {high--;}arr[low] = arr[high];     //将小值前置while (low < high && arr[high] =< X){low++;}arr[high] = arr[low];     //将大值后置}//循环结束  此时 low == higharr[low] = X;   //将基准放入指定位置return low;  //返回基准下标
}
void quick_sort(int *arr ,int low ,int high)
{if (low => high)   {return;    //递归出口   只有一个元素时}int mid = part(arr,low,high);  //找到基准quick_sort(arr,low,mid-1);   //对较小端进行递归quick_sort(arr,mid+1,high);  //对较大端进行递归return ;
} 
相关文章:
学习记录day18——数据结构 算法
算法的相关概念 程序 数据结构 算法 算法是程序设计的灵魂,结构式程序设计的肉体 算法:计算机解决问题的方法护额步骤 算法的特性 1、确定性:算法中每一条语句都有确定的含义,不能模棱两可 2、有穷性:程序执行一…...
一篇文章带你学完Java所有的时间与日期类
目录 一、传统时间与日期类 1.Date类 构造方法 获取日期和时间信息的方法 设置日期和时间信息的方法 2.Calendar类 主要特点和功能 常用方法 1. 获取当前日历对象 2. 获取日历中的某个信息 3. 获取日期对象 4. 获取时间毫秒值 5. 修改日历的某个信息 6. 为某个信息增…...
利用GPT4o Captcha工具和AI技术全面识别验证码
利用GPT4o Captcha工具和AI技术全面识别验证码 🧠🚀 摘要 GPT4o Captcha工具是一款命令行工具,通过Python和Selenium测试各种类型的验证码,包括拼图、文本、复杂文本和reCAPTCHA,并使用OpenAI GPT-4帮助解决验证码问…...
大学生算法高等数学学习平台设计方案 (第一版)
目录 目标用户群体的精准定位 初阶探索者 进阶学习者 资深研究者 功能需求的深度拓展 个性化学习路径定制 概念图谱构建 公式推导展示 交互式问题解决系统 新功能和创新点的引入 虚拟教室环境 数学建模工具集成 算法可视化平台 学术论文资源库 技术实现的前瞻性…...
机器学习算法与Python实战 | 两行代码即可应用 40 个机器学习模型--lazypredict 库!
本文来源公众号“机器学习算法与Python实战”,仅用于学术分享,侵权删,干货满满。 原文链接:两行代码即可应用 40 个机器学习模型 今天和大家一起学习使用 lazypredict 库,我们可以用一行代码在我们的数据集上实现许多…...
使用WebSocket协议调用群发方法将消息返回客户端页面
目录 一.C/S架构: 二.Http协议与WebSocket协议的区别: 1.Http协议与WebSocket协议的区别: 2.WebSocket协议的使用场景: 三.项目实际操作: 1.导入依赖: 2.通过WebSocket实现页面与服务端保持长连接&a…...
【北京迅为】《i.MX8MM嵌入式Linux开发指南》-第三篇 嵌入式Linux驱动开发篇-第五十七章 Linux中断实验
i.MX8MM处理器采用了先进的14LPCFinFET工艺,提供更快的速度和更高的电源效率;四核Cortex-A53,单核Cortex-M4,多达五个内核 ,主频高达1.8GHz,2G DDR4内存、8G EMMC存储。千兆工业级以太网、MIPI-DSI、USB HOST、WIFI/BT…...
每日一题~961div2A+B+C(阅读题,思维,数学log)
A 题意:给你 n*n 的表格和k 个筹码。每个格子上至多放一个 问至少占据多少对角线。 显然,要先 格数的多的格子去放。 n n-1 n-2 …1 只有n 的是一个(主对角线),其他的是两个。 #include <bits/stdc.h> using na…...
Fireflyrk3288 ubuntu18.04添加Qt开发环境、安装mysql-server
1、创建一台同版本的ubuntu18.04的虚拟机 2、下载rk3288_ubuntu_18.04_armhf_ext4_v2.04_20201125-1538_DESKTOP.img 3、创建空img镜像容器 dd if/dev/zero ofubuntu_rootfs.img bs1M count102404、将该容器格式化成ext4文件系统 mkfs.ext4 ubuntu_rootfs.img5、将该镜像文件…...
简化mybatis @Select IN条件的编写
最近从JPA切换到Mybatis,使用无XML配置,Select注解直接写到interface上,发现IN条件的编写相当麻烦。 一般得写成这样: Select({"<script>","SELECT *", "FROM blog","WHERE id IN&quo…...
Windows图形界面(GUI)-MFC-C/C++ - Control
公开视频 -> 链接点击跳转公开课程博客首页 -> 链接点击跳转博客主页 目录 Control 资源编辑器 添加控件 设置控件属性 添加控件变量 添加消息处理 处理控件事件 控件焦点顺序 Control 资源编辑器 资源编辑器:用于可视化地编辑对话框和控件。…...
SQL Server数据库安全:策略制定与实践指南
SQL Server数据库安全:策略制定与实践指南 在当今数字化时代,数据安全是每个组织的核心关注点。SQL Server作为广泛使用的关系型数据库管理系统,提供了一套强大的安全特性来保护存储的数据。制定有效的数据库安全策略是确保数据完整性、可用…...
Spring Boot入门指南:留言板
一.留言板 1.输⼊留⾔信息,点击提交.后端把数据存储起来. 2.⻚⾯展⽰输⼊的表⽩墙的信息 规范: 1.写一个类MessageInfo对象,添加构造方法 虽然有快捷键,但是还是不够偷懒 项目添加Lombok。 Lombok是⼀个Java⼯具库,通过添加注…...
Docker 中安装和配置带用户名和密码保护的 Elasticsearch
在 Docker 中安装和配置带用户名和密码保护的 Elasticsearch 需要以下步骤。Elasticsearch 的安全功能(包括基本身份验证)在默认情况下是启用的,但在某些版本中可能需要手动配置。以下是详细步骤,包括如何设置用户名和密码。 1. …...
面试官:说说JVM内存调优及内存结构
1. JVM简介 JVM(Java虚拟机)是运行Java程序的平台,它使得Java能够跨平台运行。JVM负责内存的自动分配和回收,减轻了程序员的负担。 2. JVM内存结构 运行时数据区是JVM中最重要的部分,包含多个内存区域: …...
Ansible的脚本-----playbook剧本【下】
目录 实战演练六:tags 模块 实战演练七:Templates 模块 实战演练六:tags 模块 可以在一个playbook中为某个或某些任务定义“标签”,在执行此playbook时通过ansible-playbook命令使用--tags选项能实现仅运行指定的tasks。 playboo…...
Mysql开启远程控制简化版,亲测有效
首先关闭防火墙 改表法 打开上图的CMD,输入密码进入,然后输入一下指令 1.use mysql; 2.update user set host % where user root;//更新root用户的权限,允许任何主机连接 3.FLUSH PRIVILEGES;//刷新权限,使更改生效 具体参考…...
【MQTT协议与IoT通信】MQTT协议的使用和管理
MQTT协议与IoT通信:MQTT协议的使用和管理 目录 引言MQTT协议概述 什么是MQTTMQTT的工作原理 MQTT协议的关键特性 轻量级与高效性发布/订阅模式质量服务等级(QoS)持久会话安全性 MQTT协议的使用方法 设置MQTT Broker连接MQTT Client发布消息订阅主题断开连接 MQTT协…...
根据题意写出完整的css,html和js代码【购物车模块页面及功能实现】
🏆本文收录于《CSDN问答解惑-专业版》专栏,主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收…...
AWS免费层之后:了解和管理您的云服务成本
Amazon Web Services (AWS) 为新用户提供了12个月的免费层服务,这是许多人开始使用云服务的绝佳方式。但是,当这一年结束后,您的AWS使用会如何变化?我们九河云通过本文将探讨免费层结束后的AWS成本情况,以及如何有效管…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。  - 个性化梦境…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
