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

八大排序算法--希尔排序(动图理解)

目录

希尔排序

概念

算法思路

动画演示

代码如下

复杂度分析

时间复杂度测试

运行结果

 完整代码

 创作不易,如果本篇博客对您有一定的帮助,大家记得留言+点赞哦。


希尔排序

概念

希尔排序是插入排序的一种,是对直接插入排序的优化。其特点在于分组排序。

算法思路

希尔排序是按照其设计者希尔的名字命名的,他对插入排序的效率进行了分析,得出如下结论:

        1.在最坏情况下即待排序序列为逆序时,需要消耗O(n^2)的时间
        2.在最好情况下即待排序序列为顺序时,需要消耗O(n)的时间


于是希尔就想:若是能先将待排序序列进行一次预排序,使待排序序列接近有序,然后再对该序列进行一次插入排序。因此此时直接插入排序的时间复杂度为O(n),那么只需控制预排序阶段的时间复杂度小于O(n^2)那么整体的时间复杂度就比插入排序的时间复杂度低了。

那具体的预排序应该怎么做才会时间复杂度满足要求呢?

        1.先选定一个小于n的整数gap(一般情况下是将n/2作为gap)作为第一增量,然后将所有距离为gap的元素分为一组,并对每一组进行插入排序
        2.重复步骤1,直到gap等于1停止,这时整个序列被分到了一组,进行一次直接插入排序,排序完成

你可能会疑惑,为什么gap由大到小?

因为gap越大,数据挪动的越快,耗时少;gap越小,数据挪动的越慢,耗时多。前期让gap较大,可以让数据快速移动到自己对应位置附近,减少挪动次数。

动画演示

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3Is6Arbg-1668608929993)(希尔排序.assets/动画.gif)]

 

我们来举一个实例:

 

首先gap取5,此时相隔距离为5的元素分到了一组(一共五组,每组两个元素),然后对每一组分别进行插入排序

 

gap折半为2,此时相隔距离为2的元素被分到了一组(一共两组,每组五个元素),然后对每一组分别进行插入排序

 

gap再次折半为1,此时所有元素被分到了一组,对它进行插入排序,至此插入排序完成

 

本例中前两趟就是希尔排序的预排序,最后一趟就是希尔排序的插入排序
 

代码如下

