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

深入浅出排序算法之希尔排序

目录

1. 原理

2. 代码实现

3. 性能分析


1. 原理

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。

(1)希尔排序是对直接插入排序的优化。
(2)当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。

 

2. 代码实现

    //希尔排序public static void shellSort(int[] array){int gap = array.length;while(gap > 1){shell(array,gap);gap /= 2;//增量是多少都可以,随便小伙伴们写}shell(array,1);}//有增量的直接插入排序//不是一组希尔排序全部排完,是间隔性的,可能是第一组先插一个,第二组再插一个,第一组再插……private static void shell(int[] array,int gap){for(int i = gap;i < array.length;i++){int tmp = array[i];int j = i - gap;for(;j >= 0;j -= gap){if(array[j] > array[j+gap]){array[j + gap] = array[j];}else{break;}}array[j + gap] = tmp;}}public static void main(String[] args) {int[] arr = {3,1,2,4,5};Sort.shellSort(arr);for (int x : arr) {System.out.print(x + " ");}}

3. 性能分析

时间复杂度空间复杂度
最好平均最坏
O(N)O(N^1.3)O(N^2)O(1)
数据有序难以构造出来
    public static void main(String[] args) {int[] arr2 = new int[10000];Test.createArray2(arr2);long s2 = System.currentTimeMillis();Sort.insertSort(arr2);long e2 = System.currentTimeMillis();System.out.println("直接插入排序的数组逆序的情况:"+(e2 - s2));int[] arr1 = new int[10000];Test.createArray2(arr1);long s1 = System.currentTimeMillis();Sort.shellSort(arr2);long e1 = System.currentTimeMillis();System.out.println("希尔排序的数组逆序的情况:"+(e1 - s1));}

稳定性:不稳定。

由于增量不同,可能导致本来在后面的元素跑到前面去!

相关文章:

深入浅出排序算法之希尔排序

目录 1. 原理 2. 代码实现 3. 性能分析 1. 原理 希尔排序法又称缩小增量法。希尔排序法的基本思想是&#xff1a;先选定一个整数&#xff0c;把待排序文件中所有记录分成个组&#xff0c;所有距离为的记录分在同一组内&#xff0c;并对每一组内的记录进行排序。然后&#xf…...

close excel by keyword 根据关键字关闭 excel 窗口 xlwings 方式实现

根据标题关键字关闭 workbook&#xff0c;如果没有打开的 workbook 则退出 excel xlwings 方式实现 更方便快捷 def close_excel_by_keyword(keyword):if ~$ in keyword:returnapp xw.apps.activefor workbook in app.books:if keyword in workbook.name:workbook.close()fi…...

LIO-SAM算法解析

文章目录 简介算法概述1.点云去畸变1.1 主要功能1.2 主要流程 2.特征提取3.IMU预积分4.地图优化5.算法评估 简介 LIO-SAM在lego-loam的基础上新增了对IMU和GPS的紧耦合&#xff0c;采用一个因子图对位姿进行优化&#xff0c;包括IMU因子&#xff0c;激光里程计因子&#xff0c…...

vscode 提升小程序开发效率的必备插件与工具

1&#xff0c;微信小程序开发助手&#xff08;WeChat Snippet&#xff09;&#xff1a;提供了小程序代码片段、模板和快速生成页面的功能&#xff0c;加快了开发速度。 2&#xff0c;小程序助手&#xff08;Minapp&#xff09;&#xff1a;提供了小程序项目创建、编译、预览和…...

第五章单元测试

一、学习目的与要求 本章对单元测试进行了详细的介绍。通过本章的学习&#xff0c;应掌握单元测试的概念&#xff0c;了解单元测试的误区&#xff0c;掌握单元测试的策略、分析方法和用例设计方法。 二、考核知识点与考核目标 &#xff08;一&#xff09;单元测试的概念&#…...

【JAVA基础】多线程与线程池

多线程与线程池 文章目录 多线程与线程池1. 相关概念1.1 线程调度1.2 守护线程 2. 生命周期3. 同步机制/同步锁3.1 synchronized3.2 lock3.3 synchronized 与 Lock 的对比 4. 死锁5. 线程通信5.1 线程间的通信5.2 等待唤醒机制5.3 举例5.4 调用 wait 和 notify 需注意的细节5.5…...

HCIA数据通信——交换机(Vlan间的通信与安全)

前言 之前的提到了交换机的概念和实验。不过交换机的一些功能还没有说完&#xff0c;我们的实验也仅仅是阻止相同地址段的IP地址互通&#xff0c;也没有用到子接口和路由器。显然&#xff0c;那样的配置过于简单。 端口安全 Port Security&#xff08;端口安全&#xff09;的功…...

Linux shell编程学习笔记16:bash中的关联数组

