深入浅出排序算法之希尔排序
目录
1. 原理
2. 代码实现
3. 性能分析
1. 原理
希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。
(1)希尔排序是对直接插入排序的优化。
(2)当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
2. 代码实现
//希尔排序public static void shellSort(int[] array){int gap = array.length;while(gap > 1){shell(array,gap);gap /= 2;//增量是多少都可以,随便小伙伴们写}shell(array,1);}//有增量的直接插入排序//不是一组希尔排序全部排完,是间隔性的,可能是第一组先插一个,第二组再插一个,第一组再插……private static void shell(int[] array,int gap){for(int i = gap;i < array.length;i++){int tmp = array[i];int j = i - gap;for(;j >= 0;j -= gap){if(array[j] > array[j+gap]){array[j + gap] = array[j];}else{break;}}array[j + gap] = tmp;}}public static void main(String[] args) {int[] arr = {3,1,2,4,5};Sort.shellSort(arr);for (int x : arr) {System.out.print(x + " ");}}
3. 性能分析
时间复杂度 | 空间复杂度 | ||
最好 | 平均 | 最坏 | |
O(N) | O(N^1.3) | O(N^2) | O(1) |
数据有序 | 难以构造出来 |
public static void main(String[] args) {int[] arr2 = new int[10000];Test.createArray2(arr2);long s2 = System.currentTimeMillis();Sort.insertSort(arr2);long e2 = System.currentTimeMillis();System.out.println("直接插入排序的数组逆序的情况:"+(e2 - s2));int[] arr1 = new int[10000];Test.createArray2(arr1);long s1 = System.currentTimeMillis();Sort.shellSort(arr2);long e1 = System.currentTimeMillis();System.out.println("希尔排序的数组逆序的情况:"+(e1 - s1));}
稳定性:不稳定。
由于增量不同,可能导致本来在后面的元素跑到前面去!
相关文章:

深入浅出排序算法之希尔排序
目录 1. 原理 2. 代码实现 3. 性能分析 1. 原理 希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后…...
close excel by keyword 根据关键字关闭 excel 窗口 xlwings 方式实现
根据标题关键字关闭 workbook,如果没有打开的 workbook 则退出 excel xlwings 方式实现 更方便快捷 def close_excel_by_keyword(keyword):if ~$ in keyword:returnapp xw.apps.activefor workbook in app.books:if keyword in workbook.name:workbook.close()fi…...

LIO-SAM算法解析
文章目录 简介算法概述1.点云去畸变1.1 主要功能1.2 主要流程 2.特征提取3.IMU预积分4.地图优化5.算法评估 简介 LIO-SAM在lego-loam的基础上新增了对IMU和GPS的紧耦合,采用一个因子图对位姿进行优化,包括IMU因子,激光里程计因子,…...
vscode 提升小程序开发效率的必备插件与工具
1,微信小程序开发助手(WeChat Snippet):提供了小程序代码片段、模板和快速生成页面的功能,加快了开发速度。 2,小程序助手(Minapp):提供了小程序项目创建、编译、预览和…...
第五章单元测试
一、学习目的与要求 本章对单元测试进行了详细的介绍。通过本章的学习,应掌握单元测试的概念,了解单元测试的误区,掌握单元测试的策略、分析方法和用例设计方法。 二、考核知识点与考核目标 (一)单元测试的概念&#…...

【JAVA基础】多线程与线程池
多线程与线程池 文章目录 多线程与线程池1. 相关概念1.1 线程调度1.2 守护线程 2. 生命周期3. 同步机制/同步锁3.1 synchronized3.2 lock3.3 synchronized 与 Lock 的对比 4. 死锁5. 线程通信5.1 线程间的通信5.2 等待唤醒机制5.3 举例5.4 调用 wait 和 notify 需注意的细节5.5…...

HCIA数据通信——交换机(Vlan间的通信与安全)
前言 之前的提到了交换机的概念和实验。不过交换机的一些功能还没有说完,我们的实验也仅仅是阻止相同地址段的IP地址互通,也没有用到子接口和路由器。显然,那样的配置过于简单。 端口安全 Port Security(端口安全)的功…...

