当前位置: 首页 > news >正文

考研算法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组&#xff0c;然后组内排序。 第二次每n/4为间隔分为2组。然后组内排序 第三次n/8为间隔分为一组。然后组内排序。 组内排序用插入排序来排序。 注&#xff1a;也可以第一次为n/3为间隔&am…...

RN 学习小记之使用 Expo 创建项目

本文Hexo博客链接&#x1f517; https://ysx.cosine.ren/react-native-note-1 xLog链接&#x1f517; https://x.cosine.ren/react-native-note-1 RSS订阅 &#x1f4e2; https://x.cosine.ren/feed/xml 由于业务需要&#xff0c;开始学习RN以备后面的需求&#xff0c;而虽然之…...

python爬虫从入门到精通

目录 一、正确认识Python爬虫 二、了解爬虫的本质 1. 熟悉Python编程 2. 了解HTML 3. 了解网络爬虫的基本原理 4. 学习使用Python爬虫库 三、了解非结构化数据的存储 1. 本地文件 2. 数据库 四、掌握各种技巧&#xff0c;应对特殊网站的反爬措施 1. User-Agent 2. C…...

从0到1精通自动化,接口自动化测试——数据驱动DDT实战

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 DDT简介 名称&am…...

【微服务】springboot整合swagger多种模式使用详解

目录 一、前言 1.1 编写API文档 1.2 使用一些在线调试工具 1.3 postman 1.4 swagger 二、swagger简介</...

AI 绘画(1):生成一个图片的标准流程

文章目录 文章回顾感谢人员生成一个图片的标准流程前期准备&#xff0c;以文生图为例去C站下载你需要的绘画模型导入参数导入生成结果&#xff1f;可能是BUG事后处理 图生图如何高度贴合原图火柴人转角色 涂鸦局部重绘 Ai绘画公约 文章回顾 AI 绘画&#xff08;0&#xff09;&…...

CPU、内存、缓存的关系

术语解释 &#xff08;1&#xff09;CPU&#xff08;Central Processing Unit&#xff09; 中央处理器 &#xff08;2&#xff09;内存 内存用于暂时存放CPU中的运算数据&#xff0c;以及与硬盘等外部存储器交换的数据。它是外存与CPU进行沟通的桥梁&#xff0c;内存的运行决定…...

AI黑客松近期比赛清单;36氪AI淘宝店盈利复盘;GitHub Copilot官方最佳实践;AI在HR领域的应用探索 | ShowMeAI日报

&#x1f440;日报&周刊合集 | &#x1f3a1;生产力工具与行业应用大全 | &#x1f9e1; 点赞关注评论拜托啦&#xff01; ⋙ 点击查看 AI Hackathon (黑客马拉松) 汇总清单 &#x1f916; 〖飞桨〗2023大模型应用创新挑战赛 百度飞桨联合上海市青年五十人创新创业研究院等…...

想要让视频素材格式快速调整转换的方法分享

有时候有些视频播放软件不支持播放某些格式的视频文件&#xff1f;那要怎么解决呢&#xff1f;换一个播放软件&#xff1f;不妨试试批量转换视频格式&#xff0c;简单的几步操作就能快速解决烦恼&#xff0c;跟着小编一起来看看具体的操作环节吧。 首先先进入“固乔科技”的官网…...

面向对象分析与设计 UML2.0 学习笔记

一、认识UML UML-Unified Modeling Language 统一建模语言&#xff0c;又称标准建模语言。是用来对软件密集系统进行可视化建模的一种语言。UML的定义包括UML语义和UML表示法两个元素。 UML是在开发阶段&#xff0c;说明、可视化、构建和书写一个面向对象软件密集系统的制品的…...

[数据库系统] 五、数据增删改

第一关&#xff1a;数据插入 用insert给数据库添加数据 相关知识 有关系student(sno,sname,ssex,sage,sdept)&#xff0c;属性对应含义&#xff1a;学号&#xff0c;姓名&#xff0c;性别&#xff0c;所在系。现有的部分元组如下所示 insert 向数据库表插入数据的基本格式有…...

