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

希尔排序【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. 概念 希尔排序也是一种插入排序&#xff0c;它是简单插入排序经过改进之后的一个更高效的版本&#xff0c;也称为缩小增量排序。希尔排序在数组中采用跳跃式分组的策略&#xff0c;通过某个增量将数组元素划分为若干组&#xff0c;然后分…...

互联网发展历程:从布线到无线,AC/AP的崭新时代

互联网的发展&#xff0c;一直在追求更便捷、更灵活的连接方式。在网络的早期&#xff0c;布线问题常常让人头疼。一项革命性的技术应运而生&#xff0c;那就是“无线AC/AP”。 布线问题的烦恼&#xff1a;繁琐的布线 早期网络的布线工作常常耗费时间和精力&#xff0c;尤其在大…...

Vue3 Axios网络请求简单应用

cd 到项目 安装Axios&#xff1a;cnpm install --save axios post传递参数 需要安装querystring 用于转换参数格式&#xff1a;cnpm install --save querystring 运行示例&#xff1a; 后台接口&#xff1a; GetTestData.java package com.csdnts.api;import java.io.IOExce…...

day-18 代码随想录算法训练营(19)二叉树 part05

513.找树左下角的值 思路一&#xff1a;层序遍历&#xff0c;每一层判断是不是最后一层&#xff0c;是的话直接返回第一个; 如何判断是不是最后一层呢&#xff0c;首先队列头部&#xff0c;其次记录左右子节点都没有的节点数是不是等于que.size()&#xff1b;或…...

【数据结构OJ题】移除链表元素

原题链接&#xff1a;https://leetcode.cn/problems/remove-linked-list-elements/description/ 1. 题目描述 2. 思路分析 我们可以定义一个结构体指针变量cur&#xff0c;让cur一开始指向头结点&#xff0c;同时定义一个结构体指针prev&#xff0c;令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用法&#xff1a;1、创建Optional对象&#xff1a;1.1 使用of()方法&#xff1a;1.2 使用ofNullable()方法&#xff1a;1.3 使用empty()方法&#xff1a; 2、判断Optional是否包含值&#xff1a;2.1 使用isPresent()方法&#xff1a; 3、获…...

LinuxPTP时间同步

参考文献&#xff1a; http://linuxptp.sourceforge.net/ 0、硬件支持 查看网卡是否支持软硬件时间戳&#xff1a; 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组队学习&#xff0c;在这个群除我佬的时代&#xff0c;写一下blog记录学习过程。 参考资源&#xff1a; 学习项目github&#xff1a;https://github.com/Joe-2002/sweettalk-django4.2 队长博客&#xff1a…...

00 - 环境配置

查看所有文章链接&#xff1a;&#xff08;更新中&#xff09;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)

两个模型比较&#xff0c;与第一个模型相比&#xff0c;NRI&#xff08;重新分对的 - 重新分错的&#xff09;/总人数。IDI&#xff08;新模型患者平均预测概率-旧模型患者平均预测概率&#xff09;-&#xff08;新模型非患者平均预测概率-旧模型非患者平均预测概率&#xff09…...

【面试总结】八股①

目录 数据库缓存穿透是什么常见的sql调优方法有哪些使用表的别名为什么能优化查询性能MySQL事务特性是哪些事务隔离级别有哪些 Java基础StringBuffer和StringBuilder的区别String直接引号新建和new String新建的区别Java中继承和实现的各种关系 消息队列Redis计算机常识缓冲击穿…...

AI绘画 | 一文学会Midjourney绘画,创作自己的AI作品(快速入门+参数介绍)

一、生成第一个AI图片 首先&#xff0c;生成将中文描述词翻译成英文 然后在输入端输入&#xff1a;/imagine prompt:Bravely running boy in Q version, cute head portrait 最后&#xff0c;稍等一会即可输出效果 说明&#xff1a; 下面的U1、U2、U3、U4代表的第一张、第二张…...

MongoDB 数据库详细介绍

MongoDB 数据库详细介绍 MongoDB&#xff08;来自“Humongous”&#xff0c;意为巨大的&#xff09;是一个开源、高性能、无模式&#xff08;NoSQL&#xff09;、文档导向的分布式数据库。它以其灵活性、可扩展性和强大的查询功能而闻名于世。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:开发环境与原理图的熟悉

作为一名大学生&#xff0c;学习单片机有一段时间了&#xff0c;也接触过嵌入式ARM的开发&#xff0c;但从未使用以及接触过STM32C8T6大开发使用&#xff0c;于是从今日开始&#xff0c;将学习使用它~ 本文介绍STM32C8T6最小系统开发环境搭建注意问题&#xff0c;STM32C8T6单片…...

【Linux命令详解 | ps命令】 ps命令用于显示当前系统中运行的进程列表,帮助监控系统状态。

文章标题 简介一&#xff0c;参数列表二&#xff0c;使用介绍1. 基本用法2. 显示所有进程3. 显示进程详细信息4. 根据CPU使用率排序5. 查找特定进程6. 显示特定用户的进程7. 显示进程内存占用8. 查看进程树9. 实时监控进程10. 查看特定进程的详细信息11. 查看特定用户的进程统计…...

“超越传统的HTTP请求:深度解析Axios,打造前端开发的终极利器“

