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

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...