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

希尔排序(C语言实现)

目录

1.希尔排序( 缩小增量排序 )

2.动图 ​编辑

3.代码实现

预排序实现 

子序列排列实现

单趟排序实现

对整组数进行子排序

希尔排序代码

代码测试 

 时间复杂度分析

希尔排序的特性总结:


1.希尔排序( 缩小增量排序 )

基本思想:

1.先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并     对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重     复上述操作…
2.当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。

2.动图 

3.代码实现

思路:

预排序实现

插入排序

预排序实现 

根据当前增量,数组被分为若干子序列,这些子序列的元素在原数组中间隔着固定的增量。对每个子序列应用插入排序。

假设最初增量为5

d越大,数据挪动得越快;d越小,数据挪动得越慢。前期让d较大,可以让数据更快得移动到自己对应的位置附近,减少挪动次数。

注:一般情况下,取序列的一半作为增量,然后依次减半,直到增量为1(也可自己设置)。

 完成了一轮希尔排序,此时整个数组并不完全有序,但是已经比原始的数组更接近有序了。然后减小增量,通常是将原来的增量除以2(或者除以3+1),现在选择下一个增量为 2,按照此排序规则继续预排序即可,直到增量为1时,则为直接插入排序,此时则排序完成。

子序列排列实现

//子序列int gap;int end;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + 3] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;

 这里只需要在插入排序的基础上修改一下即可。end的所加所减都为gap;

单趟排序实现

int gap;//单趟排序实现for (int i = 0; i < n - gap; i += gap){//子序列int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + 3] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}

 这里的 n-gap 和插入排序中的 n-1 一样是为了防止越界

对整组数进行子排序