解锁前端开发的新境界 - 深入探索Axios&#xff0c;构建卓越的互联网应用 在当今数字化世界中&#xff0c;互联网应用的需求日益增长&#xff0c;而无论是大型企业还是初创公司&#xff0c;都需要一个强大而可靠的工具来处理与后端服务器之间的通信。这就是Axios的光辉时刻。作…...

【Tomcat】tomcat的多实例和动静分离

多实例&#xff1a; 在一台服务器上有多台Tomcat&#xff1b;就算是多实例 安装telnet服务&#xff0c;可以用来测试端口通信是否正常 yum -y install telnettelnet 192.168.220.112 80 tomcat的日志文件 cd /usr/local/tomcat/logsvim catalina.out Tomcat多实例部署&…...

Python爬虫IP代理池的建立和使用

写在前面 建立Python爬虫IP代理池可以提高爬虫的稳定性和效率&#xff0c;可以有效避免IP被封锁或限制访问等问题。 下面是建立Python爬虫IP代理池的详细步骤和代码实现&#xff1a; 1. 获取代理IP 我们可以从一些代理IP网站上获取免费或付费的代理IP&#xff0c;或者自己租…...

CogVideoX-2b完整功能测评:一键部署+本地渲染+隐私安全全解析

CogVideoX-2b完整功能测评&#xff1a;一键部署本地渲染隐私安全全解析 1. 为什么选择本地化视频生成工具 在内容创作领域&#xff0c;视频制作一直是门槛较高的技能。传统视频制作需要专业的剪辑软件、大量的素材积累以及复杂的时间线操作。而云端视频生成服务虽然降低了技术…...

M2LOrder模型在STM32项目中的潜在应用:边缘设备情绪反馈

M2LOrder模型在STM32项目中的潜在应用&#xff1a;边缘设备情绪反馈 最近在捣鼓一个基于STM32的智能硬件项目&#xff0c;想给它加点“人情味”。比如&#xff0c;当用户对它说话时&#xff0c;它能感知到用户的情绪是开心还是沮丧&#xff0c;并给出更贴切的反馈。这听起来很…...

GTX1650也能跑!Windows11上OLLAMA+AnythingLLM本地部署Llama3保姆级教程

GTX1650也能跑&#xff01;Windows11上OLLAMAAnythingLLM本地部署Llama3保姆级教程 老旧硬件也能玩转大模型&#xff1f;当GTX1650这样的入门级显卡遇上Llama3这类前沿AI模型&#xff0c;很多人第一反应可能是"跑不动"。但经过实测&#xff0c;只要合理配置和优化&am…...

从LC谐振到信号振铃:用Multisim仿真带你理解PCB上的阻尼振荡

从LC谐振到信号振铃&#xff1a;用Multisim仿真揭示PCB阻尼振荡的本质 1. 振铃现象&#xff1a;硬件工程师的"噩梦" 第一次在示波器上看到信号边沿那些诡异的振荡波形时&#xff0c;我差点以为自己的电路板被某种神秘力量干扰了。这种被称为"振铃"的现象…...

Cosmos-Reason1-7B部署教程:Docker镜像免配置+7860端口快速启用

Cosmos-Reason1-7B部署教程&#xff1a;Docker镜像免配置7860端口快速启用 1. 项目概述 Cosmos-Reason1-7B是NVIDIA推出的7B参数多模态视觉语言模型(VLM)&#xff0c;专注于物理理解和思维链推理能力。作为Cosmos世界基础模型平台的核心组件&#xff0c;它能够处理图像和视频…...

阿里开源Z-Image镜像体验:ComfyUI可视化生成汉服美女实战

阿里开源Z-Image镜像体验&#xff1a;ComfyUI可视化生成汉服美女实战 1. 开篇&#xff1a;当汉服遇见AI绘画 想象一下&#xff0c;你只需要输入"一位穿着汉服的中国女性站在樱花树下"&#xff0c;AI就能在几秒钟内生成一张细节精致的写实风格图像。这不再是科幻场景…...

图像处理和深度学习笔记[特殊字符](一)

AI生命周期&#xff1a;数据准备 → 模型训练 → 模型转换 → 部署 → 监控↑ 算法工程师关注 ↑ ↓ 你将专注于此 ↓机器学习开发流程数据收集数据预处理特征提取 数据预处理和 特征提取&#xff08;其实就是数据清洗和转换&#xff09; 比较耗时耗力清洗和特征工程模型构…...

3个核心技巧:Element Plus效率提升与性能优化指南

3个核心技巧&#xff1a;Element Plus效率提升与性能优化指南 【免费下载链接】element-plus &#x1f389; A Vue.js 3 UI Library made by Element team 项目地址: https://gitcode.com/GitHub_Trending/el/element-plus 副标题&#xff1a;面向初中级开发者的Element…...

3步掌握AI模型训练:让新手也能玩转个性化Stable Diffusion模型

3步掌握AI模型训练&#xff1a;让新手也能玩转个性化Stable Diffusion模型 【免费下载链接】sd-trainer 项目地址: https://gitcode.com/gh_mirrors/sd/sd-trainer 在数字创意领域&#xff0c;AI绘画模型训练曾是一道高不可攀的技术门槛。设计师面对复杂的代码配置望而…...

2026前端面试题

1.vue的通信方式Vue组件通信方式根据组件间的关系&#xff08;父子、兄弟、跨级、任意组件&#xff09;可分为多种方案。一、父子组件通信props&#xff08;父-子&#xff09;父组件通过属性向子组件传递数据&#xff0c;子组件通过defineProps接收<!-- 父组件 --> <C…...