当前位置: 首页 > 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 比较…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...