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

插入排序和希尔排序

目录

  • 1.直接插入排序
  • 2.希尔排序

1.直接插入排序

基本思想:
把待排序的数据按其大小逐个插入到一个已经排好序的有序序列中,直到所有的数据插入完成为止。

当插入第i个元素时,前面的a[0],a[1],...,a[i-1]个数据已经排好序了,此时用a[i]a[i-1],a[i-2],...进行比较,找到插入位置就将a[i]插入,原来位置上的元素顺序后移

在这里插入图片描述

void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){int end = i;//记录已经有序的数据的最后一个数据的下标int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else//a[end]<tmp,说明前(i+1)个数已经有序了{break;}}a[end + 1] = tmp;}
}

在这里插入图片描述

元素集合月接近有序,直接插入排序算法的时间效率更高
时间复杂度:O(N^2)
稳定性:稳定

2.希尔排序

希尔排序是直接插入排序的优化

1.预排序
2.直接插入排序
基本思想:
先选定一个整数,把待排序文件中所有数据分成gap个组,所有距离为gap的数据分在同一个组里,并对每一组的数据进行排序。然后,取gap=gap/3+1,重复上述分组的操作。当gap=1时,所有数据在同一组的已经排好序了

void ShellSort(int* a, int n)
{int gap = n;while(gap > 1){//+1保证最后一个gap一定是1//gap》1是预排序//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 (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

在这里插入图片描述
在这里插入图片描述

当gap>1时都是预排序,目的是让数组更接近有序。当gap==1时,数组已经接近有序了,这样就会很快
时间复杂度:O(N^1.3)(ps:时间复杂度是不固定的)
稳定性:不稳定

相关文章:

插入排序和希尔排序

目录 1.直接插入排序2.希尔排序 1.直接插入排序 基本思想&#xff1a; 把待排序的数据按其大小逐个插入到一个已经排好序的有序序列中&#xff0c;直到所有的数据插入完成为止。 当插入第i个元素时&#xff0c;前面的a[0],a[1],...,a[i-1]个数据已经排好序了&#xff0c;此时用…...

Java web应用性能分析之【java进程问题分析定位】

Java web应用性能分析之【java进程问题分析概叙】-CSDN博客 Java web应用性能分析之【java进程问题分析工具】-CSDN博客 Java web应用性能分析之【jvisualvm远程连接云服务器】-CSDN博客 由于篇幅限制、前面三篇讲了准备工作和分析小结&#xff0c;这里将详细操作java进程问题…...

c#控件笔记

c# PictureBox在工具箱的哪个位置 在 Visual Studio 的工具箱中&#xff0c;PictureBox 控件位于 “Common Controls” 部分。要找到 PictureBox&#xff0c;请按照以下步骤操作&#xff1a; 打开 Visual Studio 并加载您的项目。确保已经打开了设计器视图&#xff08;即您的…...

STM32-15-DMA

STM32-01-认识单片机 STM32-02-基础知识 STM32-03-HAL库 STM32-04-时钟树 STM32-05-SYSTEM文件夹 STM32-06-GPIO STM32-07-外部中断 STM32-08-串口 STM32-09-IWDG和WWDG STM32-10-定时器 STM32-11-电容触摸按键 STM32-12-OLED模块 STM32-13-MPU STM32-14-FSMC_LCD 文章目录 STM…...

Go语言 几种常见的IO模型用法 和 netpoll与原生GoNet对比

【go基础】16.I/O模型与网络轮询器netpoller_go中的多路io复用模型-CSDN博客 字节开源的netPoll多路复用器源码解析-CSDN博客 一、几种常见的IO模型 1. 阻塞I/O (1) 解释&#xff1a; 用户调用如accept、read等系统调用&#xff0c;向内核发起I/O请求后&#xff0c;应用程序…...

大米cms安装支付逻辑漏洞

1.安装 下载来源&#xff1a;https://www.cnblogs.com/xfbk/p/17910054.html 链接&#xff1a;https://pan.baidu.com/s/1b-Z6RaFBZ6CsSIErY46Pyg?pwdq8qq 提取码&#xff1a;q8qq 注意一下配置就可以了&#xff1a;php5.5apachemysql5.0&#xff0c;主要就是数据库版本要注…...

使用 zxing 生成二维码以及条形码

需求背景 前期在做项目的时候&#xff0c;有一个需求是说要生成一张条形码&#xff0c;并且呢将条形码插入到 excel 中去&#xff0c;但是之前一直没有搞过找个条形码或者是二维码&#xff0c;最后是做出来了&#xff0c;这里呢就先看看怎么生成&#xff0c;后面再抽时间来写写…...

发布 jar 包到 maven 中央仓库

目前开发基本都是以maven或者gradle的方式,直接引入依赖包即可,那么该咋那么发布我们自己的jar包到maven仓库,让别人使用呢?本文适用于2024.3之后的步骤 文章目录 账号准备第一步,注册账号第二步,新建命名空间第三步,验证命名空间第四步,创建 push 的账号和密码点击右…...

AI智能体研发之路-模型篇(四):一文入门pytorch开发

博客导读&#xff1a; 《AI—工程篇》 AI智能体研发之路-工程篇&#xff08;一&#xff09;&#xff1a;Docker助力AI智能体开发提效 AI智能体研发之路-工程篇&#xff08;二&#xff09;&#xff1a;Dify智能体开发平台一键部署 AI智能体研发之路-工程篇&#xff08;三&am…...

英语口语中though的用法(even though、as though)

文章目录 英语口语中 "though" 的用法详解1. "Though" 作为转折连词的用法1.1 基本用法示例句子&#xff1a; 1.2 位置灵活性示例句子&#xff1a; 2. "Though" 作为副词的用法2.1 表示对比或转折示例句子&#xff1a; 2.2 强调前述观点示例句子…...

菜刀冰蝎哥斯拉流量通讯特征绕过检测反制感知

1.加密流程 工具名称requestsresponseAntSwordbase64等方式明文冰蝎2.0开启Openssl扩展-动态密钥aes加密aes加密base64未开启Openssl扩展-异或异或base64冰蝎3.0开启Openssl扩展-静态密钥aes加密aes加密base64未开启Openssl扩展-异或异或base64哥斯拉php的为base64异或base64异…...

前端 JS 经典:判断数组的准确方法

前言&#xff1a;判断数组的方法有很多&#xff0c;但是最完美的只有一个。 1. Object.prototype.toString.call 通过 toString.call 方法来判断是否数组。 function isArray(obj) {return Object.prototype.toString.call(obj) "[object Array]"; } 缺点&#…...

【仓库设置问题】

问题&#xff1a; 某公司在高速公路一些服务站内开设了百货超市&#xff0c;为了能及时给这些百货超市提供足够的商品&#xff0c;他们需要在一些百货超市旁修建仓库。一个仓库可以同时为多家百货超市提供服务&#xff0c;以满足各个超市对商品的需求。现已知这些百货超市在高…...

深度学习知识与心得

目录 深度学习简介 传统机器学习 深度学习发展 感知机 前馈神经网络 前馈神经网络&#xff08;BP网络&#xff09; 深度学习框架讲解 深度学习框架 TensorFlow 一个简单的线性函数拟合过程 卷积神经网络CNN&#xff08;计算机视觉&#xff09; 自然语言处理NLP Wo…...

Qt for Android

文章 USB Qt for android 获取USB设备列表&#xff08;一&#xff09;Java方式 获取 Qt for android 获取USB设备列表&#xff08;二&#xff09;JNI方式 获取 Qt for android 串口库使用 Qt for android : libusb在android中使用 Qt for Android : 使用libusb做CH340x串口传…...

HTTP 的三次握手

​​​​​ HTTP 的三次握手是指在建立 TCP 连接时&#xff0c;客户端和服务器之间进行的三步握手过程。这个过程确保了双方都能够互相通信&#xff0c;并且同步了彼此的序列号和确认号。 概念&#xff1a; 第一次握手&#xff1a;客户端发送一个 SYN&#xff08;同步…...

【Text2SQL 论文】T5-SR:使用 T5 生成中间表示来得到 SQL

论文&#xff1a;T5-SR: A Unified Seq-to-Seq Decoding Strategy for Semantic Parsing ⭐⭐⭐ 北大 & 中科大&#xff0c;arXiv:2306.08368 文章目录 一、论文速读二、中间表示&#xff1a;SSQL三、Score Re-estimator四、总结 一、论文速读 本文设计了一个 NL 和 SQL 的…...

【HarmonyOS】应用屏蔽截屏和录屏

【HarmonyOS】应用屏蔽截屏和录屏 一、问题背景&#xff1a; 金融类或者高密性质的应用APP&#xff0c;对于截屏和录屏场景&#xff0c;某些业务下是禁止不允许。 目前这种场景的需求也是非常有必要的&#xff0c;很多电诈都是通过远程录屏软件&#xff0c;获取到账户密码或者…...

[BUG历险记] ERROR: [SIM 211-100] CSim failed with errors

问题重现 在开发HLS过程中&#xff0c;我碰到一个奇怪的现象&#xff0c;同样的工程&#xff0c;在我重装完系统后&#xff0c;不能进行C仿真了&#xff0c;但是综合实现都是可以正常运作的。 vitis的报错也非常奇怪&#xff0c;单单一行&#xff1a; ERROR: [SIM 211-100] C…...

Redis中大Key与热Key的解决方案

原文地址&#xff1a;https://mp.weixin.qq.com/s/13p2VCmqC4oc85h37YoBcg 在工作中Redis已经成为必备的一款高性能的缓存数据库&#xff0c;但是在实际的使用过程中&#xff0c;我们常常会遇到两个常见的问题&#xff0c;也就是文章标题所说的大 key与热 key。 一、定义 1.1…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...