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

【数据结构】八大排序之希尔排序算法

news 2025/8/24 3:17:31

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022

一.优化直接插入排序算法

我们在之前对直接插入排序算法的优化部分通过对直接插入排序的分析可以得到一个结论,即:

       进行直接插入排序的数组,如果越接近局部有序,则后续进行直接插入排序算法时其时间复杂度就会越低.

       所谓基本有序,就是指小的关键字基本在前面,大的关键字基本在后面,而不大不小的基本在中间.

       例如下面这个数组序列,虽然它还是无序的状态,甚至是局部逆序的状态,但至少它的前8个数据"0-7"都在前半部分,后8个数据"8-15"都在后半部分,这样就比完全逆序状态更接近基本有序,相应的算法执行的次数也直接减少了一半:

当我们再进一步,将它们整合的更加接近局部有序一些,可以发现,这时算法的总执行次数又直接减少了一半:

        而当我们整合到最接近局部有序时,可以发现,这时算法的总执行次数表达式中的n^2项就已经消失了:

我们已经知道了如果将数组整合成局部有序,就可以大大优化直接插入排序,问题是如何通过预排序将数列整合成局部有序呢?

其实很简单,我们将这些数字不断分为gap组,然后分别让相隔gap个元素的一组数据保持有序就可以了:

         如下,第一次我们将数组分为8组,然后使相隔8个元素的每组数据都保持有序,即第一组数据"15和7"要调整为顺序,则将其二者调换位置即可,后续七组操作同理:

然后我们就可以得到如下数组了:

         接着,我们再将数组分为4组,让每隔4个元素的数据保持有序,即第一组数据"7,3,15,11"要调整为顺序,则将其看作一个代排数组,然后用直接插入排序将其调整为"3,7,11,15"的顺序,后面7组同理:

然后我们就可以得到如下数组:

         我们继续再将数组分为2组,让每隔2个元素的数据保持有序,即将第一组数据"3,1,7,5,11,9,15,13"直接插入排序,将其调整为"1,3,5,7,9,11,13,15"的顺序,第二组同理:

 然后我们就可以得到如下数组:

          然后就是最后一步,我们将数组看作一组,让相邻的两个元素的数据保持有序,即将全组数据直接插入排序,就可以得到最终结果:

至此,其实我们对直接插入排序的优化过程,就是希尔排序算法的思路.

二.希尔排序简介及思路

希尔排序(Shell Sort)是一种插入排序算法.

它的基本思想是:

  • 先选定一个整数,把待排序文件中所有数据分成gap个组,所有距离为gap的数据分在同一组内,并对每一组内的数据进行排序.
  • 重复上述分组和排序的工作,当达到gap=1时,所有数据在统一组内排好序.

算法动图演示如下:

三.希尔排序算法的代码实现

算法实现步骤:(以升序为例)

  1. 从下标为0的元素开始,遍历到下标为n-gap个元素为止,我们使用end来记录本次处理的元素下标,用tmp记录下间隔gap的元素的数值.
  2. 和间隔gap的两个元素进行比较,如果a[end+gap] < a[end],则将a[end]的值赋值给a[end+gap],并给end减掉gap.
  3. 然后无论这次有没有交换位置,都将tmp赋值给a[end+gap]的位置,如果没有交换,则a[end+gap]就是tmp原本的值,如果这次有交换,则因为end减去了gap,则会使tmp赋值给原本a[end]的位置.该部分图示如下:
  4. 当第一轮遍历完下标为n-gap的元素之后,给gap除以2,继续重复1-3步的操作.
  5. 不断重复第4步操作,直到最终gap为1,即执行直接插入排序后,本次排序完成.

搞清算法实现步骤后,代码实现就比较简单了,希尔排序代码如下:

