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

希尔排序和直接插入排序

因为排序这些比较复杂点我就分几期给大家来讲~~~

直接插入排序

直接插入排序是一种简单的排序算法,主要用于对少量数据进行排序。其基本思想是将待排序的元素逐个插入到已经排好序的部分中,从而形成一个有序序列。

具体步骤如下:

  1. 初始化:将数组分为已排序和未排序两部分,开始时已排序部分只有一个元素。
  2. 遍历未排序部分:从未排序部分取出一个元素(称为“关键元素”),然后与已排序部分的元素进行比较。
  3. 插入:找到合适的位置,将关键元素插入到已排序部分,保持其有序性。
  4. 重复:重复步骤2和3,直到未排序部分的元素全部插入到已排序部分。

特点:

  • 时间复杂度:最坏情况为O(n^2),最好情况为O(n)(当数组已经基本有序时)。
  • 空间复杂度:O(1),因为只需要常量空间来存放关键元素。
  • 稳定性:是稳定排序,两个相等的元素在排序后相对位置不变。

直接插入排序适合小规模数据的排序,且在数据基本有序时效率较高。

当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移

#include <stdio.h>// 直接插入排序函数
void InsertionSort(int* arr, int n) {int i, key, j;for (i = 1; i < n; i++) {key = arr[i];j = i - 1;// 将 arr[i] 插入到已排序的序列 arr[0...i-1] 中的正确位置while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}
}// 打印数组函数
void PrintArray(int* arr, int n) {int i;for (i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {283571469};int n = sizeof(arr) / sizeof(arr[0]);printf("Original array:\n");PrintArray(arr, n);InsertionSort(arr, n);printf("Sorted array:\n");PrintArray(arr, n);return 0;
}

在这里插入图片描述

希尔排序

希尔排序是一种基于插入排序的排序算法,也被称为递减增量排序。它通过将待排序数组分成多个子数组,使每个子数组中的元素进行插入排序,从而提高排序效率。其基本思路是通过选择一个增量序列,将待排序数组分组进行排序。

具体步骤如下:

  1. 选择增量:首先选择一个增量(也叫“间隔”),通常是整个数组长度的一半,然后逐步减小增量,直到增量为1。
  2. 分组排序:根据当前增量,将数组分成若干个子数组,对每个子数组进行插入排序。
  3. 重复:继续减少增量,并对新的分组进行插入排序,直到增量为1,此时对整个数组进行一次插入排序。

特点:

  • 时间复杂度:平均和最坏情况下的时间复杂度为O(n(1.5))到O(n2),而最好情况下为O(n log n),具体表现取决于增量序列的选择。
  • 空间复杂度:O(1),因为只需常量级的辅助空间。
  • 稳定性:希尔排序一般不稳定,可能改变相同元素的相对位置。

希尔排序相较于简单的插入排序在性能上有显著提升,适合中等规模的数据排序。

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

希尔排序的特性总结

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就
    会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的
    希尔排序的时间复杂度都不固定:
    《数据结构(C语言版)》— 严蔚敏
    在这里插入图片描述
    《数据结构-用面相对象方法与C++描述》— 殷人昆
    在这里插入图片描述
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){// +1保证最后一个gap一定是1// gap > 1时是预排序// gap == 1时是插入排序gap = gap / 3 + 1;for (size_t 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;}}
}

在这里插入图片描述
那我们下期再见啦
~冒泡选择以及快排
在这里插入图片描述

相关文章:

希尔排序和直接插入排序

因为排序这些比较复杂点我就分几期给大家来讲~~~ 直接插入排序 直接插入排序是一种简单的排序算法&#xff0c;主要用于对少量数据进行排序。其基本思想是将待排序的元素逐个插入到已经排好序的部分中&#xff0c;从而形成一个有序序列。 具体步骤如下&#xff1a; 初始化&…...

IDEA 配置 Git 详解

本文将介绍在IntelliJ IDEA 中如何配置Git 没有安装配置 Git 的可以参考我的这篇文章&#xff1a;安装配置 Git 一、操作环境及准备 1.win 10 2.已安装且配置了Git 3.有Gitee账户 4.安装了IntelliJ IDEA 2023.2.1 5.全程联网 二、配置步骤 2.1 配置git 1.采用全局设置&…...

Docker 部署 Redis 监控系统实战:Redis Exporter 与 Prometheus 完整配置指南

Docker 部署 Redis 监控系统实战&#xff1a;Redis Exporter 与 Prometheus 完整配置指南 文章目录 Docker 部署 Redis 监控系统实战&#xff1a;Redis Exporter 与 Prometheus 完整配置指南一 缓存简述二 redis exporter 部署三 环境变量配置四 修改文件权限五 验证 exporter …...

高级算法设计与分析-MaxFlow网络流基础知识

MaxFlow网络流 1 网络流基础概念 source:源点 sink:终点 Flow:流量 capacity:容量 Residual:残量 Residual Network:残量网络 Augmenting path:增广路径,表示从源点 s 到终点 t 不包含环的路径 Bottleneck capacity:瓶颈容量 2 最大流 2.1 基础概念 2.2 增广路算法 …...

Java项目实战II基于Java+Spring Boot+MySQL的桂林旅游景点导游平台(源码+数据库+文档)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者 一、前言 桂林&#xff0c;以其独特的喀斯特地貌、秀美的自然风光闻名遐迩&#xff0c;每年吸引着无数国内外游…...

C语言-输入输出

实验一&#xff1a;编写一个输出两行自定义字符的 C 程序 一、实验目的 熟悉 C 语言的基本结构和语法。掌握 printf() 函数的使用方法。了解在 Code::Blocks 中编写、编译和运行程序的过程。 二、实验内容 编写一个 C 程序&#xff0c;要求输出两行字符&#xff0c;内容自定…...

如何在GitHub上传自己的项目?(一文看懂,每一步的操作和解决常见错误的方法)

目录 步骤一&#xff1a;准备 Git 环境 1. 安装 Git 2. 配置 Git 步骤二&#xff1a;在 GitHub 创建一个新的仓库 1. 登录到你的 GitHub 账号。 2. 点击右上角的 号&#xff0c;然后选择 New repository。 3. 填写以下信息&#xff1a; 步骤三&#xff1a;将本地项目上…...

数据结构_day1

目录 大纲 1.数据结构基础知识 1.1 什么是数据结构 1.2 数据 1.3 逻辑结构 1.4 存储结构 1.4.1 顺序存储 1.4.2 链式存储 1.4.3 索引存储结构 1.4.4 散列存储 1.5 操作 2.算法基础知识 2.1 什么是算法 2.2 算法的设计 2.3 算法的特性 2.4 评价算法的好坏 大纲 数据结构、算法(理…...

c# using 声明进行资源管理

在 C# 8 中&#xff0c;using 声明引入了一种新的语法&#xff0c;称为 using 声明&#xff0c;它使得开发人员在处理资源时的代码更加简洁和清晰。主要的变化包括 使用声明 和 使用上下文&#xff08;using declaration&#xff09; 的引入。 使用语句的简化 在 C# 8 中&…...

Kafka之基本概念

1、Kafka是什么&#xff1f; Kafka是由Scala语言开发的一个多分区、多副本&#xff0c;基于Zookeeper集群协调的系统。 那这个所谓的系统又是什么系统呢&#xff1f; 回答这个问题要从发展的角度来看&#xff1a;起初Kafka的定位是分布式消息系统。但是目前它的定位是一个分布…...

倪师学习笔记-天纪-斗数简介

一、学习过程 学习->验证->思考 二、算命方法 算命方法特点铁板神数适合核对六亲子平法准确度一般紫微斗数天文地理融合最好&#xff0c;批六亲不准&#xff0c;配合相可以提升准确率 三、果 天地人三者一起影响果&#xff0c;天时地利人和促成成功1/31/31/31算命部…...

Python酷库之旅-第三方库Pandas(143)

目录 一、用法精讲 646、pandas.Timestamp.is_quarter_start属性 646-1、语法 646-2、参数 646-3、功能 646-4、返回值 646-5、说明 646-6、用法 646-6-1、数据准备 646-6-2、代码示例 646-6-3、结果输出 647、pandas.Timestamp.is_year_end属性 647-1、语法 647…...

细说QT各种线程锁的特点和用法

文章目录 QMutex特点用法QReadWriteLock特点用法QSemaphore特点用法QWaitCondition特点用法在Qt框架中,提供了多种线程同步机制,包括互斥锁(Mutex)、读写锁(Read-Write Lock)、信号量(Semaphore)和条件变量(Wait Conditions)。这些机制用于处理多线程编程中的数据一致性和线程…...

Caffeine+Redis两级缓存架构

CaffeineRedis两级缓存架构 在高性能的服务项目中&#xff0c;我们一般会将一些热点数据存储到 Redis这类缓存中间件中&#xff0c;只有当缓存的访问没有命中时再查询数据库。在提升访问速度的同时&#xff0c;也能降低数据库的压力。 但是在一些场景下单纯使用 Redis 的分布…...

kafka和zookeeper单机部署

安装kafka需要jdk和zookeeper环境&#xff0c;因此先部署单机zk的测试环境。 zookeeper离线安装 下载地址&#xff1a; zookeeper下载地址&#xff1a;Index of /dist/zookeeper 这里下载安装 zookeeper-3.4.6.tar.gz 版本&#xff0c;测试环境单机部署 上传服务器后解压缩 …...

别了,公有云!下云迁移真的是大趋势么?

【科技明说 &#xff5c; 科技热点关注】 不知道你们还有没有印象&#xff0c;早在2022年&#xff0c;IBM发布了《IBM 企业转型指数&#xff1a;云现状》中也反映了这一趋势&#xff1a;80%的企业已经考虑或正在考虑将已经部署到公有云上的工作负载迁回私有的基础设施。 然而&…...

网关在不同行业自动化生产线的应用

网关在不同行业自动化生产线的应用&#xff0c;展示了其作为信息与物理世界交汇点的广泛影响力&#xff0c;尤其在推动行业智能化、自动化方面发挥了不可估量的作用。以下是网关技术在污水处理、智慧农业、智慧工厂、电力改造及自动化控制等领域的深入应用剖析。 1. 污水处理 …...

C++ socket编程(1)

这里是一个socket编程Demo&#xff0c;不考虑出错情况&#xff0c;代码简单&#xff0c;便于了解socket流程。 Demo分为服务器程序和客户端程序&#xff0c;运行需要先启动服务器程序&#xff0c;再启动客户端程序。 服务器会等待连接&#xff0c;客户端连接后&#xff0c;服…...

C# 文件夹类的实现与文件属性处理

在现代软件开发中&#xff0c;处理文件和文件夹是非常常见的任务。 C# 提供了丰富的类库来操作这些文件系统的基本元素。本篇文章将探讨如何在 C# 中实现一个简单的文件夹类&#xff0c;以及如何获取文件名、文件路径、大小和创建日期等文件属性。 一、使用 System.IO 命…...

基于SSM框架和Layui的学院课程安排系统的设计与实现(源码+定制+定制)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...