希尔排序【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;
                //控制待比较元素的位置,初始值为待插入元素的位置减去增量值,即index
                while (index >= 0 && insertVal < arr[index]) {
                    //当前待比较元素向后移一位,这里的一位就是step长度
                    arr[index + step] = arr[index];
                    //指针向左挪动一位,继续跟下一个元素作比较
                    index -= step;
                }
                //退出循环后后,将待插入元素插入到index的下一位
                arr[index + step] = insertVal;
            }
        }
        return arr;
    }
}

在这里插入图片描述

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

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

相关文章

docker私有仓库harbor

一、安装docker-compose yum install docker-compose -y 二、下载harbor安装包 tar -xf harbor-online-installer-v2.1.0.tgz cp harbor.yml.tmpl harbor.yml 三、修改harbor配置 [rootharbor ~]# vim harbor.ymlhostname: "修改为本机ip" harboradminpassword:…

Python文件操作与输入输出:从基础到高级应用

文章目录 &#x1f340;引言&#x1f340;文件操作基础&#x1f340;上下文管理器与文件自动关闭&#x1f340;文件的迭代与逐行读取&#x1f340;文件的其他常见操作&#x1f340;输入输出基础&#x1f340; 文件输入输出&#x1f340;格式化输出&#x1f340;高级文件操作&am…

cesium学习记录08-鼠标绘制多边形

上一篇学习了实体的一些基础知识&#xff0c;这一篇来学习鼠标绘制实体多边形的实现 一、方法一&#xff1a; 1&#xff0c;结果显示 贴地&#xff1a; 不贴地&#xff1a; 2&#xff0c;方法全部代码&#xff1a; 主方法&#xff1a; /*** 绘制多边形* param {Object} op…

UI设计师个人工作总结范文

UI设计师个人工作总结范文篇一 感受到了领导们“海纳百川”的胸襟&#xff0c;感受到了作为广告人“不经历风雨&#xff0c;怎能见彩虹”的豪气&#xff0c;也体会到了重庆广告从业人员作为拓荒者的艰难和坚定(就目前国内广告业而言&#xff0c;我认为重庆广告业尚在发展阶段并…

实战:工作中对并发问题的处理 | 京东物流技术团队

1. 问题背景 问题发生在快递分拣的流程中&#xff0c;我尽可能将业务背景简化&#xff0c;让大家只关注并发问题本身。 分拣业务针对每个快递包裹都会生成一个任务&#xff0c;我们称它为 task。task 中有两个字段需要关注&#xff0c;一个是分拣中发生的异常&#xff08;exp…

本地跑Mapreduce程序的相关配置

本地跑MapReduce程序需要配置的代码 为了在本地运行MapReduce程序&#xff0c;需要加如下的东西 在项目中创建一个如图所示的包&#xff1a;org.apache.hadoop.io.nativeio&#xff0c;并在该包下面创建一个名为&#xff1a;NativeIO的类&#xff08;注意&#xff1a;名字不能…

RabbitMQ:可靠消息传递的强大消息中间件

消息中间件在现代分布式系统中起着关键作用&#xff0c;它们提供了一种可靠且高效的方法来进行异步通信和解耦。在这篇博客中&#xff0c;我们将重点介绍 RabbitMQ&#xff0c;一个广泛使用的开源消息中间件。我们将深入探讨 RabbitMQ 的特性、工作原理以及如何在应用程序中使用…

第三章 图论 No.11二分图,匈牙利算法与点覆盖

文章目录 二分染色&#xff1a;257. 关押罪犯增广路径372. 棋盘覆盖 最小点覆盖376. 机器任务 最大独立集378. 骑士放置 最小路径点覆盖 二分染色&#xff1a;257. 关押罪犯 257. 关押罪犯 - AcWing题库 最大最小问题&#xff0c;一眼二分 答案的范围在 [ 1 , 1 e 9 ] [1, 1…

ReactDOM模块react-dom/client没有默认导出报错解决办法

import ReactDOM 模块“"E:/Dpandata/Shbank/rt-pro/node_modules/.pnpm/registry.npmmirror.comtypesreact-dom18.2.7/node_modules/types/react-dom/client"”没有默认导出。 解决办法 只需要在tsconfig.json里面添加配置 "esModuleInterop": true 即…