docker私有注册表创建和使用

说明 本文给出了一个具体的使用docker registry和nginx配置docker私有注册表的方案。 创建和配置 docker compose 使用docker compose的方式运行registry容器&#xff0c;配置如下&#xff1a; # cat docker-compose.yml services:registry:image: registry:2ports:- &quo…...

用OpenCV进行OCR字符分割

1. 引言 本文重点介绍如何利用传统的图像处理的方法来进行OCR字符切分&#xff0c;进而可以用分割后的单个字符做相应的后续任务&#xff0c;虽然现在计算机视觉依然是卷积神经网络的天下&#xff0c;但是对于一些相对简单的落地场景传统方案还是很有效的。 闲话少说&#xff…...

MyCat Docker 搭建与测试

mycat 是mysql分库分表的中间件&#xff0c;由java编写&#xff0c;本次进行mysql、mycat 的docker搭建&#xff0c;理解mycat的原理与特性。 一、mysql docker 搭建 这里启动两个实例&#xff1a; docker run -itd --name mysql1 -p 3307:3306 -e MYSQL_ROOT_PASSWORD123 m…...

车载通讯USB开发,增强车内娱乐体验

车载通讯开发中使用的 USB 协议常见于车内娱乐系统、车载设备和汽车诊断工具等应用。USB&#xff08;Universal Serial Bus&#xff0c;通用串行总线&#xff09;是一种常见的数字通信接口标准&#xff0c;用于连接计算机、外部设备及其他电子设备之间的数据传输和通信。 USB …...

js的一些小技巧

大厂面试题分享 面试题库 前后端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★ 地址&#xff1a;前端面试题库 web前端面试题库 VS java后端面试题库大全 作用域 全局作用域局部作用域&#xff08;函数里&#xff09;也称函数作用域块级作用域 {…...

Springboot Mybatis 自定义顺序排序查询,指定某个字段

前言 与本文无关 "我进去了" ....... 正文 今天要讲些什么&#xff1f; 其实很简单&#xff0c;就是查询数据的时候&#xff0c;想根据自己指定的字段的自定义顺序&#xff0c;做排序查询数据。 本篇文章会讲到的几个点 &#xff1a; 1. 单纯sql 怎么实现 排序2. …...

期刊会议审稿意见

AAAI 修改意见 违背了研究方向的假设&#xff1b;虽然实验结果不错&#xff0c;但是没有明确地指向任何成功的方向&#xff0c;作者也没有充分地处理失败的案例——The results, though good are not clearly pointing to any direction of success, and the authors have no…...

Java类加载机制:从字节码到对象的奇妙之旅

目录 什么是类加载机制&#xff1f; 类加载顺序 类加载顺序图 双亲委派模型 双亲委派模型示意图 如何打破双亲委派模型&#xff1f; 要想学好java&#xff0c;首先得知道它是什么&#xff0c;怎么运行的&#xff0c;怎么加载的&#xff0c;运行的是个什么东西&#xff0c…...

代码随想录第一天|二分法、双指针

代码随想录第一天 Leetcode 704 二分查找Leetcode 35 搜索插入位置Leetcode 34 在排序数组中查找元素的第一个和最后一个位置Leetcode 69 x 的平方根Leetcode 367 有效的完全平方数Leetcode 27 移除元素Leetcode 26 删除有序数组中的重复项Leetcode 283 移动零Leetcode 844 比较…...

突破试用限制:开源脚本实现IDM无限使用的完整解决方案

突破试用限制&#xff1a;开源脚本实现IDM无限使用的完整解决方案 【免费下载链接】IDM-Activation-Script IDM Activation & Trail Reset Script 项目地址: https://gitcode.com/gh_mirrors/id/IDM-Activation-Script 一、问题引入&#xff1a;IDM用户的痛点与解决…...

UE5材质编辑器进阶:手把手教你创建并调用自定义ush函数库(附避坑指南)