public static void shellSort(int[] a){int gal = a.length;while(gal>1) {int j = 0;gal/=2;   //特别之处gal  分组排序 5 3 1.。。//核心for (int i = gal; i < a.length; i++) {j = i-gal;if(a[j] > a[i]) {int tmp = a[j];a[j] = a[i];a[i] = tmp;}}}}

复杂度分析

希尔排序的时间复杂度并不好计算,因为 gap的取值方法很多中,导致很难去计算,下面是两位老师书中给出的解释。

 

 《数据结构-用面向对象方法与C++描述》--- 殷人昆

     时间复杂度  n^1.3 -- n^1.5  说不准  与每次分组的个数gap有关
     空间复杂度 O(1)
     稳定性 不稳定 当有几个相同的数字时,排序后相对位置会改变

时间复杂度测试

接下来我们试着用大量数据测试一下。

int[] a = new int[10_0000];  //10万个数据测试

1.orderArray函数实现生成一个基本有序数列,即从小到大排列。

public static void orderArray(int[] a) {for (int i = 0; i < a.length; i++) {a[i] = i;}}


2.notOrderArray函数生成一个倒序数列,即从大到小排列。

public static void notOrderArray(int[] a) {for (int i = 0; i < a.length; i++) {a[i] = a.length-i;}}


3.randomArray函数生成一个随机无序数列。

 public static void randomArray(int[] a) {Random random = new Random();for (int i = 0; i < a.length; i++) {a[i] = random.nextInt(10_0000);}}


4.testInsertSort函数测试   System.currentTimeMillis() 返回值单位是毫秒

 

 public static void testInsertSort(int[] a){int[] tmpArray = Arrays.copyOf(a,a.length);long startTime = System.currentTimeMillis();    //注意用long接收shellSort(tmpArray);long endTime = System.currentTimeMillis();  //返回单位是毫秒System.out.println("直接插入排序耗时:"+(endTime-startTime));}


5.main函数调用执行

public static void main(String[] args) {int[] a = new int[10_0000];//有序System.out.println("基本有序数列");orderArray(a);testInsertSort(a);//倒序System.out.println("逆序数列");notOrderArray(a);testInsertSort(a);//随机乱序System.out.println("无序数列");randomArray(a);testInsertSort(a);}

运行结果

         

 希尔排序和直接插入排序都属于插入排序,而希尔排序更是直接插入排序的优化。对比上文直接插入排序的测试结果。

            

 可以看出,希尔排序确实快了许多。并且耗时稳定。

 完整代码

import java.util.Random;public class sort {public static void main(String[] args) {int[] a = new int[10_0000];//有序System.out.println("基本有序数列");orderArray(a);testInsertSort(a);//无序System.out.println("逆序数列");notOrderArray(a);testInsertSort(a);//乱序System.out.println("无序数列");randomArray(a);testInsertSort(a);}//希尔排序  是插入排序的优化//时间复杂度  n^1.3 -- n^1.5  说不准  与每次分组的个数有关//空间复杂度 O(1)//稳定性 不稳定 当有几个相同的数字时,排序后相对位置会改变public static void shellSort(int[] a){int gal = a.length;while(gal>1) {int j = 0;gal/=2;   //特别之处gal  分组排序 5 3 1.。。//核心for (int i = gal; i < a.length; i++) {j = i-gal;if(a[j] > a[i]) {int tmp = a[j];a[j] = a[i];a[i] = tmp;}}}}//生成有序数组  从小到大排列public static void orderArray(int[] a) {for (int i = 0; i < a.length; i++) {a[i] = i;}}//n无序 其实就是从大到小排列public static void notOrderArray(int[] a) {for (int i = 0; i < a.length; i++) {a[i] = a.length-i;}}//乱序 随机生成序列public static void randomArray(int[] a) {Random random = new Random();for (int i = 0; i < a.length; i++) {a[i] = random.nextInt(10_0000);}}//大量数据测试public static void testInsertSort(int[] a){int[] tmpArray = Arrays.copyOf(a,a.length);long startTime = System.currentTimeMillis();    //注意用long接收shellSort(tmpArray);long endTime = System.currentTimeMillis();System.out.println("希尔排序耗时:"+(endTime-startTime));}}

 创作不易,如果本篇博客对您有一定的帮助,大家记得留言+点赞哦。

相关文章:

八大排序算法--希尔排序(动图理解)

目录 希尔排序 概念 算法思路 动画演示 代码如下 复杂度分析 时间复杂度测试 运行结果 完整代码 创作不易&#xff0c;如果本篇博客对您有一定的帮助&#xff0c;大家记得留言点赞哦。 希尔排序 概念 希尔排序是插入排序的一种&#xff0c;是对直接插入排序的优化。其…...

数据结构之常见排序算法

文章目录 1.排序概念2.10种排序比较3.排序算法3.1直接插入排序&#xff08;元素越有序&#xff0c;越高效&#xff09;3.2希尔排序序( 缩小增量排序 )3.3直接选择排序3.5堆排序3.6冒泡排序3.8快速排序 递归实现&#xff08;无序使用最好&#xff09;3.8.1挖坑法 &#xff08;建…...

Java版企业电子招标采购系统源代码Spring Boot + 二次开发 + 前后端分离 构建企业电子招采平台之立项流程图

项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&#xff0c;以及审…...

2.2 模型与材质基础

一、渲染管线与模型基础 1. 渲染管线 可编程阶段&#xff08;蓝色区域&#xff09;&#xff1a; 1顶点着色器 2几何着色器 3片元着色器 2. 模型的实现原理 UV&#xff1a;在建模软件中&#xff0c;进行UV展开&#xff0c;UV会放在一个横向为U纵向为V&#xff0c;范围&#xff0…...

什么是Docker

一 、什么是Docker 1.1 简介 Docker 使用 Google 公司推出的 Go 语言 (opens new window)进行开发实现&#xff0c;基于 Linux 内核的 cgroup (opens new window)&#xff0c;namespace (opens new window)&#xff0c;以及 OverlayFS (opens new window)类的 Union FS (open…...

1109. 航班预订统计

这里有 n 个航班&#xff0c;它们分别从 1 到 n 进行编号。 有一份航班预订表 bookings &#xff0c;表中第 i 条预订记录 bookings[i] [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti &#xff08;包含 firsti 和 lasti &#xff09;的 每个航班 上预订了 seatsi 个座…...

[SQL挖掘机] - 窗口函数 - 合计: rollup

介绍: rollup 是一种用于在 sql 查询中生成聚合数据的特殊操作。它可以创建包含子总计和总计的结果集&#xff0c;并可用于生成层次化报表或汇总数据。 rollup 操作在 group by 子句中使用&#xff0c;可以在查询结果中生成多级汇总数据。它会根据指定的列进行分组&#xff0…...

2022年全国硕士研究生入学统一考试管理类专业学位联考写作试题——解析版

四、写作&#xff1a;第56&#xff5e;57小题&#xff0c;共65分。其中论证有效性分析30分&#xff0c;论说文35分。 56.论证有效性分析&#xff1a;分析下述论证中存在的缺陷和漏洞&#xff0c;选择若干要点&#xff0c;写一篇600字左右的文章&#xff0c;对该论证的有效性进…...

元类在测试框架中的运用

元类在测试框架中的运用 书接上回 我们知道了元类的基本用法&#xff0c;也写了一个小demo&#xff0c;接下来我们就尝试运用进我们测试框架。 #一款无需编码且易用于二次开发的接口测试框架。 #我写的我写的我写的我写的 pip install mwj-apitest #这里面就用到了元类&…...

VBA快速交叉分段标记字符颜色

实例需求&#xff1a;A列中有不确定行数的数据&#xff0c;现在需要将数据按照每4位一组间隔标记颜色&#xff0c;如下图所示。 示例代码如下。 Sub Demo()Dim rngCell As RangeDim rngData As RangeDim i, res, intLenSet rngData Range("A1").CurrentRegionrngDa…...

根据Pytorch源码实现的 ResNet18

一&#xff0c;类模块定义: import torch import torch.nn as nn import torch.nn.functional as F from torch import Tensorclass ResBlock(nn.Module):def __init__(self, inchannel, outchannel, stride1) -> None:super(ResBlock, self).__init__()# 这里定义了残差块…...

药品管理系统servlet+jsp+sql医院药店仓库进销存java源代码mysql

本项目为前几天收费帮学妹做的一个项目&#xff0c;Java EE JSP项目&#xff0c;在工作环境中基本使用不到&#xff0c;但是很多学校把这个当作编程入门的项目来做&#xff0c;故分享出本项目供初学者参考。 一、项目描述 药品管理系统servletjspsql 系统有1权限&#xff1a;…...

这9个UI设计工具一定码住!非常好用

对于设计师来说&#xff0c;好用的UI设计工具无疑会对设计工作起到事半功倍的作用&#xff0c;今天本文与大家分享9个好用的UI设计工具&#xff0c;一起来看看吧&#xff01; 1、即时设计 即时设计是一个能在网页中直接使用&#xff0c;且支持团队协作的国产UI设计工具&#…...

gin通过反射来执行动态的方法

在gin中&#xff0c;可以通过反射来执行对应的方法。下面是一个示例&#xff1a; package mainimport ("fmt""github.com/gin-gonic/gin""reflect" )type UserController struct{}func (uc *UserController) GetUser(c *gin.Context) {userId :…...

java高并发系列 - 第23天:JUC中原子类,一篇就够了

java高并发系列 - 第23天:JUC中原子类 这是java高并发系列第23篇文章,环境:jdk1.8。 本文主要内容 JUC中的原子类介绍介绍基本类型原子类介绍数组类型原子类介绍引用类型原子类介绍对象属性修改相关原子类预备知识 JUC中的原子类都是都是依靠volatile、CAS、Unsafe类配合…...

《HeadFirst设计模式(第二版)》第一章源码

代码文件目录结构&#xff1a; FlyBehavior.java package Chapter1_StrategyPattern.ch1_3_behavior.behaviors.fly;public interface FlyBehavior {void fly(); } FlyNoWay.java package Chapter1_StrategyPattern.ch1_3_behavior.behaviors.fly;public class FlyNoWay imp…...

insert into select用法

文章目录 一、insert into select二、insert into select插入失败 本篇文章主要讲解insert into select 的用法&#xff0c;以及insert into select的坑或者注意事项。本篇文章中的sql基于mysql8.0进行讲解 一、insert into select 该语法常用于从另一张表查询数据插入到某表中…...

图像识别技术:计算机视觉的进化与应用展望

导言&#xff1a; 图像识别技术是计算机视觉领域的重要研究方向&#xff0c;它使计算机能够理解和解释图像内容&#xff0c;从而实现自动化和智能化的图像处理。随着深度学习等技术的快速发展&#xff0c;图像识别在诸多领域取得了重大突破&#xff0c;如自动驾驶、医疗影像分析…...

【免费送书】重新定义Python学习!

欢迎关注博主 Mindtechnist 或加入【智能科技社区】一起学习和分享Linux、C、C、Python、Matlab&#xff0c;机器人运动控制、多机器人协作&#xff0c;智能优化算法&#xff0c;滤波估计、多传感器信息融合&#xff0c;机器学习&#xff0c;人工智能等相关领域的知识和技术。关…...

Qt 4. 发布exe

把ex2.exe放在H盘Ex2文件夹下&#xff0c;执行 H:\Ex2>windeployqt ex2.exe H:\Ex2>windeployqt ex2.exe H:\Ex2\ex2.exe 64 bit, release executable Adding Qt5Svg for qsvgicon.dll Skipping plugin qtvirtualkeyboardplugin.dll due to disabled dependencies (Qt5…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...