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

深入浅出排序算法之希尔排序

目录

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. 原理 希尔排序法又称缩小增量法。希尔排序法的基本思想是&#xff1a;先选定一个整数&#xff0c;把待排序文件中所有记录分成个组&#xff0c;所有距离为的记录分在同一组内&#xff0c;并对每一组内的记录进行排序。然后&#xf…...

close excel by keyword 根据关键字关闭 excel 窗口 xlwings 方式实现

根据标题关键字关闭 workbook&#xff0c;如果没有打开的 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的紧耦合&#xff0c;采用一个因子图对位姿进行优化&#xff0c;包括IMU因子&#xff0c;激光里程计因子&#xff0c…...

vscode 提升小程序开发效率的必备插件与工具

1&#xff0c;微信小程序开发助手&#xff08;WeChat Snippet&#xff09;&#xff1a;提供了小程序代码片段、模板和快速生成页面的功能&#xff0c;加快了开发速度。 2&#xff0c;小程序助手&#xff08;Minapp&#xff09;&#xff1a;提供了小程序项目创建、编译、预览和…...

第五章单元测试

一、学习目的与要求 本章对单元测试进行了详细的介绍。通过本章的学习&#xff0c;应掌握单元测试的概念&#xff0c;了解单元测试的误区&#xff0c;掌握单元测试的策略、分析方法和用例设计方法。 二、考核知识点与考核目标 &#xff08;一&#xff09;单元测试的概念&#…...

【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间的通信与安全)

前言 之前的提到了交换机的概念和实验。不过交换机的一些功能还没有说完&#xff0c;我们的实验也仅仅是阻止相同地址段的IP地址互通&#xff0c;也没有用到子接口和路由器。显然&#xff0c;那样的配置过于简单。 端口安全 Port Security&#xff08;端口安全&#xff09;的功…...

Linux shell编程学习笔记16:bash中的关联数组

上一节我们探讨了普通的数组&#xff0c;即使用数字下标来索引数组中不同的元素的数组&#xff0c;也可以称之为索引数组。 相比纯粹的数字&#xff0c;字符串不仅能表明含义&#xff0c;也更便于记忆使用&#xff0c;于是就有了关联数组。 一、关联数组概述 bash 从4.0开始支…...

浏览器是怎么执行JS的?——消息队列与事件循环

看完渡一的课后&#xff0c;感觉这块内容确实非常重要&#xff0c;写 JS 的连 JS 的执行原理都不知道可不行。 事件循环 在写 JS 的时候&#xff0c;你有没有想过 JS 是按照什么顺序执行的&#xff1f;浏览器是怎么执行 JS 代码的&#xff1f;为什么有时候代码没有按照我们认为…...

IMU预积分的过程详解

一、IMU和相机数据融合保证位姿的有效性&#xff1a; 当运动过快时&#xff0c;相机会出现运动模糊&#xff0c;或者两帧之间重叠区域太少以至于无法进行特征匹配&#xff0c;所以纯视觉SLAM对快速的运动很敏感。而有了IMU&#xff0c;即使在相机数据无效的那段时间内&#xff…...

TypeScript中的类型运算符

类型运算符 1. keyof运算符 1. 简介 是一个单目运算符&#xff0c;接受一个对象类型作为参数&#xff0c;返回该对象的所有键名组成的联合类型。 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…...

为什么进行压力测试? 有哪些方法?

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

Java开发者必备:支付宝沙箱环境支付远程调试指南

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f516;系列专栏&#xff1a; C语言、Linux、Cpolar ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 文章目录 前言1. 下载当面付demo2. 修改配置文件3. 打包成web服务4. 局域网测试5. 内网穿透6. 测试公网访问7. 配置二级…...

基于STM32温湿度传感器采集报警系统设计

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

檢測項目簡體字

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

适用于嵌入式arm的ffmpeg编解码

在嵌入式arm应用开发中&#xff0c;经常会遇到需要处理视频的情况&#xff0c;这时候就需要强大的开源工具ffmpeg出马了。 这里可以下载到各个版本的ffmpeg。 ffmpeg各版本https://www.videohelp.com/software/ffmpeg/old-versions 现在ffmpeg更新较频繁&#xff0c;如…...

nlp与知识图谱代码解读_词嵌入

目录 词嵌入简单原理代码案例解读专业原理介绍场景 词嵌入 简单原理 可以使用一些比喻和生活中的例子&#xff1a; 老师&#xff1a; 你们还记得玩乐高积木的时候&#xff0c;每个积木块代表了一个特定的事物或形状吗&#xff1f;现在&#xff0c;想象一下&#xff0c;每个词…...

HarmonyOS 音频通话开发指导

常用的音频通话模式包括 VOIP 通话和蜂窝通话。 ● VOIP 通话&#xff1a;VOIP&#xff08;Voice over Internet Protocol&#xff09;通话是指基于互联网协议&#xff08;IP&#xff09;进行通讯的一种语音通话技术。VOIP 通话会将通话信息打包成数据包&#xff0c;通过网络进…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

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

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

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…...

基于 TAPD 进行项目管理

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

FFmpeg:Windows系统小白安装及其使用

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

mac:大模型系列测试

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

rknn toolkit2搭建和推理

安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 &#xff0c;不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源&#xff08;最常用&#xff09; conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...