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

插入排序——希尔排序

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、简述&#xff1a; 希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”&#xff08;Diminishing Increment Sort&#xff09;&#xff0c;是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 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语言题目&#xff0c;最近天气炎热&#xff0c;多喝水。 NO.1 下面程序执行后&am…...

Android签名查看

查看签名文件信息 第一种方法&#xff1a; 1.打开cmd&#xff0c;执行keytool -list -v -keystore xxx.keystore&#xff0c;效果如下图&#xff1a; 第二种方法: 1.打开cmd&#xff0c;执行 keytool -list -v -keystore xxxx.keystore -storepass 签名文件密码&#xff0…...

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中智能指针的关系 内存泄漏 什么是内存泄漏&#xff1a;内存泄漏指因为疏忽或错误造成程…...

CVE-2023-3836:大华智慧园区综合管理平台任意文件上传漏洞复现

文章目录 CVE-2023-3836&#xff1a;大华智慧园区综合管理平台任意文件上传漏洞复现0x01 前言0x02 漏洞描述0x03 影响范围0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 CVE-2023-3836&#xff1a;大华智慧园区综合管理平台任意文件上传漏洞复现 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…...

【数学建模竞赛】预测类赛题常用算法解析

解析常见的预测类算法 灰色预测模型 灰色预测模型是一种利用少量的、不完全的信息&#xff0c;建立数学模型并进行预测的方法。该方法通过对系统行为特征的发展变化规律进行估计预测&#xff0c;同时也可以对行为特征的异常情况发生的时刻进行估计计算&#xff0c;并研究特定…...

OFDM 系统在 AWGN 信道下对不同载波频率偏移 (CFO) 的 BER 灵敏度研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

go基础07-了解map实现原理并高效使用

对于C程序员出身的Gopher来说&#xff0c;map类型是和切片、interface一样能让他们感受到Go语言先进性的重要语法元素。map类型也是Go语言中最常用的数据类型之一。 go 中 map 怎么表现&#xff1f; 一些有关Go语言的中文教程或译本将map称为字典或哈希表&#xff0c;但在这里…...

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语言理解能力比较

文章目录 第一个考验&#xff0c;语义理解第二个考验&#xff0c;历史问题的回答推荐阅读 百度旗下AI大模型文心一言宣布向全社会全面开放,所有用户都可以体验这款AI大模型了。要比较这两个语言模型&#xff0c;我们先设计好题目。 第一个考验&#xff0c;语义理解 题目1&…...

浏览器进程,性能指标,性能优化

目录 浏览器进程&#xff1a;多进程 主进程&#xff1a;显示、交互&#xff0c;增删进程 UI进程&#xff1a;控制地址栏、书签、前进后退 存储进程&#xff1a;cookie&#xff0c;webstorage&#xff0c;indexDB 渲染进程&#xff1a;每个标签页或窗口都有一个独立的渲染进…...

Python基础set集合定义与函数

set集合 集合的特点&#xff1a; 1.集合是无序 2.集合是去重 定义一个空集合 name_set set() 定义一个非空集合 name_set {a, b, c} 关系测试&#xff1a; 交集&#xff0c;并集&#xff0c;差集&#xff0c;对称差集 1.交集&#xff1a;intersection() 或者 & …...

【大数据之Kafka】九、Kafka Broker之文件存储及高效读写数据

1 文件存储 1.1 文件存储机制 Topic是逻辑上的概念&#xff0c;而partition是物理上的概念&#xff0c;每个partition对应于一个log文件&#xff0c;该log文件中存储的是Producer生产的数据。 Producer生产的数据会被不断追加到该log文件末端&#xff0c;为防止log文件过大导致…...

Android 使用Camera2 API 和 GLSurfaceView实现相机预览

GLSurfaceView 和 SurfaceView 是 Android 中用于显示图像的两个视图类&#xff0c;它们在实现方式和使用场景上有一些区别。 实现方式&#xff1a;GLSurfaceView 基于 OpenGL ES 技术实现&#xff0c;可以通过 OpenGL ES 渲染图像。而 SurfaceView 则是通过基于线程的绘制方式…...

说说IO多路复用

分析&回答 IO多路复用 I/O multiplexing 这里面的 multiplexing 指的其实是在单个线程通过记录跟踪每一个Sock(I/O流)的状态(对应空管塔里面的Fight progress strip槽)来同时管理多个I/O流。直白点说&#xff1a;多路指的是多个socket连接&#xff0c;复用指的是复用一个…...

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 可以查看锁的模式&#xff0c;类型&#xff0c;锁的表…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...