希尔排序【Java算法】
文章目录
- 1. 概念
- 2. 思路
- 3. 代码实现
1. 概念
希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组进行插入排序操作,直至增量为1。
推荐一个B站六分钟的视频,PPT动画做的非常好,清晰明了。

2. 思路
① 希尔排序采用跳跃式的分组方式,什么是跳跃式?也就是说同一组内的成员在原序列中实际上是互相隔着一段距离的,它们被迫抽出来组成一队,内部采用插入排序比较大小。它们互相隔着的距离是相等的,这个距离我们称它为增量,增量怎么确定?一般来说,初始增量值为序列长度的一半,接下来我们根据增量值计算分组,如下图增量为5,所以索引0跟索引5一组,索引1跟索引6一组 …,以此类推,序列被分成了五组;

② 分了组之后,组员内部要进行插入排序的,但是这里的插入排序步长其实并不是1,我们知道原本的插入排序是从右往左一步一步地比较大小并插入的,但是希尔排序是跳跃式分组的,虽然说你们被分到了同一个队伍里,但是不要忘记了,你们本身的索引并不相连,索引还是原来位置的索引,所以,在这里插入排序的时候,每一步的长度应该是增量的大小,除了步长不一样外,其它思路都不变;
③ 在第一轮排序完成之后,发现整体上序列的顺序有了一个大体的趋势,小的基本在左边,大的基本在右边,但这才是第一步还不算排好序;
④ 再开始下一轮排序,每一轮开始时的增量值都应是上一轮增量值的一半。原理还不变,外部分组,内部插入排序,什么时候不再分组,不再排序?增量值一直减半,总有一天它会减为1,到1的时候就是全体序列进行最基本的插入排序了,没错这是最后一步,所以终止条件就是增量值开始小于1,这时候的序列已经完全有序。
3. 代码实现
import java.util.Arrays;public class Test {public static void main(String[] args) {int[] arr = {2, 9, 3, 11, 7, 8, 4, 1, 6};int[] newArr = sort(arr);System.out.println(Arrays.toString(newArr));}public static int[] sort(int[] arr) {//控制增量值,初始值为序列长度的一半,每次减半,步长为0时停止for (int step = arr.length / 2; step > 0; step /= 2) {//控制待插入元素的位置,初始值为增量值for (int i = step; i < arr.length; i++) {//待插入元素int insertVal = arr[i];//待比较元素初始位置int index = i - step;//控制待比较元素的位置,初始值为待插入元素的位置减去增量值,即indexwhile (index >= 0 && insertVal < arr[index]) {//当前待比较元素向后移一位,这里的一位就是step长度arr[index + step] = arr[index];//指针向左挪动一位,继续跟下一个元素作比较index -= step;}//退出循环后后,将待插入元素插入到index的下一位arr[index + step] = insertVal;}}return arr;}
}

相关文章:
希尔排序【Java算法】
文章目录 1. 概念2. 思路3. 代码实现 1. 概念 希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分…...
互联网发展历程:从布线到无线,AC/AP的崭新时代
互联网的发展,一直在追求更便捷、更灵活的连接方式。在网络的早期,布线问题常常让人头疼。一项革命性的技术应运而生,那就是“无线AC/AP”。 布线问题的烦恼:繁琐的布线 早期网络的布线工作常常耗费时间和精力,尤其在大…...
Vue3 Axios网络请求简单应用
cd 到项目 安装Axios:cnpm install --save axios post传递参数 需要安装querystring 用于转换参数格式:cnpm install --save querystring 运行示例: 后台接口: GetTestData.java package com.csdnts.api;import java.io.IOExce…...
day-18 代码随想录算法训练营(19)二叉树 part05
513.找树左下角的值 思路一:层序遍历,每一层判断是不是最后一层,是的话直接返回第一个; 如何判断是不是最后一层呢,首先队列头部,其次记录左右子节点都没有的节点数是不是等于que.size();或…...
【数据结构OJ题】移除链表元素
原题链接:https://leetcode.cn/problems/remove-linked-list-elements/description/ 1. 题目描述 2. 思路分析 我们可以定义一个结构体指针变量cur,让cur一开始指向头结点,同时定义一个结构体指针prev,令prev初始化为空指针NULL…...
centos 安装 virtualbox
参考 https://phoenixnap.com/kb/how-to-install-virtualbox-centos-7 遇到 Gpg Keys Failue 这样解决 将 rpm 包下载到本地 –disablerepovirtualbox sudo yum --disablerepovirtualbox localinstall VirtualBox-7.0-7.0.10_158379_el7-1.x86_64 failure: repodata/repomd…...
Java8之Optional类的基本使用
文章目录 一、简介二、常见的Optional用法:1、创建Optional对象:1.1 使用of()方法:1.2 使用ofNullable()方法:1.3 使用empty()方法: 2、判断Optional是否包含值:2.1 使用isPresent()方法: 3、获…...
LinuxPTP时间同步
参考文献: http://linuxptp.sourceforge.net/ 0、硬件支持 查看网卡是否支持软硬件时间戳: sudo ethtool -T eno1 Time stamping parameters for eno1: Time stamping parameters for eno1: Capabilities: hardware-transmit (SOF_TIMESTAMPIN…...
【Django】Task1安装python环境及运行项目
【Django】Task1安装python环境及运行项目 写在最前 8月份Datawhale组队学习,在这个群除我佬的时代,写一下blog记录学习过程。 参考资源: 学习项目github:https://github.com/Joe-2002/sweettalk-django4.2 队长博客:…...
00 - 环境配置
查看所有文章链接:(更新中)GIT常用场景- 目录 文章目录 1. 环境说明2. 安装配置2.1 配置user信息2.2 config的三个作用域 3. 建git仓库3.1 把已有的项目代码纳入git管理3.2 新建的项目直接用git管理3.3 配置local的user和email3.4 优先级&…...
R语言实现计算净重新分类指数(NRI)和综合判别改善指数(IDI)
两个模型比较,与第一个模型相比,NRI(重新分对的 - 重新分错的)/总人数。IDI(新模型患者平均预测概率-旧模型患者平均预测概率)-(新模型非患者平均预测概率-旧模型非患者平均预测概率)…...
【面试总结】八股①
目录 数据库缓存穿透是什么常见的sql调优方法有哪些使用表的别名为什么能优化查询性能MySQL事务特性是哪些事务隔离级别有哪些 Java基础StringBuffer和StringBuilder的区别String直接引号新建和new String新建的区别Java中继承和实现的各种关系 消息队列Redis计算机常识缓冲击穿…...
AI绘画 | 一文学会Midjourney绘画,创作自己的AI作品(快速入门+参数介绍)
一、生成第一个AI图片 首先,生成将中文描述词翻译成英文 然后在输入端输入:/imagine prompt:Bravely running boy in Q version, cute head portrait 最后,稍等一会即可输出效果 说明: 下面的U1、U2、U3、U4代表的第一张、第二张…...
MongoDB 数据库详细介绍
MongoDB 数据库详细介绍 MongoDB(来自“Humongous”,意为巨大的)是一个开源、高性能、无模式(NoSQL)、文档导向的分布式数据库。它以其灵活性、可扩展性和强大的查询功能而闻名于世。MongoDB 使用 JSON 格式的文档来存…...
Qt在mac安装
先在app store下载好Xcode 打开Xcode 随便建个文件给它取个名字找个地方放提醒没建立git link,不用理他打开终端, 输入/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"...
STM32 F103C8T6学习笔记1:开发环境与原理图的熟悉
作为一名大学生,学习单片机有一段时间了,也接触过嵌入式ARM的开发,但从未使用以及接触过STM32C8T6大开发使用,于是从今日开始,将学习使用它~ 本文介绍STM32C8T6最小系统开发环境搭建注意问题,STM32C8T6单片…...
【Linux命令详解 | ps命令】 ps命令用于显示当前系统中运行的进程列表,帮助监控系统状态。
文章标题 简介一,参数列表二,使用介绍1. 基本用法2. 显示所有进程3. 显示进程详细信息4. 根据CPU使用率排序5. 查找特定进程6. 显示特定用户的进程7. 显示进程内存占用8. 查看进程树9. 实时监控进程10. 查看特定进程的详细信息11. 查看特定用户的进程统计…...
“超越传统的HTTP请求:深度解析Axios,打造前端开发的终极利器“
解锁前端开发的新境界 - 深入探索Axios,构建卓越的互联网应用 在当今数字化世界中,互联网应用的需求日益增长,而无论是大型企业还是初创公司,都需要一个强大而可靠的工具来处理与后端服务器之间的通信。这就是Axios的光辉时刻。作…...
【Tomcat】tomcat的多实例和动静分离
多实例: 在一台服务器上有多台Tomcat;就算是多实例 安装telnet服务,可以用来测试端口通信是否正常 yum -y install telnettelnet 192.168.220.112 80 tomcat的日志文件 cd /usr/local/tomcat/logsvim catalina.out Tomcat多实例部署&…...
Python爬虫IP代理池的建立和使用
写在前面 建立Python爬虫IP代理池可以提高爬虫的稳定性和效率,可以有效避免IP被封锁或限制访问等问题。 下面是建立Python爬虫IP代理池的详细步骤和代码实现: 1. 获取代理IP 我们可以从一些代理IP网站上获取免费或付费的代理IP,或者自己租…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...
Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...
零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
sshd代码修改banner
sshd服务连接之后会收到字符串: SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢? 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头,…...
