插入排序算法(C语言版)

直接插入排序

插入排序(insert sort)是一种简单的排序算法,它的工作原理与手动整理一副牌的过程非常相似。

具体来说,我们在未排序区间选择一个基准元素,将该元素与其左侧已排序区间的元素逐一比较大小,并将该元素插入到正确的位置。

代码示例

void insert_sort(int* arr,int n)
{for (int i = 0; i < n - 1; ++i){//将end+1的数据插入到[0.end]的有序区间int end = i;int tmp = arr[end + 1];while (end >= 0){if (tmp < arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}

性能分析

  • 时间复杂N^2)
  • 空间复杂度:O(1)

希尔排序

希尔排序(Shell Sort)是插入排序的一种,它是针对直接插入排序算法的改进。

希尔排序又称缩小增量排序,因 DL.Shell 于 1959 年提出而得名。

它通过比较相距一定间隔的元素来进行,各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。

代码示例

void shell_sort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//保证最后一次 gap==1//多组并排for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

性能分析

  • 时间复杂度不好计算,需要进行推导,推导出来平均时间复杂度: O(N^1.3— N^2)
  • 空间复杂度:O(1)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3224373.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

编写ONLYOFFICE8.1版本推广活动文章

在这个日新月异的数字时代&#xff0c;高效、协同、智能已成为现代办公的关键词。作为全球领先的在线与桌面办公套件解决方案提供商&#xff0c;ONLYOFFICE始终站在技术创新的前沿&#xff0c;致力于为全球用户带来更加便捷、安全、强大的办公体验。今日&#xff0c;我们满怀激…

【实习问题记录】Nodeclub本地部署

问题描述 在按照官方网站给出的教程一步一步操作以后发现出现以下报错&#xff1a; 问题分析 显示连接不上mongodb&#xff0c;分析报错可能是因为版本不匹配导致的&#xff0c;查看安装的mongodb版本发现是7.0.4&#xff0c;与目标版本不匹配&#xff0c;同时查看mongodb官…

基于 sftp 的 NAS (局域网文件存储服务器)

局域网 NAS (文件存储服务器) 的基本功能有: 能够存储文件, 同时能够通过多个设备访问 (上传/下载) 文件. 这些功能通过 sftp 可以实现. sftp 是基于 SSH 的文件传输协议, SSH 全程加密传输, 使用 公钥 认证 (不使用密码/口令), 能够提供很高的安全性. 上文说到, 在 LVM 和 bt…

如何压缩pdf文件大小,怎么压缩pdf文件大小

在数字化时代&#xff0c;pdf文件因其稳定的格式和跨平台兼容性&#xff0c;成为了工作与学习中不可或缺的一部分。然而&#xff0c;随着pdf文件内容的丰富&#xff0c;pdf文件的体积也随之增大&#xff0c;给传输和存储带来了不少挑战。本文将深入探讨如何高效压缩pdf文件大小…

了解PPO算法(Proximal Policy Optimization)

Proximal Policy Optimization (PPO) 是一种强化学习算法&#xff0c;由 OpenAI 提出&#xff0c;旨在解决传统策略梯度方法中策略更新过大的问题。PPO 通过引入限制策略更新范围的机制&#xff0c;在保证收敛性的同时提高了算法的稳定性和效率。 PPO算法原理 PPO 算法的核心…

IDEA如何创建原生maven子模块

文件 -> 新建 -> 新模块 -> Maven ArcheTypeMaven ArcheType界面中的输入框介绍 名称&#xff1a;子模块的名称位置&#xff1a;子模块存放的路径名创建Git仓库&#xff1a;子模块不单独作为一个git仓库&#xff0c;无需勾选JDK&#xff1a;JDK版本号父项&#xff1a;…

策略路由和路由策略的区别详解

先说策略路由也就是 PBR&#xff1a; 它不会影响路由表的生成&#xff0c;设备的路由表是已经存在而且稳定的。 举个例子&#xff1a; 用 TCP/IP 路由技术一书的表述就是&#xff1a;策略路由就是一个复杂的静态路由。 总结&#xff1a;策略路由是一个基于路由表的影响特定数…

微信服务里底部的不常用功能如何优化的数据分析思路

图片.png 昨天下午茶时光&#xff0c;和闺蜜偶然聊起&#xff0c;其实在微信服务底部&#xff0c;有很多被我们忽略遗忘&#xff0c;很少点过用过的功能服务&#xff0c;往往进入服务只为了收付款或进入钱包&#xff0c;用完就走了&#xff0c;很少拉到底部&#xff0c;看到和用…

mirthConnect 常用示例和语法整理

mirthConnect 常用示例和语法整理 1、jolt json常用语法 https://please.blog.csdn.net/article/details/140137463 2、常用方法 2.1 WinningDateUtils 所有的时间工具在WinningDateUtils里面 获取当前时间&#xff1a;var nowStrWinningDateUtils.getStandardNowStr()获取…

Python函数 之 函数基础

print() 在控制台输出 input() 获取控制台输⼊的内容 type() 获取变量的数据类型 len() 获取容器的⻓度 (元素的个数) range() ⽣成⼀个序列[0, n) 以上都是我们学过的函数&#xff0c;函数可以实现⼀个特定的功能。我们将学习⾃⼰如何定义函数, 实现特定的功能。 1.函数是什么…

由于找不到krpt.dll,无法继续执行代码的7种解决方法

krpt.dll 与 Microsoft Office 套件中的 PDF 文档生成和编辑功能有关。它是 Microsoft Office 中的一项关键组件&#xff0c;在 Word、Excel 等应用程序中扮演着重要角色&#xff0c;支持文档转换成 PDF 格式的功能。那么遇到找不到krpt.dll文件或krpt.dll丢失要怎么办&#xf…

鸿蒙语言基础类库:【@ohos.util.ArrayList (线性容器ArrayList)】

线性容器ArrayList 说明&#xff1a; 本模块首批接口从API version 8开始支持。后续版本的新增接口&#xff0c;采用上角标单独标记接口的起始版本。开发前请熟悉鸿蒙开发指导文档&#xff1a;gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md点击或者复制转到。 …

FunAudioLLM SenseVoice语音转录与CosyVoice语音合成及语音克隆使用案例

参考: https://fun-audio-llm.github.io/ 1、SenseVoice语音转录 在线体验:https://modelscope.cn/studios/iic/CosyVoice-300M 参考:https://github.com/FunAudioLLM/SenseVoice 下载: pip install -U funasr使用: from funasr import AutoModelmodel_dir = "…

连接与隔离:Facebook在全球化背景下的影响力

在当今全球化的背景下&#xff0c;Facebook作为全球最大的社交网络平台&#xff0c;不仅连接了世界各地的人们&#xff0c;还在全球社会、经济和文化中发挥着深远的影响。本文将深入探讨Facebook在全球化进程中的作用&#xff0c;以及其对个体和社会之间连接与隔离的双重影响。…

odoo中的钩子 Hooks

钩子 钩子&#xff08;Hooks&#xff09;是一种在特定时间点或特定事件发生时执行自定义代码的机制。它们允许开发者在不修改核心代码的情况下&#xff0c;为Odoo添加自定义功能或扩展现有功能。以下是关于Odoo钩子的一些关键点和常见用法&#xff1a; 一、钩子的类型 pre_i…

CLion学习笔记-cmake编译和多main函数编译

这里就不讲怎么配置clion了 项目名字 pcl_kdtree_search 1.新建一个工程名字自己取&#xff0c;我这里用自己学习pcl的&#xff0c;加一个main函数&#xff0c;这个时候Cmake里边就是这样的。 #声明要求的cmake最低版本 cmake_minimum_required(VERSION 3.19) #声明一个工程…

福建 | 南安帝兴混凝土电子签收的困难和突破

01 发展从来都是从困难开始 混凝土发货单实现无纸化签收&#xff0c;众多业内人士认为这个概念很好&#xff0c;但能否落地却大多抱有怀疑态度&#xff0c;理由多种多样&#xff1a; “行业太传统&#xff0c;接受不了新鲜事物。” “驾驶员年龄偏大&#xff0c;玩不来智能手…

Linux源码阅读笔记09-进程NICE案例分析1

task_nice task_nice函数功能&#xff1a;获取某个进程的nice值&#xff0c;其中nice值为进程的优先级&#xff0c;与静态优先级有关&#xff08;nicestatic_prio-120&#xff09;。 nice的取值范围&#xff1a;-20 ~ 19 内核源码 根据内核的注释可以知道&#xff1a;task_n…

el-table封装popver組件,点击列筛选行数据功能,支持筛选,搜索,排序功能

子组件&#xff1a; <template><div class"tableTool" ref"tableTool" click.stop><el-button click"shengFnc">升序</el-button><el-button click"jiangFnc">降序</el-button><el-input v-m…

68.SAP FICO - 记账码学习

目录 定义 用途 配置步骤 定义记账码 - OB41 配置会计科目类型 在会计中&#xff0c;“借”和“贷”是记账符号&#xff0c;代表了记账的方向。而在SAP中却没有大家熟知的记账符号“借”和“贷”&#xff0c;那SAP中如何录入凭证呢&#xff1f;其实&#xff0c;SA…