UE5材质编辑器进阶&#xff1a;打造高效可复用的自定义ush函数库 在虚幻引擎5的材质创作中&#xff0c;重复编写相同的HLSL代码不仅效率低下&#xff0c;还容易引入错误。本文将带你深入理解如何创建并调用自定义ush函数库&#xff0c;提升材质开发的专业性和可维护性。 1. 为什…...

MDS vs PCA:哪种降维方法更适合你的数据?

MDS与PCA深度对比&#xff1a;从算法原理到实战选型指南 当面对高维数据时&#xff0c;降维技术就像一把打开数据奥秘的钥匙。在众多降维方法中&#xff0c;多维尺度变换(MDS)和主成分分析(PCA)是最常被比较的两种经典技术。它们都能将复杂的高维数据简化为更易理解的二维或三维…...

天问Block环境下ASRPRO语音芯片实战:语音交互、GPIO控制与PWM调光开发指南

1. 天问Block与ASRPRO芯片开发入门 第一次接触天问Block和ASRPRO语音芯片时&#xff0c;我被它们的组合惊艳到了。这个开发环境就像乐高积木一样&#xff0c;通过拖拽代码块就能完成复杂的功能开发&#xff0c;特别适合像我这样的硬件爱好者。ASRPRO作为一款专为语音交互设计的…...

Phi-3-mini-4k-instruct-gguf代码实例:Python requests调用Web API完整示例

Phi-3-mini-4k-instruct-gguf代码实例&#xff1a;Python requests调用Web API完整示例 1. 模型简介 Phi-3-mini-4k-instruct-gguf是微软Phi-3系列中的轻量级文本生成模型GGUF版本&#xff0c;特别适合问答、文本改写、摘要整理和简短创作等场景。这个经过优化的版本可以直接…...

保姆级教程:用Python+OpenCV搞定汽车360全景拼接(附C++移植思路)

从零构建汽车360全景系统&#xff1a;PythonOpenCV实战与C工程化指南 当你第一次坐上驾驶座&#xff0c;启动车辆时&#xff0c;中控屏上突然展现出车辆周围无死角的鸟瞰视图——这就是现代汽车360全景系统带来的神奇体验。作为提升驾驶安全性和便利性的关键技术&#xff0c;它…...

用ZYNQ PS-SPI给Flash测个速:华邦W25Q80在25MHz时钟下的真实读写性能报告

ZYNQ PS-SPI Flash性能深度评测&#xff1a;华邦W25Q80在25MHz时钟下的极限挖掘 当我们需要在嵌入式系统中选择一款Flash存储器时&#xff0c;数据手册上的理论参数往往无法反映真实应用场景下的性能表现。本文将基于Xilinx ZYNQ平台的PS-SPI接口&#xff0c;对华邦W25Q80 Flas…...

从RAG到Agentic RAG 的进化之路

何为Agentic RAG? RAG系统, 为大模型补充了数据, 无论是实时数据还是私域数据. Agentic RAG系统, 更近一步, 为RAG系统添加了Agent的智能, 让AI不光只作用在查询这个阶段, 而是充分利用, Agent的计划(Plan), 自省(reflect), 工具调用(tools use), 编排(orchestrate)等等能力,…...

LumiPixel Canvas Quest教育应用:生成历史人物或文学角色形象辅助教学

LumiPixel Canvas Quest教育应用&#xff1a;生成历史人物或文学角色形象辅助教学 1. 教学场景中的视觉化挑战 历史课本上密密麻麻的文字描述和语文教材中抽象的人物描写&#xff0c;常常让学生难以形成直观印象。当讲到"秦始皇统一六国"时&#xff0c;学生脑海中可…...

如何用MusicFree插件打造你的专属音乐播放器:终极免费指南

如何用MusicFree插件打造你的专属音乐播放器&#xff1a;终极免费指南 【免费下载链接】MusicFreePlugins MusicFree播放插件 项目地址: https://gitcode.com/gh_mirrors/mu/MusicFreePlugins MusicFree插件是一个开源的音乐播放器扩展系统&#xff0c;它允许你将多个音…...