Linux shell编程学习笔记16:bash中的关联数组
上一节我们探讨了普通的数组,即使用数字下标来索引数组中不同的元素的数组,也可以称之为索引数组。 相比纯粹的数字,字符串不仅能表明含义,也更便于记忆使用,于是就有了关联数组。 一、关联数组概述 bash 从4.0开始支…...
浏览器是怎么执行JS的?——消息队列与事件循环
看完渡一的课后,感觉这块内容确实非常重要,写 JS 的连 JS 的执行原理都不知道可不行。 事件循环 在写 JS 的时候,你有没有想过 JS 是按照什么顺序执行的?浏览器是怎么执行 JS 代码的?为什么有时候代码没有按照我们认为…...

IMU预积分的过程详解
一、IMU和相机数据融合保证位姿的有效性: 当运动过快时,相机会出现运动模糊,或者两帧之间重叠区域太少以至于无法进行特征匹配,所以纯视觉SLAM对快速的运动很敏感。而有了IMU,即使在相机数据无效的那段时间内ÿ…...
TypeScript中的类型运算符
类型运算符 1. keyof运算符 1. 简介 是一个单目运算符,接受一个对象类型作为参数,返回该对象的所有键名组成的联合类型。 type MyObj {foo: number,bar: string, };type Keys keyof MyObj; // foo|bar这个例子keyof MyObj返回MyObj的所有键名组成的…...

【蓝桥杯选拔赛真题03】C++输出字母Y 青少年组蓝桥杯C++选拔赛真题 STEMA比赛真题解析
目录 C/C++输出字母Y 一、题目要求 1、编程实现 2、输入输出 二、算法分析...
redis搭建集群-多实例快速搭建
1.基础的redis.conf的配置 # Redis configuration file example. # # Note that in order to read the configuration file, Redis must be # started with the file path as first argument: # # ./redis-server /path/to/redis.conf# Note on units: when memory size is ne…...

为什么进行压力测试? 有哪些方法?
在信息技术飞速发展的今天,软件系统的性能已经成为了用户满意度的决定性因素之一。而要确保一个系统在实际使用中能够稳定可靠地运行,压力测试就显得尤为关键。本文将深入探讨什么是压力测试,为什么它是如此重要,以及一些常见的压…...

Java开发者必备:支付宝沙箱环境支付远程调试指南
🔥博客主页: 小羊失眠啦. 🔖系列专栏: C语言、Linux、Cpolar ❤️感谢大家点赞👍收藏⭐评论✍️ 文章目录 前言1. 下载当面付demo2. 修改配置文件3. 打包成web服务4. 局域网测试5. 内网穿透6. 测试公网访问7. 配置二级…...

基于STM32温湿度传感器采集报警系统设计
**单片机设计介绍,1648【毕设课设】基于STM32温湿度传感器采集报警系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序程序 六、 文章目录 一 概要 这次的设计主要是通过读取DHT11和HCSR04的数值,(Proteus的传感器…...

檢測項目簡體字
某些項目可能要求代碼中不允許使用簡體字 安裝stcheck檢查 yarn add stcheck --dev在項目根目錄創建 st.config.json 文件 {"patterns": ["./**/*.(ts|js|tsx|jsx|vue|html)","!**/node_modules/**","!.git/**"],"gitignore&q…...

适用于嵌入式arm的ffmpeg编解码
在嵌入式arm应用开发中,经常会遇到需要处理视频的情况,这时候就需要强大的开源工具ffmpeg出马了。 这里可以下载到各个版本的ffmpeg。 ffmpeg各版本https://www.videohelp.com/software/ffmpeg/old-versions 现在ffmpeg更新较频繁,如…...
nlp与知识图谱代码解读_词嵌入
目录 词嵌入简单原理代码案例解读专业原理介绍场景 词嵌入 简单原理 可以使用一些比喻和生活中的例子: 老师: 你们还记得玩乐高积木的时候,每个积木块代表了一个特定的事物或形状吗?现在,想象一下,每个词…...
HarmonyOS 音频通话开发指导
常用的音频通话模式包括 VOIP 通话和蜂窝通话。 ● VOIP 通话:VOIP(Voice over Internet Protocol)通话是指基于互联网协议(IP)进行通讯的一种语音通话技术。VOIP 通话会将通话信息打包成数据包,通过网络进…...

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...

九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...

FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...

mac:大模型系列测试
0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何,是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试,是可以跑通文章里面的代码。训练速度也是很快的。 注意…...

rknn toolkit2搭建和推理
安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 ,不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源(最常用) conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...