关于跨国文件传输需要了解的5点

我们在为企业客户解决各种IT问题的多年经验中&#xff0c;发现跨国文件传输一直是许多企业IT部门的难题。提升数据传输效率只是跨国文件传输的一个方面&#xff0c;还有更多的因素困扰着一些大型企业、集团。 作为企业文件传输的领先品牌&#xff0c;镭速(私有化部署方案&…

VectorStyler for Mac: 让你的创意无限绽放的全新设计工具

VectorStyler for Mac是一款专为Mac用户打造的矢量设计工具&#xff0c;它结合了功能强大的矢量编辑器和创意无限的样式编辑器&#xff0c;让你的创意无限绽放。 VectorStyler for Mac拥有直观简洁的用户界面&#xff0c;让你能够轻松上手。它提供了丰富的矢量绘图工具&#x…

flutter 常见的状态管理器

flutter 常见的状态管理器 前言一、Provider二、Bloc三、Redux四、GetX总结 前言 当我们构建复杂的移动应用时&#xff0c;有效的状态管理是至关重要的&#xff0c;因为应用的不同部分可能需要共享数据、相应用户交互并保持一致的状态。Flutter 中有多种状态管理解决方案&#…

机器学习深度学习——seq2seq实现机器翻译(数据集处理)

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位即将上大四&#xff0c;正专攻机器学习的保研er &#x1f30c;上期文章&#xff1a;机器学习&&深度学习——从编码器-解码器架构到seq2seq&#xff08;机器翻译&#xff09; &#x1f4da;订阅专栏&#xff1a;机…

三菱plc 工程的系统参数fCPu参数与 可编程控制器的系统参数/CPu参数不一致。

三菱plc 工程的系统参数fCPu参数与 可编程控制器的系 统参数/CPu参数不一致。

掌握Python的X篇_30_使用python解析网页HTML

本篇将会介绍beutifulsoup4模块&#xff0c;可以用于网络爬虫、解析HTML和XML&#xff0c;对于没有接触过前端&#xff0c;不了解HTML是如何工作的&#xff0c;需要先解释一下什么事HTML。 1. HTML 网页中的各种布局等的背后都是非常简单的纯文本格式&#xff0c;那种格式称为…

Android的学习系列之Android Studio Setup安装

Android的学习系列之Android Studio Setup安装 [TOC](Android的学习系列之Android Studio Setup安装) 前言Android平台搭建总结 前言 还是项目需要&#xff0c;暂时搭建安卓的运行平台。 Android平台搭建 安装包 双击安装包&#xff0c;进入安装。 下一步 根据自己需求&a…

(7)(7.1) 使用航点和事件规划任务

文章目录 前言 7.1.1 设置Home位置 7.1.2 视频&#xff1a;制作并保存多路点任务 7.1.3 视频&#xff1a;加载已保存的多航点任务 7.1.4 使用说明 7.1.5 提示 7.1.6 自动网格 7.1.7 任务指令 7.1.8 任务结束 7.1.9 任务重置 7.1.10 MIS_OPTIONS 7.1.11 任务再出发 …

客户跟进轻松搞定:推荐一款功能全面的客户跟进软件

阅读本文您可以了解&#xff1a;1、如何选择客户跟进软件&#xff1b;2、简单好用的客户跟进软件推荐 客户跟进是建立并维护良好客户关系的关键步骤。通过定期的跟进&#xff0c;可以及时了解客户的需求和反馈&#xff0c;解决问题&#xff0c;提供支持&#xff0c;从而增强客…

ubuntu18.04下配置muduoC++11环境

1.安装muduo依赖的编译工具及库 Cmake sudo apt-get install cmakeBoost sudo apt-get install libboost-dev libboost-test-devcurl、c-ares DNS、google protobuf sudo apt-get install libcurl4-openssl-dev libc-ares-dev sudo apt-get install protobuf-compiler libp…

你知道什么是Curriculum Training模型吗

随着深度学习技术的飞速发展&#xff0c;研究人员在不断探索新的训练方法和策略&#xff0c;以提高模型的性能和泛化能力。其中&#xff0c;Curriculum Training&#xff08;课程学习&#xff09;模型作为一种前沿的训练方法&#xff0c;引起了广泛的关注和研究。本文将深入探讨…