数据结构和算法-希尔排序（增量序列 算法实现 性能分析 稳定性）

文章目录

  • 希尔排序
    • 过程小结
    • 增量序列不是固定的
  • 算法实现
  • 算法性能分析
  • 稳定性
  • 小结

希尔排序

基本有序，就是存在有序的子序列
在这里插入图片描述
通过增量4得到各个子表
在这里插入图片描述
对各个子表分别进行插入排序
在这里插入图片描述
缩小增量，再除2，此时的子表
在这里插入图片描述
对各个子表插入排序
在这里插入图片描述
缩小增量，再除2
此时子表就是整个表，对整个表开始插入排序
在这里插入图片描述

过程小结

在这里插入图片描述

增量序列不是固定的

在这里插入图片描述

算法实现

对每个子表做插入排序时，开始直接从子表的第二个元素开始，此时第二个元素为d+1开始，遍历到n

然后对比，只不过都是按增量序列的差来对比对应位置。移动位置也需要按增量序列的差来移动

最后找到大于的了，需要将此时比对的元素位置加上增量
在这里插入图片描述

算法性能分析

不同增量序列，排序的趟数和每趟的比对次数不一样
最坏增量为1和插入排序一样
在这里插入图片描述

稳定性

因为需要增量d来找到元素位置，用链表实现比较麻烦，所以仅适用于顺序表
在这里插入图片描述

小结

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/295530.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

STC进阶开发（四）SPI协议、矩阵键盘、EEPROM

STC进阶开发（四）SPI协议、矩阵键盘、EEPROM

前言 这一期我们简单介绍一下SPI协议，然后我们学习一下矩阵键盘，了解EEPROM是干什么用的，话不多说，开整！ SPI协议 SPI（Serial Peripheral Interface）是一种同步串行通信协议，用于在…
阅读更多...
OJ刷题 第十七篇（）

OJ刷题 第十七篇（）

34005 - 汽水瓶（有意思） 时间限制 : 1 秒 内存限制 : 128 MB 有这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶，方…
阅读更多...
Python 测试框架 Pytest 入门

Python 测试框架 Pytest 入门

简介 pytest 是一个功能强大而易于使用的 Python 测试框架。它提供了简单的语法和灵活的功能，用于编写和组织测试代码。 1、简单易用：pytest 的语法简洁明了，使得编写测试用例更加直观和易于理解。它使用 assert 语句来验证预期结果&#x…
阅读更多...
SpringBoot内嵌的Tomcat启动过程以及请求

SpringBoot内嵌的Tomcat启动过程以及请求

