插入排序——希尔排序
1、简述:
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。 [1]
2、复杂度
时间复杂度:O(nlogn)~O(n²) (取决于增量的序列)
空间复杂度:O(1)
3、稳定性:不稳定的
由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。
4、例子:
推导过程:格努增量进行分组,增量 = 序列长度/2;

#include <iostream>
using namespace std;int main() {int arr[8] = {45, 98, 66, 90, 88, 78, 25, 45};int len = sizeof(arr)/sizeof(arr[0]);int gap = len / 2;int count = 0; // 记录输出次数用的可删除while (gap >= 1) {cout<<++count<<"轮排序:"<<endl;// 将每个元素进行for (int i = gap; i < len; i++) {// 对同个分组内的元素进行比较for (int j = i - gap; j >= 0; j -= gap) {if (arr[j] <= arr[j + gap]) break;// 换位:方法一(交换两个数据不使用第三个变量)arr[j] = arr[j] + arr[j + gap] - (arr[j + gap] = arr[j]);// 换位:方法二(第三个变量)
// int tmp = arr[j + gap];
// arr[j + gap] = arr[j];
// arr[j] = tmp;}}// 缩小增量gap = gap / 2;for (int a = 0;a < len;a++) {cout << arr[a] << " ";}cout<<endl;}cout<<"最后结果:";for (int i = 0;i < len;i++) {cout << arr[i] << " ";}return 0;
}
输出结果:
1轮排序:
45 78 25 45 88 98 66 90
2轮排序:
25 45 45 78 66 90 88 98
3轮排序:
25 45 45 66 78 88 90 98
最后结果:25 45 45 66 78 88 90 98
参考:
千锋教育-希尔排序:希尔排序为什么会那么牛那么快,能够证明吗? - 知乎
百度百科-希尔排序:百度百科-验证
生命不息,学习不止,若有不正确的地方,欢迎指正。
相关文章:
插入排序——希尔排序
1、简述: 希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。 希尔排…...
C语言之初阶总结篇
目录 NO.1 NO.2 NO.3 NO.4 NO.5 NO.6 NO.7 NO.8 NO.9 NO.10 NO.11 NO.12.概念tips NO.13.求最小公倍数 NO.14.最大公因数 NO.15.输入读取字符串 NO.16.倒置字符串 今天是一些C语言题目,最近天气炎热,多喝水。 NO.1 下面程序执行后&am…...
Android签名查看
查看签名文件信息 第一种方法: 1.打开cmd,执行keytool -list -v -keystore xxx.keystore,效果如下图: 第二种方法: 1.打开cmd,执行 keytool -list -v -keystore xxxx.keystore -storepass 签名文件密码࿰…...
Educational Codeforces Round 3
目录 A. USB Flash Drives B. The Best Gift C. Load Balancing D. Gadgets for dollars and pounds A. USB Flash Drives #include<bits/stdc.h>using namespace std; const int N1e65; typedef long long ll; typedef pair<ll,ll> pll; typedef array<int…...
Docker Compose常用命令
常用命令 1.1 restart, start, stop-- 启动和停止服务 命令必须在 docker-compose.yml文件所在的目录下执行。 # 前台启动, 启动项目中的所有服务。 $. docker-compose up# 后台启动, 启动所有服务并在后台运行。 $. docker-compose up -d# 停止所有服务。 $. docker-compose …...
C++——智能指针
智能指针 文章目录 智能指针内存泄漏智能指针解决内存泄漏问题智能指针的使用及原理RAII智能指针对象的拷贝问题 C中的智能指针auto_ptrunique_ptrshared_ptrweak_ptr定制包装器C11和boost中智能指针的关系 内存泄漏 什么是内存泄漏:内存泄漏指因为疏忽或错误造成程…...
CVE-2023-3836:大华智慧园区综合管理平台任意文件上传漏洞复现
文章目录 CVE-2023-3836:大华智慧园区综合管理平台任意文件上传漏洞复现0x01 前言0x02 漏洞描述0x03 影响范围0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 CVE-2023-3836:大华智慧园区综合管理平台任意文件上传漏洞复现 0x01 前言 免责声…...
LAMP搭建WordPress
L linux A apache hhtpd M mysql/maridb P PHP1、 安装php yum -y install php php-fpm php-server php-mysql1.1、 启动php-fpm并自启 systemctl enable php-fpm --now[rootecs-1cee ~]# systemctl status php-fpm ● php-fpm.service - The PHP FastCGI Process ManagerLoa…...
【数学建模竞赛】预测类赛题常用算法解析
解析常见的预测类算法 灰色预测模型 灰色预测模型是一种利用少量的、不完全的信息,建立数学模型并进行预测的方法。该方法通过对系统行为特征的发展变化规律进行估计预测,同时也可以对行为特征的异常情况发生的时刻进行估计计算,并研究特定…...
OFDM 系统在 AWGN 信道下对不同载波频率偏移 (CFO) 的 BER 灵敏度研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
go基础07-了解map实现原理并高效使用
对于C程序员出身的Gopher来说,map类型是和切片、interface一样能让他们感受到Go语言先进性的重要语法元素。map类型也是Go语言中最常用的数据类型之一。 go 中 map 怎么表现? 一些有关Go语言的中文教程或译本将map称为字典或哈希表,但在这里…...
SpringMVC进阶:常用注解、参数传递和请求响应以及页面跳转
目录 一、常用注解 1.1.RequestMapping 1.2.RequestParam 1.3.ModelAttribute 1.4.SessionAttributes 1.5.RequestBody 1.6.RequestHeader 1.7.PathVariable 1.8.CookieValue 二、参数传递 2.1.基础类型String 2.2.复杂类型 2.3.RequestParam 2.4.PathVariable 2…...
nacos - centos7.x环境单机与集群快速部署
参考官网:https://nacos.io/zh-cn/docs/what-is-nacos.html 官方集群部署手册:https://nacos.io/zh-cn/docs/cluster-mode-quick-start.html 【单机部署】 1.下载 & 解压到安装目录 下载:wget -c https://github.com/alibaba/nacos/releases/download/2.1.2/nacos-ser…...
文心一言初体验,和ChatGPT语言理解能力比较
文章目录 第一个考验,语义理解第二个考验,历史问题的回答推荐阅读 百度旗下AI大模型文心一言宣布向全社会全面开放,所有用户都可以体验这款AI大模型了。要比较这两个语言模型,我们先设计好题目。 第一个考验,语义理解 题目1&…...
浏览器进程,性能指标,性能优化
目录 浏览器进程:多进程 主进程:显示、交互,增删进程 UI进程:控制地址栏、书签、前进后退 存储进程:cookie,webstorage,indexDB 渲染进程:每个标签页或窗口都有一个独立的渲染进…...
Python基础set集合定义与函数
set集合 集合的特点: 1.集合是无序 2.集合是去重 定义一个空集合 name_set set() 定义一个非空集合 name_set {a, b, c} 关系测试: 交集,并集,差集,对称差集 1.交集:intersection() 或者 & …...
【大数据之Kafka】九、Kafka Broker之文件存储及高效读写数据
1 文件存储 1.1 文件存储机制 Topic是逻辑上的概念,而partition是物理上的概念,每个partition对应于一个log文件,该log文件中存储的是Producer生产的数据。 Producer生产的数据会被不断追加到该log文件末端,为防止log文件过大导致…...
Android 使用Camera2 API 和 GLSurfaceView实现相机预览
GLSurfaceView 和 SurfaceView 是 Android 中用于显示图像的两个视图类,它们在实现方式和使用场景上有一些区别。 实现方式:GLSurfaceView 基于 OpenGL ES 技术实现,可以通过 OpenGL ES 渲染图像。而 SurfaceView 则是通过基于线程的绘制方式…...
说说IO多路复用
分析&回答 IO多路复用 I/O multiplexing 这里面的 multiplexing 指的其实是在单个线程通过记录跟踪每一个Sock(I/O流)的状态(对应空管塔里面的Fight progress strip槽)来同时管理多个I/O流。直白点说:多路指的是多个socket连接,复用指的是复用一个…...
mysql 锁解决的办法
可以查看锁的信息,TRX_MYSQL_THREAD_ID 为processlist的表中的会话id,用于kill select trx_id,trx_state,trx_started,trx_requested_lock_id,trx_wait_started,trx_weight,trx_mysql_thread_id,trx_query from innodb_trx 可以查看锁的模式,类型,锁的表…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
VisualXML全新升级 | 新增数据库编辑功能
VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...
GraphRAG优化新思路-开源的ROGRAG框架
目前的如微软开源的GraphRAG的工作流程都较为复杂,难以孤立地评估各个组件的贡献,传统的检索方法在处理复杂推理任务时可能不够有效,特别是在需要理解实体间关系或多跳知识的情况下。先说结论,看完后感觉这个框架性能上不会比Grap…...