int gap;for (int j = 0; j < gap; j++){//单趟排序实现for (int i = 0; i < n - gap; i += gap){//子序列int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + 3] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}

外层循环(for (int j = 0; j < gap; j++))意在对每个以gap为间隔的分组进行遍历。

 这里进行一下优化:

三层代码的循环是每一组子排序排完再进行下一组,直到排完整个数组。

下面这组代码优化后效率并没有很大的提升,只是代码更为简洁。

这组代码是齐头并进,排完第一组的前n个就排下一组了,并没有把第一组全部排完。

int gap;for (int i = 0; i < n - gap; i++){//子序列int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + 3] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}

 

希尔排序代码

分析

gap越大,大的值更快调到后面,小的值更快调到前面,越不接近有序。
gap越小,大的值更慢调到后面,小的值更慢调到前面,越接近有序。
当gap为1,就是直接插入排序。
 

所以我们这里的gap值应该是在变化的,一般我们随n变化,取gap = gap/3+1,或者gap  = gap/2;

void ShellSort(int* a,int n)
{int gap = n;while (gap>1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){//子序列int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

 这里无论gap是奇数还是偶数,这里gap最终都会除以到值为1。

 gap>1时是预排序,目的让其接近有序。
gap=1时是直接插入排序,目的让其有序。
在gap=1时,已经十分接近有序了

代码测试 

 时间复杂度分析

希尔排序的时间复杂度并不固定,它依赖于所选择的间隔序列(增量序列)。直到今天,已经有多种不同的间隔序列被提出来,每种都有自己的性能特点。

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

 《数据结构-用面相对象方法与C++描述》--- 殷人昆

 因为咋们的gap是按照Knuth提出的方式取值的,而且Knuth进行了大量的试验统计,我们暂时就按照:O(N^1.25) 到  O(1.6* N^1.25) 来算。

希尔排序的特性总结:

时间复杂度:O(N²)

空间复杂度:O(1)

稳定性:不稳定

复杂性:简单



如有错误,请指正 

 

相关文章:

希尔排序(C语言实现)

目录 1.希尔排序( 缩小增量排序 ) 2.动图 ​编辑 3.代码实现 预排序实现 子序列排列实现 单趟排序实现 对整组数进行子排序 希尔排序代码 代码测试 时间复杂度分析 希尔排序的特性总结&#xff1a; 1.希尔排序( 缩小增量排序 ) 基本思想&#xff1a; 1.先选定一个…...

LLVM 中的Value、User、Use设计

概述 LLVM是一个强大的编译器基础设施&#xff0c;提供了一套丰富的库&#xff0c;用于构建编译器的前端和后端。在LLVM中&#xff0c;Value、User和Use是几个核心的概念&#xff0c;它们之间有着紧密的关系 Value Value是LLVM中表示所有可计算的值的基类&#xff0c;例如常…...

C++智能指针入门教程(C++11)

智能指针 1.定义 ​ C中的智能指针是一种用于自动管理动态分配的内存的模板类&#xff0c;它们通过封装原始指针来提供自动的内存管理功能&#xff0c;从而避免了内存泄漏和悬挂指针等问题。C标准库中提供了几种智能指针类型&#xff0c;其中最常用的是std::unique_ptr、std:…...

常用工具推荐!分享7款AI论文修改软件工具网站

在当今学术研究和写作领域&#xff0c;AI论文修改软件工具已经成为了不可或缺的助手。这些工具不仅能够帮助研究人员提高写作效率&#xff0c;还能确保论文的质量和原创性。以下是七款值得推荐的AI论文修改软件工具网站&#xff0c;其中特别推荐千笔-AIPassPaper。 1. 千笔-AI…...

怎么解除BitLocker对磁盘的加密?

BitLocker是一种Windows操作系统内置的加密功能&#xff0c;用于保护用户的数据安全。它通过对整个磁盘进行加密&#xff0c;防止数据被未经授权的用户访问。BitLocker主要用于保护笔记本电脑和台式机中的重要数据&#xff0c;尤其是在设备丢失或被盗的情况下。怎么解除BitLock…...

群晖使用Docker部署WPS Office并实现异地使用浏览器制作办公文档

文章目录 前言1. 本地环境配置2. 制作本地分享链接3. 制作公网访问链接4. 公网ip地址访问您的分享相册5. 制作固定公网访问链接 前言 想象一下这个场景&#xff1a;如果遇到周末紧急需要改方案&#xff0c;但团队成员都在各自家中&#xff0c;这个时候如果大家能够轻松访问这个…...

Unity3d 以鼠标位置点为中心缩放视角(正交模式下)

思路整理&#xff1a; 缩放前&#xff1a; 缩放后&#xff1a; 记录缩放前鼠标的屏幕坐标 A&#xff0c;计算鼠标位置对应的世界坐标 A_world 缩放完成后&#xff0c;根据当前屏幕下A所对应的世界坐标A1_world 计算A1_world 和 A_world 的偏移量 移动摄像机 代码&#xff…...

Git清除某文件所有历史提交记录

一、软件要求 1.1 软件版本要求 git > 2.22.0python3 > 3.5 1.2 辅助插件 git filter-repo Linux/macOS # Debian/Ubuntu 系统 # 或使用 pip 安装pip install git-filter-repo sudo apt install git-filter-repo Windows pip install git-filter-repo二、操作步骤…...

jacoco生成单元测试覆盖率报告

前言 单元测试是日常编写代码中常用的&#xff0c;用于测试业务逻辑的一种方式&#xff0c;单元测试的覆盖率可以用来衡量我们的业务代码经过测试覆盖的比例。 目前市场上开源的单元测试覆盖率的java插件&#xff0c;主要有Emma&#xff0c;Cobertura&#xff0c;Jacoco。具体…...

【CSS Tricks】如何做一个粒子效果的logo

效果展示 代码展示 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>粒子效果Logo</title>…...

如何使用ssm实现基于Javaweb的网上花店系统的设计与实现

TOC ssm653基于Javaweb的网上花店系统的设计与实现jsp 研究背景 自计算机发展以来给人们的生活带来了改变。第一代计算机为1946年美国设计&#xff0c;最开始用于复杂的科学计算&#xff0c;占地面积、开机时间要求都非常高&#xff0c;经过数十几的改变计算机技术才发展到今…...

Elastic 的 OpenTelemetry PHP 发行版简介

作者&#xff1a;Pawel Filipczak 宣布 OpenTelemetry PHP 的 Elastic 发行版的第一个 alpha 版本。在本篇博文中了解使用 OpenTelemetry 来检测 PHP 应用程序是多么简单。 我们很高兴推出 OpenTelemetry PHP 的 Elastic Distribution 的第一个 alpha 版本。在这篇文章中&…...

TCP 和 UDP 协议的区别?

参考TCP 和 UDP的区别_tcp和udp的区别-CSDN博客...

【PHP】使用thinkphp5查询最大值时,把varchar类型字段转换成数字

有时候我们需要把carchar类型的字段进行聚合函数运运行&#xff08;max、min、avg&#xff09;&#xff0c;但是如果直接用聚合函数&#xff0c;得到的结果是错误的&#xff0c;因为varchar字段是字符串&#xff0c;无法直接使用聚合函数&#xff0c;所以需要把varchar字段转换…...

Java 正则表达式详解

正则表达式 (Regular Expression&#xff0c;简称 regex) 是一种强大的文本处理工具&#xff0c;可以用来匹配、搜索和替换文本中的特定模式。在 Java 中&#xff0c;正则表达式由 java.util.regex 包提供支持。 1. 理解正则表达式语法 正则表达式使用特殊的字符和符号来定义…...

MySQL篇(窗口函数/公用表达式(CTE))(持续更新迭代)

目录 讲解一&#xff1a;窗口函数 一、简介 二、常见操作 1. sumgroup by常规的聚合函数操作 2. sum窗口函数的聚合操作 三、基本语法 1. Function(arg1,..., argn) 1.1. 聚合函数 sum函数&#xff1a;求和 min函数 &#xff1a;最小值 1.2. 排序函数 1.3. 跨行函数…...

Jira Cloud涨价5%-20%,钉钉项目Teambition成优选替代

近日&#xff0c;Jira再次宣布涨价&#xff0c;Cloud版涨幅达到5%-20%&#xff0c;这一消息来源于Atlassian官方面向合作伙伴发布的2024年最新涨价通知。 Atlassian旗下核心产品&#xff0c;包括Jira、Confluence、JiraServiceManagement等的Cloud版本价格将有所提高&#xff…...

Python语言基础教程(下)4.0

✨博客主页&#xff1a; https://blog.csdn.net/m0_63815035?typeblog &#x1f497;《博客内容》&#xff1a;.NET、Java.测试开发、Python、Android、Go、Node、Android前端小程序等相关领域知识 &#x1f4e2;博客专栏&#xff1a; https://blog.csdn.net/m0_63815035/cat…...

【HTTP】构造HTTP请求和状态码

状态码 用于响应中&#xff0c;表示响应的结果如何 正确&#xff1f;错误&#xff1f;什么原因&#xff1f; HTTP 中的状态码都是标准约定好的 200 OK 成功了&#xff0c;一切顺利 在抓包到的响应中 404 Not Found 访问的资源&#xff08;URL 中的路径&#xff09;没找…...

Delta Lake如何使用

1. 安装 Java 确保你的系统上安装了 Java 8 或更高版本。可以通过以下命令检查 Java 是否已安装&#xff1a; java -version2. 安装 Apache Spark 下载 Spark&#xff1a; 从 Apache Spark 官方网站 下载适合的版本&#xff0c;建议下载预编译的版本&#xff08;例如&#xf…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...