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

【数据结构与算法】十大经典排序算法-希尔排序

🌟个人博客:www.hellocode.top
🏰Java知识导航:Java-Navigate
🔥CSDN:HelloCode.
🌞知乎:HelloCode
🌴掘金:HelloCode
⚡如有问题,欢迎指正,一起学习~~


希尔排序是一种插入排序的改进版本,旨在解决插入排序在处理大规模数据时的效率问题。通过将数组分为多个子序列并对这些子序列进行局部排序,希尔排序逐步将元素“分组”并逐渐接近它们的最终排序位置。这种逐步的排序方式可以有效减少逆序对的数量,从而加快整体排序过程。

基本思想

希尔排序

这里使用五分钟学算法大佬的动图,很清晰

  1. 希尔排序将数组分成若干个子序列,每个子序列包含间隔为 h 的元素,称为 h-子序列。
  2. 对每个 h-子序列应用插入排序,以实现局部排序。
  3. 不断缩小 h 的值,重复步骤 2,直到 h 为 1。此时,整个序列基本有序,只需对相邻元素进行插入排序即可。

一般间隔也就是gap的选取就是数组长度的一半,如上图所示,原始数组为[8,9,1,7,2,3,5,4,6,0],初始间隔就是5,也就是会将图中数组分为[8,3][9,5][1,4][7,6][2,0]共5组,然后对这些组合进行插入排序,并不断缩小gap(每次缩小一半),重复进行插入排序操作,最终就能够得到有序数组~

对分组不太理解的可以看下图,非常清晰:

img

代码实现

代码的话还是循环,只需要在插入排序外层再加一层循环控制gap 的缩小即可,就是改良版的插入排序(需要对比图片和插入排序的思路仔细体会),具体代码如下:

