考研算法29天:希尔排序 【希尔排序】
算法介绍
希尔排序 = 等差数列 + 普通版插入排序
循环数组

第一次每n/2为间隔分为4组,然后组内排序。
第二次每n/4为间隔分为2组。然后组内排序
第三次n/8为间隔分为一组。然后组内排序。
组内排序用插入排序来排序。
注:也可以第一次为n/3为间隔,第二次为n/3^2,,第三次为n/3^3.这个随你定义。

上面这个图片是讲采用3的分法的话最坏算法时间复杂度只有O(n*开平方n)。

c++中的sort = 快排 + 插排
算法题目

算法ac代码:
#include <iostream>using namespace std;const int N = 1000010;
int q[N];void shell_sort(int n){for(int d=n/2;d>=1;d = d/2)//算出每次的公差{for(int start=0;start<d;start++)//每次的开始下标{//插入排序for(int i=start+d;i<n;i=i+d){int x = q[i],j=i;while(j>start&&q[j-d]>x){q[j] = q[j-d];j = j-d;}q[j] = x;}}}return;
}
int main(){int n;cin>>n;for(int i=0;i<n;i++)scanf("%d",&q[i]);shell_sort(n);for(int i=0;i<n;i++)printf("%d ",q[i]);return 0;
}
算法复杂度
时间复杂度:
要看你是按照啥规矩分的组,不同分组的时间复杂度不一样,如果是按照“2”的话时间复杂度为O(N^2)
空间复杂度
O(1)
稳定性:
原先的元素的相对位置会不一样,所以不稳定。
快排和希尔排序时间复杂度最坏情况是不考虑的,其发生这样的情况的概率就如小型星球撞地球的概率一样,可以忽略不计。
相关文章:
考研算法29天:希尔排序 【希尔排序】
算法介绍 希尔排序 等差数列 普通版插入排序 循环数组 第一次每n/2为间隔分为4组,然后组内排序。 第二次每n/4为间隔分为2组。然后组内排序 第三次n/8为间隔分为一组。然后组内排序。 组内排序用插入排序来排序。 注:也可以第一次为n/3为间隔&am…...
RN 学习小记之使用 Expo 创建项目
本文Hexo博客链接🔗 https://ysx.cosine.ren/react-native-note-1 xLog链接🔗 https://x.cosine.ren/react-native-note-1 RSS订阅 📢 https://x.cosine.ren/feed/xml 由于业务需要,开始学习RN以备后面的需求,而虽然之…...
python爬虫从入门到精通
目录 一、正确认识Python爬虫 二、了解爬虫的本质 1. 熟悉Python编程 2. 了解HTML 3. 了解网络爬虫的基本原理 4. 学习使用Python爬虫库 三、了解非结构化数据的存储 1. 本地文件 2. 数据库 四、掌握各种技巧,应对特殊网站的反爬措施 1. User-Agent 2. C…...
从0到1精通自动化,接口自动化测试——数据驱动DDT实战
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 DDT简介 名称&am…...
【微服务】springboot整合swagger多种模式使用详解
目录 一、前言 1.1 编写API文档 1.2 使用一些在线调试工具 1.3 postman 1.4 swagger 二、swagger简介</...
AI 绘画(1):生成一个图片的标准流程
文章目录 文章回顾感谢人员生成一个图片的标准流程前期准备,以文生图为例去C站下载你需要的绘画模型导入参数导入生成结果?可能是BUG事后处理 图生图如何高度贴合原图火柴人转角色 涂鸦局部重绘 Ai绘画公约 文章回顾 AI 绘画(0)&…...
CPU、内存、缓存的关系
术语解释 (1)CPU(Central Processing Unit) 中央处理器 (2)内存 内存用于暂时存放CPU中的运算数据,以及与硬盘等外部存储器交换的数据。它是外存与CPU进行沟通的桥梁,内存的运行决定…...
AI黑客松近期比赛清单;36氪AI淘宝店盈利复盘;GitHub Copilot官方最佳实践;AI在HR领域的应用探索 | ShowMeAI日报
👀日报&周刊合集 | 🎡生产力工具与行业应用大全 | 🧡 点赞关注评论拜托啦! ⋙ 点击查看 AI Hackathon (黑客马拉松) 汇总清单 🤖 〖飞桨〗2023大模型应用创新挑战赛 百度飞桨联合上海市青年五十人创新创业研究院等…...
想要让视频素材格式快速调整转换的方法分享
有时候有些视频播放软件不支持播放某些格式的视频文件?那要怎么解决呢?换一个播放软件?不妨试试批量转换视频格式,简单的几步操作就能快速解决烦恼,跟着小编一起来看看具体的操作环节吧。 首先先进入“固乔科技”的官网…...
面向对象分析与设计 UML2.0 学习笔记
一、认识UML UML-Unified Modeling Language 统一建模语言,又称标准建模语言。是用来对软件密集系统进行可视化建模的一种语言。UML的定义包括UML语义和UML表示法两个元素。 UML是在开发阶段,说明、可视化、构建和书写一个面向对象软件密集系统的制品的…...
[数据库系统] 五、数据增删改
第一关:数据插入 用insert给数据库添加数据 相关知识 有关系student(sno,sname,ssex,sage,sdept),属性对应含义:学号,姓名,性别,所在系。现有的部分元组如下所示 insert 向数据库表插入数据的基本格式有…...
docker私有注册表创建和使用
说明 本文给出了一个具体的使用docker registry和nginx配置docker私有注册表的方案。 创建和配置 docker compose 使用docker compose的方式运行registry容器,配置如下: # cat docker-compose.yml services:registry:image: registry:2ports:- &quo…...
用OpenCV进行OCR字符分割
1. 引言 本文重点介绍如何利用传统的图像处理的方法来进行OCR字符切分,进而可以用分割后的单个字符做相应的后续任务,虽然现在计算机视觉依然是卷积神经网络的天下,但是对于一些相对简单的落地场景传统方案还是很有效的。 闲话少说ÿ…...
MyCat Docker 搭建与测试
mycat 是mysql分库分表的中间件,由java编写,本次进行mysql、mycat 的docker搭建,理解mycat的原理与特性。 一、mysql docker 搭建 这里启动两个实例: docker run -itd --name mysql1 -p 3307:3306 -e MYSQL_ROOT_PASSWORD123 m…...
车载通讯USB开发,增强车内娱乐体验
车载通讯开发中使用的 USB 协议常见于车内娱乐系统、车载设备和汽车诊断工具等应用。USB(Universal Serial Bus,通用串行总线)是一种常见的数字通信接口标准,用于连接计算机、外部设备及其他电子设备之间的数据传输和通信。 USB …...
js的一些小技巧
大厂面试题分享 面试题库 前后端面试题库 (面试必备) 推荐:★★★★★ 地址:前端面试题库 web前端面试题库 VS java后端面试题库大全 作用域 全局作用域局部作用域(函数里)也称函数作用域块级作用域 {…...
Springboot Mybatis 自定义顺序排序查询,指定某个字段
前言 与本文无关 "我进去了" ....... 正文 今天要讲些什么? 其实很简单,就是查询数据的时候,想根据自己指定的字段的自定义顺序,做排序查询数据。 本篇文章会讲到的几个点 : 1. 单纯sql 怎么实现 排序2. …...
期刊会议审稿意见
AAAI 修改意见 违背了研究方向的假设;虽然实验结果不错,但是没有明确地指向任何成功的方向,作者也没有充分地处理失败的案例——The results, though good are not clearly pointing to any direction of success, and the authors have no…...
Java类加载机制:从字节码到对象的奇妙之旅
目录 什么是类加载机制? 类加载顺序 类加载顺序图 双亲委派模型 双亲委派模型示意图 如何打破双亲委派模型? 要想学好java,首先得知道它是什么,怎么运行的,怎么加载的,运行的是个什么东西,…...
代码随想录第一天|二分法、双指针
代码随想录第一天 Leetcode 704 二分查找Leetcode 35 搜索插入位置Leetcode 34 在排序数组中查找元素的第一个和最后一个位置Leetcode 69 x 的平方根Leetcode 367 有效的完全平方数Leetcode 27 移除元素Leetcode 26 删除有序数组中的重复项Leetcode 283 移动零Leetcode 844 比较…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
微服务通信安全:深入解析mTLS的原理与实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言:微服务时代的通信安全挑战 随着云原生和微服务架构的普及,服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...
ThreadLocal 源码
ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物,因为每个访问一个线程局部变量的线程(通过其 get 或 set 方法)都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段,这些类希望将…...
【PX4飞控】mavros gps相关话题分析,经纬度海拔获取方法,卫星数锁定状态获取方法
使用 ROS1-Noetic 和 mavros v1.20.1, 携带经纬度海拔的话题主要有三个: /mavros/global_position/raw/fix/mavros/gpsstatus/gps1/raw/mavros/global_position/global 查看 mavros 源码,来分析他们的发布过程。发现前两个话题都对应了同一…...
Selenium 查找页面元素的方式
Selenium 查找页面元素的方式 Selenium 提供了多种方法来查找网页中的元素,以下是主要的定位方式: 基本定位方式 通过ID定位 driver.find_element(By.ID, "element_id")通过Name定位 driver.find_element(By.NAME, "element_name"…...