//希尔排序(升序
void ShellSort(int* a, int n)
{int gap = n;//gap>1都是在预排序//gap==1时就是直接插入排序了while (gap > 1){gap /= 2;//嫌慢的话可以gap/=3+1.加一是要保证最后一次一定是1for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[i + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

四.希尔排序算法的时间复杂度分析

希尔排序的时间复杂度的计算是较为复杂的,我们先来看两本官方书籍对该部分的描述:

       希尔排序的分析是一个复杂的问题，因为它的时间是所取“增量”序列的函数，这涉及一些数学上尚未解决的难题。因此，到目前为止尚未有人求得一种最好的增量序列，但大量的研究已得出一些局部的结论。如有人指出，当增量序列为dlta[k]=2^{t-k+1}-1时，希尔排序的时间复杂度为O(n^{\frac{3}{2}})，其中t为排序趟数，1 \leqslant k \leqslant t \leqslant \left \lfloor log_{2}(n+1) \right \rfloor。

        还有人在大量的实验基础上推出：当n在某个特定范围内，希尔排序所需的比较和移动次数约为n^{1.3}，当n\rightarrow \infty时，可减少到n((log_{2}n)^{2})^{2}。增量序列可以有各种取法，但需注意：应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1。

                                                                 ——《数据结构(C语言版)》严蔚敏

       gap的取法有多种。最初Shell提出取gap=\left \lfloor \frac{n}{2} \right \rfloor，gap=\left \lfloor \frac{gap}{2} \right \rfloor，直到gap=1,后来Knuth提出取gap=\left \lfloor \frac{gap}{3} \right \rfloor+1。还有人提出都取奇数为好，也有人提出各gap互质为好。无论哪一种主张都没有得到证明。
        对希尔排序的时间复杂度的分析很困难，在特定情况下可以准确地估算关键码的比较次数和对象移动次数，但想要弄清关键码比较数和对象移动次教与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。在Knuth所著的《计算机程序设计技巧》第3卷中，利用大量的实验统计资料得出，当n很大时，关键码平均比较次数和对象平均移动次数大约在n^{1.25}到1.6n^{1.25}范围内，这是在利用直接插入排序作为子序列排序方法的情况下得到的。                             ——《数据结构-用面向对象方法与C++描述》殷人昆

       因此,当前对于希尔排序的时间复杂度,学术界仍没有一个确切的研究结果,我们只能在估算希尔排序时间复杂度时借助Knuth大佬的实验统计结果,即采用O(n^{1.25})到O(1.6*n^{1.25})来近似的估算希尔排序的时间复杂度.

结语

希望这篇希尔排序算法详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.

有关更多排序相关知识可以移步:

【数据结构】八大排序算法​icon-default.png?t=N7T8https://blog.csdn.net/weixin_72357342/article/details/135038495?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22135038495%22%2C%22source%22%3A%22weixin_72357342%22%7D&fromshare=blogdetail学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

相关文章推荐

【数据结构】八大排序之冒泡排序算法

【数据结构】八大排序之希尔排序算法

数据结构排序算法篇思维导图:

相关文章：

【数据结构】八大排序之希尔排序算法

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 一.优化直接插入排序算法 我们在之前对直接插入排序算法的优化部分通过对直接插入排序的分析可以得到一个结论,即: 进行直接插入排序的数组,如果越接近局部有序,则后续进行直…...

编程日记 2023/12/17 21:44:46

NestJS使用gRPC实现微服务通信

代码仓库地址&#xff1a;https://github.com/zeng-jc/rpc-grpc-practice 1.1 基本概念 gRPC 基于 Protocol Buffers&#xff08;protobuf&#xff09;作为接口定义语言&#xff08;IDL&#xff09;&#xff0c;意味着你可以使用 protobuf 来定义你的服务接口&#xff0c;gRP…...

编程日记 2023/12/17 21:43:45

Android手机使用Termux终端模拟器

Termux 是 Android 平台上的一个终端模拟器&#xff0c;可以在 Android 手机上模拟 Linux 环境。它提供命令行界面&#xff0c;并且提供了功能健全的包管理工具&#xff08;pkg&#xff09;。另外就是 Termux 不需要 root 权限&#xff0c;安装后默认产生一个用户&#xff0c;可…...

编程日记 2023/12/17 21:42:45

【Linux】cp问题，生产者消费者问题代码实现

文章目录 前言一、 BlockQueue.hpp&#xff08;阻塞队列&#xff09;二、main.cpp 前言 生产者消费者模式就是通过一个容器来解决生产者和消费者的强耦合问题。生产者和消费者彼此之间不直接通讯&#xff0c;而通过阻塞队列来进行通讯&#xff0c;所以生产者生产完数据之后不用…...

编程日记 2023/12/17 21:40:43

C++1114新标准——统一初始化（Uniform Initialization）、Initializer_list（初始化列表）、explicit

系列文章目录 C11&14新标准——Variadic templates&#xff08;数量不定的模板参数&#xff09; C11&14新标准——Uniform Initialization&#xff08;统一初始化&#xff09;、Initializer_list&#xff08;初始化列表&#xff09;、explicit 文章目录 系列文章目录1…...

编程日记 2023/12/17 21:39:42

Kubeadm 方式部署K8s集群

环境 主节点CPU核数必须是 ≥2核且内存要求必须≥2G&#xff0c;否则k8s无法启动 主机名地址角色配置kube-master192.168.134.165主节点2核4Gkube-node1192..168.134.166 工作节点2核4Gkube-node2192.168.134.163工作节点2核4G 1.获取镜像 谷歌镜像[由于国内网络原因…...

编程日记 2023/12/17 21:36:40

力扣376周赛

力扣第376场周赛 找出缺失和重复的数字 map模拟 class Solution { public:vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {int n grid.size() , m grid[0].size();map<int,int>mi;for(int i 0 ; i < n ; i ){for…...

编程日记 2023/12/17 21:35:39

SU渲染受到电脑性能影响大吗？如何提高渲染速度

一般3d设计师们在进行设计工作前都需要提供一台高配电脑&#xff0c;那么你这知道su渲染对电脑要求高吗&#xff1f;电脑带不动su怎么解决&#xff1f;su对电脑什么配件要求高&#xff1f;今天这篇文章就详细为大家带来电脑硬件对su建模渲染的影响&#xff0c;以及su渲染慢怎么…...

编程日记 2023/12/17 21:33:38

Docker - Android源码编译与烧写

创建源代码 并挂载到win目录 docker run -v /mnt/f/android8.0:/data/android8.0 -it --name android8.0 49a981f2b85f /bin/bash 使用 docker update 命令动态调整内存限制&#xff1a; 重新运行一个容器 docker run -m 512m my_container 修改运行中容器 显示运行中容器 d…...

编程日记 2023/12/17 21:32:37

股票价格预测 | Python实现基于ARIMA和LSTM的股票预测模型（含XGBoost特征重要性衡量）

文章目录 效果一览文章概述模型描述源码设计效果一览 文章概述 Python实现基于ARIMA和LSTM的股票预测模型（Stock-Prediction） Data ExtractionFormatting data for time seriesFeature engineering（Feature Importance using X...

编程日记 2023/12/17 21:30:35

Base64

1. Base64是什么&#xff1f; Base64&#xff08;基底64&#xff09;是一种基于64个可打印字符来表示二进制数据的表示方法。每6个比特为一个单元&#xff0c;对应某个可打印字符。3个字节相当于24个比特&#xff0c;对应于4个Base64单元&#xff0c;即3个字节可由4个可打印字…...

编程日记 2023/12/17 21:28:34

二叉搜索树的简单C++类实现

二叉搜索树&#xff08;BST&#xff09;是一种重要的数据结构&#xff0c;它对于理解树的操作和算法至关重要&#xff0c;其中序输出是有序的。本文通过C实现一个BST的类&#xff0c;并在插入和删除节点时提供清晰的输出&#xff0c;可视化这些操作的过程。 二叉搜索树的节点结…...

编程日记 2023/12/17 21:26:32

禁毒知识竞赛流程和规则

禁毒知识竞赛是一项全国性竞赛活动。有着深化全国青少年毒品预防教育&#xff0c;巩固学校毒品预防教育成果的重要作用。本文介绍一场禁毒知识竞赛的完整流程和规则&#xff0c;供单位组织此类活动时参考。 1、赛制 第一轮10进6&#xff0c;第二轮6进4&#xff0c;4支队伍决出…...

编程日记 2023/12/17 21:25:31

CSS 基础

文章目录 CSS 常见的属性CSS 常见样式行内样式内嵌样式导入样式 CSS 选择器标签选择器id选择器类选择器全局选择器属性选择器组合选择器 CSS 常见应用表格列表导航栏下拉菜单提示工具图片廊 CSS (Cascading Style Sheets&#xff0c;层叠样式表&#xff09;&#xff0c;是一种用…...

编程日记 2023/12/17 21:22:29

黑色翻页时钟HTML源码-倒计时单页翻页时钟

黑色翻页时钟HTML源码-倒计时单页翻页时钟这是一个类似fliqlo的黑色翻页时钟HTML源码&#xff0c;它仅包含一个HTML文件&#xff0c;上传到网站后即可使用。该时钟具有查看当前时间、秒表和倒计时功能&#xff0c;并且可以在页面的右下角进行设置。 红色动态炫酷数字时钟html网…...

编程日记 2023/12/17 21:21:27

2043杨辉三角（C语言）

目录 一&#xff1a;题目 二&#xff1a;思路分析 三&#xff1a;代码 一&#xff1a;题目 二&#xff1a;思路分析 1.通过杨辉三角&#xff0c;不难发现中间的数等于肩头两个数之和 2.但是当我们的输出结果&#xff0c;与杨辉三角的形式有所不同&#xff0c;但是我们可以找…...

编程日记 2023/12/17 21:19:26

【机器学习】从底层手写实现线性回归

【机器学习】Building-Linear-Regression-from-Scratch 线性回归 Linear Regression0. 数据的导入与相关预处理0.工具函数1. 批量梯度下降法 Batch Gradient Descent2. 小批量梯度下降法 Mini Batch Gradient Descent&#xff08;在批量方面进行了改进&#xff09;3. 自适应梯度…...

编程日记 2023/12/17 21:18:25

判断数组中对象的某个值是否有相同的并去重

如果你想判断数组中对象的某个值是否有相同的&#xff0c;并进行去重&#xff0c;你可以使用 JavaScript 中的一些数组方法和 Set 对象。以下是一个示例&#xff1a; // 原始数组包含对象 const array [{ id: 1, name: John },{ id: 2, name: Jane },{ id: 3, name: Doe },{ …...

编程日记 2023/12/17 21:17:23

Shell脚本 变量 语句 表达式

常见的解释器 #!/bin/sh #不推荐(了解) #!/bin/bash #!/usr/bin/python #!/bin/awk#!后跟的字符表示要启动的程序&#xff0c;该程序读取该文件执行。 #! 是一个约定的标记&#xff0c;它告诉系统这个脚本需要什么解释器来执行shell 函数 myShellName () {command1 }函数调用…...

编程日记 2023/12/17 21:16:22

MIT6.S081-实验准备

实验全程在Vmware虚拟机 (镜像&#xff1a;Ubuntu-20.04-beta-desktop-amd64) 中进行 一、版本控制 1.1 将mit的实验代码克隆到本地 git clone git://g.csail.mit.edu/xv6-labs-2020 1.2 修改本地git配置文件 创建github仓库&#xff0c;记录仓库地址 我的仓库地址就是htt…...

编程日记 2023/12/17 21:14:20

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

编程新知 2025/6/21 16:23:04

Qwen3-Embedding-0.6B深度解析：多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

编程新知 2025/8/15 19:59:33

Neo4j 集群管理：原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档，本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石，用于构建高可用、可扩展且一致的图数据库服务…...

编程新知 2025/7/4 0:49:28

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

编程新知 2025/8/5 6:58:34

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

编程新知 2025/8/22 3:33:58

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

编程新知 2025/8/21 23:03:46

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

编程新知 2025/8/22 5:19:55

【深度学习新浪潮】什么是credit assignment problem？

Credit Assignment Problem（信用分配问题） 是机器学习，尤其是强化学习（RL）中的核心挑战之一，指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中，智能体执行一系列动作后获得一个最终奖励，但每个动作对最终结果的贡献程度往往…...

编程新知 2025/8/22 7:01:50

2.3 物理层设备

在这个视频中&#xff0c;我们要学习工作在物理层的两种网络设备&#xff0c;分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间&#xff0c;需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质&#xff0c;假设A节点要给…...

编程新知 2025/8/22 2:26:44

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...

编程新知 2025/8/21 18:25:03