/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月10日 20:59*/
public class ShellSort {public static void main(String[] args) {int[] arr = {8,9,1,7,2,3,5,4,6,0};System.out.println("原数组:" + Arrays.toString(arr));shellSort(arr);System.out.println("排序后:" + Arrays.toString(arr));}public static void shellSort(int[] arr){int n = arr.length;// 两层for循环,外层不断缩小gap(每次缩小为一半)for(int gap = n / 2; gap > 0; gap /= 2){// 内层对每组进行插入排序// 这里的i还是指向第一个待插入元素(也就是gap,可以看图理解)// 此时已排序数组的最后一个元素,就应该是i - gap// 这里i的跨度就不应该是++而是 += gap(配合图更好理解)for(int i = gap;i < n; i ++){int current = arr[i];       // 当前待插入元素int pre = i - gap;          // 有序部分的最后一个元素下标// 当 i 位置元素大于等于 pre 位置元素时说明已经有序,就继续i+= gapwhile(pre >= 0){// 已经是正确位置,直接退出循环if(current >= arr[pre]){break;}// 位置不正确,需要寻找正确位置arr[pre + gap] = arr[pre];pre -= gap;}//此时pre下标的值是负数了,将current的值放到pre变量加上一个gap的位置上arr[pre + gap] = current;}}}
}

测试:

原数组:[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
排序后:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

优化

  • 希尔排序的性能高度依赖于步长序列的选择。选择不同的步长序列可能会对排序效率产生影响。
  • 一些常见的步长序列包括希尔步长序列(h = n/2, n/4, n/8, …)、Sedgewick步长序列等。
  • 通过尝试不同的步长序列,可以选择合适的步长来优化希尔排序的性能。

总结

优点

  1. 相对于传统的插入排序,希尔排序通过将元素分组进行排序,减少了逆序对的数量,从而加快了排序过程。
  2. 希尔排序是原地排序算法,只需在原始数组上进行元素的交换和移动,不需要额外的辅助空间。

缺点

  1. 希尔排序的最坏情况时间复杂度并不稳定,通常在 O(n^2) 到 O(n log n) 之间。虽然平均情况下性能较好,但在某些特定情况下,性能可能不如其他高级排序算法。
  2. 步长序列的选择对性能产生影响,选择不当可能导致排序效率下降。

复杂度

  • 时间复杂度:取决于步长序列的选择,通常在 O(n log n) 到 O(n^2) 之间。
  • 空间复杂度:原地排序,空间复杂度为 O(1)。

使用场景

  1. 希尔排序适用于中等规模的数据集,对于大规模数据,其性能可能不如其他更高级的排序算法。
  2. 在实际应用中,希尔排序的性能可能会比预期的好,尤其在某些特定情况下,例如对部分有序的数据进行排序时。

当使用希尔排序时,应特别注意其时间和空间复杂度的说明是基于最坏情况下的估计。这样的估计可能会高于实际情况。希尔排序在某些实际应用中可能表现得比预期的要好。

相关文章:

【数据结构与算法】十大经典排序算法-希尔排序

&#x1f31f;个人博客&#xff1a;www.hellocode.top &#x1f3f0;Java知识导航&#xff1a;Java-Navigate &#x1f525;CSDN&#xff1a;HelloCode. &#x1f31e;知乎&#xff1a;HelloCode &#x1f334;掘金&#xff1a;HelloCode ⚡如有问题&#xff0c;欢迎指正&#…...

docker 常用命令

1. 搜索并下载镜像 docker search bundlefusion # 搜索docker pull jhljx/bundlefusion # 将远程仓库文件下载到本地2. 用镜像创建容器 docker run -it --namebundlefusion colec777/bundlefusion-cu11.4-cudagl:v8 /bin/bash # 创建并运行 exit # 退出终端 sudo docker cont…...

uniapp微信小程序中打开腾讯地图获取用户位置信息

实现的效果 第一步&#xff1a;首先登录微信公众平台 , 需要用到AppID 第二步&#xff1a; 注册登录腾讯位置服务 注册需要手机号和邮箱确认&#xff0c;然后创建应用 创建后点击添加key 添加后会生成key&#xff0c;后面会用到这个key 第三步&#xff1a; 登录微信公众平台&a…...

嵌入式领域:人才供需失衡,发展潜力巨大

嵌入式技术正快速发展&#xff0c;ARM处理器、嵌入式操作系统、LINUX等技术助力嵌入式领域崛起。然而&#xff0c;行业新颖且门槛高&#xff0c;缺乏专业指导。因此&#xff0c;嵌入式人才稀缺&#xff0c;身价水涨船高。 未来几年&#xff0c;嵌入式系统将在信息化、智能化、…...

python 书籍

python高手进阶之路 10册 QQ:417398600...

Debian纯净系统安装php常用扩展和程序

适用于 php-fpm debian容器 mysql扩展 docker-php-ext-install pdo_mysql docker-php-ext-install mysqliredis扩展 pecl install redis docker-php-ext-enable redis# pecl无法装就&#xff1a; docker-php-source extract # 创建并初始化 /usr/src/php目录&#xff08;扩展…...

vue+element中如何设置单个el-date-picker开始时间和结束时间关联

功能&#xff1a;选了开始时间&#xff0c;则结束时间只能选择开始时间之后的&#xff1b;选了结束时间&#xff0c;则开始时间只能选择结束时间之前的 重点是picker-options属性 图示&#xff1a; 代码展示: // body 内部<el-form-item><el-date-pickerv-model&qu…...

二次封装ajax和axios

ajax app.config.globalProperties.$http function(url, method, data, async, fun) {$.ajax({url: baseUrl url, //请求地址type: method, //请求方式dataType: json, //数据类型contentType: "application/json",xhrFields: { //跨域设置withCredentials: t…...

Android进阶之SeekBar动态显示进度

SeekBar 在开发中并不陌生,默认的SeekBar是不显示进度的,当然用吐司或者文案在旁边实时显示也是可以的,那能不能移动的时候才显示&#xff0c;默认不显示呢,当然网上花哨的三方工具类太多了&#xff0c;但是我只是单纯的想在SeekBar的基础上去添加一个可以跟随移动显示的气泡而…...

企业计算机服务器中了locked勒索病毒怎么办,如何预防勒索病毒攻击

计算机服务器是企业的关键信息基础设备&#xff0c;随着计算机技术的不断发展&#xff0c;企业的计算机服务器也成为了众多勒索者的攻击目标&#xff0c;勒索病毒成为当下计算机服务器的主要攻击目标。近期&#xff0c;我们收到很多企业的求助&#xff0c;企业的服务器被locked…...

大麦订单截图 一键生成订单截图

新版付款图样式展示 这个样式图就是在大麦刚付款完的一个订单截图&#xff0c;它的状态是等待卖家发货 下滑下载源码 下载源码&#xff1a;https://pan.baidu.com/s/16lN3gvRIZm7pqhvVMYYecQ?pwd6zw3...

LLaMA长度外推高性价比trick:线性插值法及相关改进源码阅读及相关记录

前言 最近&#xff0c;开源了可商用的llama2&#xff0c;支持长度相比llama1的1024&#xff0c;拓展到了4096长度&#xff0c;然而&#xff0c;相比GPT-4、Claude-2等支持的长度&#xff0c;llama的长度外推显得尤为重要&#xff0c;本文记录了三种网络开源的RoPE改进方式及相…...

中国信息安全测评中心CISP家族认证一览

随着国家对网络安全的重视&#xff0c;中国信息安全测评中心根据国家政策、未来趋势、重点内容陆续增添了很多CISP细分认证。 今日份详细介绍&#xff0c;部分CISP及其子品牌相关认证内容&#xff0c;一定要收藏哟&#xff01; 校园版CISP NISP国家信息安全水平考试&#xff…...

牛客网【面试必刷TOP101】~ 06 递归/回溯

牛客网【面试必刷TOP101】~ 06 递归/回溯 文章目录 牛客网【面试必刷TOP101】~ 06 递归/回溯[toc]BM55 没有重复项数字的全排列(★★)BM56 有重复项数字的全排列(★★)BM57 岛屿数量(★★)BM58 字符串的排列(★★)BM59 N皇后问题(★★★)BM60 括号生成(★★)BM61 矩阵最长递增路…...

ArcGIS Pro基础:【划分】工具实现等比例、等面积、等宽度划分图形操作

本次介绍【划分】工具的使用&#xff0c;如下所示&#xff0c;为该工具所处位置。使用该工具可以实现对某个图斑的等比例面积划分、相等面积划分和相等宽度划分。 【等比例面积】&#xff1a;其操作如下所示&#xff0c;其中&#xff1a; 1表示先选中待处理的图斑&#xff0c;2…...

括号匹配问题:栈的巧妙应用与代码优化【栈、优化、哈希表】

当解决算法问题时&#xff0c;灵活使用数据结构是至关重要的。在这个问题中&#xff0c;我们需要判断一个只包含括号的字符串是否有效&#xff0c;即括号是否能够正确匹配和闭合。使用栈这一数据结构可以很好地解决这个问题。 题目链接&#xff1a;有效的括号 解题思路&#xf…...

vue项目正确使用样式deep穿透

经常开发前端的程序员应该都知道前端一般都是组件化开发&#xff0c;为了避免样式污染通常会使用scoped添加属性选择器&#xff0c;此时如果我们想在父组件中修改子组件的样式便成了难题。其实&#xff0c;我们可以通过以下几种方式修改子组件样式&#xff0c; 组件样式穿透 …...

Jenkins持续集成-快速上手

Jenkins持续集成-快速上手 注&#xff1a;Jenkins一般不单独使用&#xff0c;而是需要依赖代码仓库&#xff0c;构建工具等。 搭配组合&#xff1a;GitGitee&#xff08;GitHub、GitLab&#xff09;MavenJenkins 前置准备 常见安装方式&#xff1a; war包Docker容器实例&…...

查看linux 所有运行的应用和端口命令

要查看 Linux 中所有运行的应用程序及其对应的端口&#xff0c;可以使用以下命令&#xff1a; 1. 使用 netstat 命令&#xff08;已被弃用&#xff0c;建议使用 ss 命令&#xff09;&#xff1a; netstat -tuln 这会显示当前系统上所有打开的网络连接和监听的端口。其中&#…...

Maven安装与配置,Eclipse配置Maven【图文并茂的保姆级教程】

&#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 接下来看看由辉辉所写的关于Maven的相关操作吧 目录 &#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 一.Maven是什么&#xff1f; 二.Maven的下…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...