上一节我们探讨了普通的数组&#xff0c;即使用数字下标来索引数组中不同的元素的数组&#xff0c;也可以称之为索引数组。 相比纯粹的数字&#xff0c;字符串不仅能表明含义&#xff0c;也更便于记忆使用&#xff0c;于是就有了关联数组。 一、关联数组概述 bash 从4.0开始支…...

浏览器是怎么执行JS的?——消息队列与事件循环

看完渡一的课后&#xff0c;感觉这块内容确实非常重要&#xff0c;写 JS 的连 JS 的执行原理都不知道可不行。 事件循环 在写 JS 的时候&#xff0c;你有没有想过 JS 是按照什么顺序执行的&#xff1f;浏览器是怎么执行 JS 代码的&#xff1f;为什么有时候代码没有按照我们认为…...

IMU预积分的过程详解

一、IMU和相机数据融合保证位姿的有效性&#xff1a; 当运动过快时&#xff0c;相机会出现运动模糊&#xff0c;或者两帧之间重叠区域太少以至于无法进行特征匹配&#xff0c;所以纯视觉SLAM对快速的运动很敏感。而有了IMU&#xff0c;即使在相机数据无效的那段时间内&#xff…...

TypeScript中的类型运算符

类型运算符 1. keyof运算符 1. 简介 是一个单目运算符&#xff0c;接受一个对象类型作为参数&#xff0c;返回该对象的所有键名组成的联合类型。 type MyObj {foo: number,bar: string, };type Keys keyof MyObj; // foo|bar这个例子keyof MyObj返回MyObj的所有键名组成的…...

【蓝桥杯选拔赛真题03】C++输出字母Y 青少年组蓝桥杯C++选拔赛真题 STEMA比赛真题解析

目录 C/C++输出字母Y 一、题目要求 1、编程实现 2、输入输出 二、算法分析...

redis搭建集群-多实例快速搭建

1.基础的redis.conf的配置 # Redis configuration file example. # # Note that in order to read the configuration file, Redis must be # started with the file path as first argument: # # ./redis-server /path/to/redis.conf# Note on units: when memory size is ne…...

为什么进行压力测试? 有哪些方法?

在信息技术飞速发展的今天&#xff0c;软件系统的性能已经成为了用户满意度的决定性因素之一。而要确保一个系统在实际使用中能够稳定可靠地运行&#xff0c;压力测试就显得尤为关键。本文将深入探讨什么是压力测试&#xff0c;为什么它是如此重要&#xff0c;以及一些常见的压…...

Java开发者必备:支付宝沙箱环境支付远程调试指南

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f516;系列专栏&#xff1a; C语言、Linux、Cpolar ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 文章目录 前言1. 下载当面付demo2. 修改配置文件3. 打包成web服务4. 局域网测试5. 内网穿透6. 测试公网访问7. 配置二级…...

基于STM32温湿度传感器采集报警系统设计

**单片机设计介绍&#xff0c;1648【毕设课设】基于STM32温湿度传感器采集报警系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序程序 六、 文章目录 一 概要 这次的设计主要是通过读取DHT11和HCSR04的数值&#xff0c;&#xff08;Proteus的传感器…...

檢測項目簡體字

某些項目可能要求代碼中不允許使用簡體字 安裝stcheck檢查 yarn add stcheck --dev在項目根目錄創建 st.config.json 文件 {"patterns": ["./**/*.(ts|js|tsx|jsx|vue|html)","!**/node_modules/**","!.git/**"],"gitignore&q…...

适用于嵌入式arm的ffmpeg编解码

在嵌入式arm应用开发中&#xff0c;经常会遇到需要处理视频的情况&#xff0c;这时候就需要强大的开源工具ffmpeg出马了。 这里可以下载到各个版本的ffmpeg。 ffmpeg各版本https://www.videohelp.com/software/ffmpeg/old-versions 现在ffmpeg更新较频繁&#xff0c;如…...

nlp与知识图谱代码解读_词嵌入

目录 词嵌入简单原理代码案例解读专业原理介绍场景 词嵌入 简单原理 可以使用一些比喻和生活中的例子&#xff1a; 老师&#xff1a; 你们还记得玩乐高积木的时候&#xff0c;每个积木块代表了一个特定的事物或形状吗&#xff1f;现在&#xff0c;想象一下&#xff0c;每个词…...

HarmonyOS 音频通话开发指导

常用的音频通话模式包括 VOIP 通话和蜂窝通话。 ● VOIP 通话&#xff1a;VOIP&#xff08;Voice over Internet Protocol&#xff09;通话是指基于互联网协议&#xff08;IP&#xff09;进行通讯的一种语音通话技术。VOIP 通话会将通话信息打包成数据包&#xff0c;通过网络进…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...