1.springboot内嵌的tomcat的pom坐标 启动后可以看到tomcat版本为9.0.46 2.springboot 内嵌tomcat启动流程 点击进入SpringApplication.run()方法里面 看这次tomcat启动相关的核心代码refreshContext(context);刷新上下文方法 public ConfigurableApplicationContext run(Stri…
阅读更多...
银行卡号识别

银行卡号识别

导入库 from typing import Any, Union, Sequencefrom cv2.mat_wrapper import Mat from imutils import contours import numpy as np import argparse import imutils import cv2 import myutils设置参数 # 设置参数 from numpy import dtype, ndarray, genericap argpars…
阅读更多...
“巴渝工匠杯”2022年重庆市职业院校技能大赛（高职组）云计算样题

“巴渝工匠杯”2022年重庆市职业院校技能大赛（高职组）云计算样题

“巴渝工匠杯”2022年重庆市职业院校技能大赛（高职组）云计算样题 需要软件包环境可私信博主 【赛程名称】云计算赛项第一场次-私有云 某企业拟使用OpenStack搭建一个企业云平台，以实现资源池化弹性管理、企业应用集中管理、统一安全认证和授…
阅读更多...
Visual Studio 2022进行文件差异比较

Visual Studio 2022进行文件差异比较

前言 Visual Studio 2022在版本17.7.4中发布在解决方案资源管理器中比较文件的功能，通过使用此功能，可以轻松地查看两个文件之间的差异，包括添加、删除和修改的代码行。可以逐行查看差异，并根据需要手动调整和编辑文件内容以进行…
阅读更多...
易图讯便携式三维电子沙盘实战应用系统

易图讯便携式三维电子沙盘实战应用系统

便携式三维电子沙盘采用军工加固三防高性能笔记本，具有IP65级防尘防水防摔性能，以大数据、云计算、虚拟现实、物联网、AI等先进技术为支撑，支持高清卫星影像、DEM高程数据、矢量数据、三维模型、倾斜摄像、BIM、点云、城市白模、等高线、标高…
阅读更多...
数据结构学习 jz56数组中数字出现的次数

数据结构学习 jz56数组中数字出现的次数

关键词：位运算 异或性质 虽然有两道题，但是其实应该分成三个级别的题目。 题目一： 一个整型数组 sockets 里除 一个 数字之外，其他数字都出现了两次。 思路：异或的性质 复杂度计算： 时间复杂度O(n) 空…
阅读更多...
在Go语言中处理HTTP请求中的Cookie

在Go语言中处理HTTP请求中的Cookie

在Web开发中，Cookie是一种常用的技术，用于在客户端存储数据，并在随后的请求中发送回服务器。Go语言的标准库提供了强大的支持来处理HTTP请求中的Cookie。 首先，让我们了解如何在Go语言中设置Cookie。以下是一个简单的示例&#x…
阅读更多...
three.js场景设计器-小地图的视角参考功能

three.js场景设计器-小地图的视角参考功能

three.js实现场景方向的左上角小地图 思路 1&#xff1a;创建单独场景 2.添加辅助线 3.添加坐标轴的XYZ文字-使用sprite实现 4.旋转主视图时同步相机位置到小地图。 <template> <div ref"miniMapContainer" class"mini-map"></div>…
阅读更多...
Apache Commons Email在邮件发送中的应用

Apache Commons Email在邮件发送中的应用

第1章&#xff1a;简介 大家好&#xff0c;我是小黑&#xff0c;今天咱们聊聊Apache Commons Email这个库&#xff0c;它在发送邮件方面可谓是小而美的利器。Apache Commons Email基于JavaMail API&#xff0c;但它提供了更简洁、更易用的接口&#xff0c;让咱们在处理电子邮件…
阅读更多...
如果PostgreSQL有两层nginx代理，会发生什么事？

如果PostgreSQL有两层nginx代理，会发生什么事？

转载说明&#xff1a;如果您喜欢这篇文章并打算转载它&#xff0c;请私信作者取得授权。感谢您喜爱本文&#xff0c;请文明转载&#xff0c;谢谢。 1. 前言 PostgreSQL默认只能本机连接&#xff0c;若要在别的客户端远程连接pgsql&#xff0c;则需要修改配置文件pg_hba.conf&a…
阅读更多...
CommonJS 和 ES6 Module：一场模块规范的对决（下）

CommonJS 和 ES6 Module：一场模块规范的对决（下）

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…
阅读更多...
QML —— SwipeView、PageIndicator组合示例（附完整源码）

QML —— SwipeView、PageIndicator组合示例（附完整源码）

示例效果 介绍 SwipeView提供了一个基于滑动的导航模型，由一组页面组成。一次只能看到一个页面。用户可以通过横向滑动在页面之间导航。请注意，SwipeView本身是完全不可见的。建议将其与PageIndicator结合使用，以向用户提供有多个页面的视觉线索。 PageIndicator用于指示包含…
阅读更多...
UG装配-沿线运动

UG装配-沿线运动

如果希望图中圆柱销沿着槽运动&#xff0c;直接约束面是困难的&#xff0c;我们可以画出圆弧的中心线和圆柱销的中心点&#xff0c;约束点在线上&#xff0c;进行移动 需要注意的是&#xff0c;我们在零件中画点和线的时候&#xff0c;在装配体默认加载模型引用集的时候是无法显…
阅读更多...
生活中的物理3——神奇陷阱（随机倒下的抽屉柜门）

生活中的物理3——神奇陷阱（随机倒下的抽屉柜门）

1实验 材料&#xff1a;大自然&#xff08;风&#xff09;、抽屉门松掉的抽屉 实验 1、找一个大风的日子&#xff0c;打开窗户&#xff08;不要找下雨天&#xff0c;不然你会被你亲爱的嫲嫲KO&#xff09; 2、让风在抽屉面前刮过 3、你发现了什么&#xff1f;&#xff1f;&…
阅读更多...
南某人：从工厂到品牌的华丽转身！

南某人：从工厂到品牌的华丽转身！

南某人&#xff0c;这个名字在中国的市场上已经响当当&#xff0c;但你知道吗&#xff1f;这个品牌其实并没有自己的工厂和门店。那么&#xff0c;他们是如何做到年收入高达40亿的呢&#xff1f; 起初&#xff0c;南某人和许多中国品牌一样&#xff0c;从生产保暖内衣起家。然…
阅读更多...
傅里叶级数、傅里叶变换、小波变换、离散余弦变换的理解

傅里叶级数、傅里叶变换、小波变换、离散余弦变换的理解

目录 1. 傅里叶级数2.傅里叶变换 1. 傅里叶级数 功能&#xff1a;能把任意周期性函数展开成一系列正弦、余弦函数的和。 公式&#xff1a; f ( x ) a 0 2 ∑ n 1 ∞ ( a n cos ⁡ ( 2 π n x T ) b n sin ⁡ ( 2 π n x T ) ) 傅里叶系数 a n 2 T ∫ x 0 x 0 T f ( x )…
阅读更多...
机器学习（三） -- 特征工程（1）

机器学习（三） -- 特征工程（1）

系列文章目录 机器学习&#xff08;一&#xff09; -- 概述 机器学习&#xff08;二&#xff09; -- 数据预处理&#xff08;1-3&#xff09; 机器学习&#xff08;三&#xff09; -- 特征工程&#xff08;1-2&#xff09; 未完待续…… 目录 系列文章目录 前言 一、特征…
阅读更多...
最新文章

Copyright @ 2022~2023