数据结构算法--6 希尔排序和计数排序

希尔排序

希尔排序与插入排序原理相同,希尔排序是一种分组插入排序算法

> 首先取一个整数d1=n/2,将元素分为d1个组,每组相邻两元素之间距离为d1,在各组内之间插入排序。

> 取第二个整数d2=n/2,重复上述分组排序过程,直到di=1,即所有元素在同一组内直接插入排序

> 希尔排序每趟并不使某些元素有序,而是使整体数据越来越接近有序;最后一趟排序使所有数据有序。

给一个数组:5,7,4,6,3,1,2,9,8

首先d=4:

5和3交换位置;7和1交换位置;4和2交换位置;6和9位置不变;

数组在第一轮变为3,1,2,6,5,7,4,9,8

然后d=2:

两组内部再次插入排序,结果变为2,1,3,6,4,7,5,9,8

最后d=1,整体插入排序使数组有序:1,2,3,4,5,6,7,8,9

> 希尔排序代码:

def insert_sort_gap(li,gap):for i in range(gap,len(li)):  # i 表示摸到牌的下标tmp=li[i]j=i-gapwhile j>=0 and li[j]>tmp:li[j+gap]=li[j]j-=gapli[j+gap]=tmpdef shell_sort(li):d=len(li) //2while d>=1:insert_sort_gap(li,d)d //=2

计数排序

计数排序是对列表进行排序,列表中的数大小在0到100之间,时间复杂度为O(n)

对于一个数组,我们先写出一个从0到5的数,然后在这些数后边写上每个值在列表中出现的次数

我们在整个数组中先写出这些统计的值的数默认为0

我们找出出现的次数后:

将其按大小写出:1,1,1,2,2,3,3,3,4,5

> 希尔排序代码:

def count_sort(li,max_count=100):count=[0 for _ in range(max_count+1)]   #生成100个0,他们的下标就是列表中的值for val in li:count[val] +=1li.clear()for ind,val in enumerate(count):for i in range(val):                #添加整个值的次数为valli.append(ind)                  

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

HTML——列表,表格,表单内容的讲解

文章目录 一、列表1.1无序(unorder)列表1.2 有序(order)列表1.3 定义列表 二、表格**2.1 基本的表格标签2.2 演示 三、表单3.1 form元素3.2 input元素3.2.1 单选按钮 3.3 selcet元素 基础部分点击: web基础 一、列表 …

华为云云耀云服务器L实例评测|华为云云耀云服务器L实例CentOS的存储和备份策略

1 华为云云耀云服务器L实例介绍 华为云云耀云服务器L实例是华为云计算服务中的一种虚拟云服务器,它提供了强大的计算资源,可以在云端运行各种应用程序和服务。 华为云服务器提供了多种实例类型,包括通用型、计算优化型、内存优化型等&#…

时序预测 | MATLAB实现POA-CNN-GRU鹈鹕算法优化卷积门控循环单元时间序列预测

时序预测 | MATLAB实现POA-CNN-GRU鹈鹕算法优化卷积门控循环单元时间序列预测 目录 时序预测 | MATLAB实现POA-CNN-GRU鹈鹕算法优化卷积门控循环单元时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 MATLAB实现POA-CNN-GRU鹈鹕算法优化卷积门控循环单元时间序…

Flutter笔记:手写一个简单的画板工具

Flutter笔记 手写一个简单的画板工具 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq_28550263/article/details/133418742 目 录 1…

华为智能企业上网行为管理安全解决方案(2)

本文承接: https://blog.csdn.net/qq_37633855/article/details/133339254?spm1001.2014.3001.5501 重点讲解华为智能企业上网行为管理安全解决方案的部署流程。 华为智能企业上网行为管理安全解决方案(2) 课程地址方案部署整体流程组网规划…

R语言进行孟德尔随机化+meta分析(2)----基于R和stata

目前不少文章用到了孟德尔随机化meta分析,在上一章咱们简单介绍了一下meta分析的基础知识。咱们今天来介绍一篇11分文章,由文章看看孟德尔随机化meta分析如何进行,文章的题目是:Appraising the causal role of smoking in multipl…

No165.精选前端面试题,享受每天的挑战和学习

🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…

AIGC(生成式AI)试用 7 -- 桌面小程序

生成式AI,别人用来写作,我先用来写个桌面小程序。 桌面小程序:计算器 需求 Python开发图形界面,标题:计算器 - * / 基本运算计算范围:-999999999 ~ 999999999** 乘方计算(例,2*…

NX 1988 如何将组件转为部件

打开组件 文件-导出-部件 指定部件名为1206,类选择:所有要导出的部件 选择完全加载 完成

【从入门到起飞】JavaSE—Stream流

🎊专栏【JavaSE】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【如愿】 🥰欢迎并且感谢大家指出我的问题 文章目录 🍔Stream流的作用🍔Stream流的使用步骤🎄获取Strea…

Go-Ldap-Admin | openLDAP 同步钉钉、企业微信、飞书组织架构实践和部分小坑

目录 一、Docker-compose快速拉起demo测试环境 二、原生部署流程 安装MySQL:5.7数据库 安装openLDAP 修改域名,新增con.ldif 创建一个组织 安装OpenResty 下载后端 下载前端 部署后端 部署前端 三、管理动态字段 钉钉 企业微信 飞书 四、…

内存函数(memcpy、memmove、memset、memcmp)你真的懂了吗?

💓博客主页:江池俊的博客⏩收录专栏:C语言进阶之路👉专栏推荐:✅C语言初阶之路 ✅数据结构探索💻代码仓库:江池俊的代码仓库🎉欢迎大家点赞👍评论📝收藏⭐ 文…

26663-2011 大型液压安全联轴器 课堂随笔

声明 本文是学习GB-T 26663-2011 大型液压安全联轴器. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 1 范围 本标准规定了大型液压安全联轴器的分类、技术要求、试验方法及检验规则等。 本标准适用于联接两同轴线的传动轴系,可起到限制…

分布式事务-TCC案例分析流程图

防止cancel方法在最后执行出现问题,用户收到提示已经退款成功但是由于cancel过慢或者出现问题(虽然最后会重试成功但是用户体验很差),可以做以下的业务sql模型优化(增加一个冻结金额)。

消息队列实现进程间通信

write.c #include<myhead.h>typedef struct {long msgtype; //消息类型char data[1024]; //消息正文 }Msg_s;#define SIZE sizeof(Msg_s)-sizeof(long) //消息正文的大小int main(int argc, const char *argv[]) {key_t key; //定义一个键值if((key ftok("./&q…

基于springboot的洗衣店订单管理系统

目录 前言 一、技术栈 二、系统功能介绍 顾客信息管理 店家信息管理 店铺信息管理 洗衣信息管理 预约功能 洗衣信息 交流区 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 随着信息互联网信息的飞速发展&#xff0c;无纸化作业变成了一种趋势&#x…

红队打靶:THE PLANETS: MERCURY打靶思路详解(vulnhub)

目录 写在开头 第一步&#xff1a;主机发现和端口扫描 第二步&#xff1a;Web渗透 第三步&#xff1a;获取初步立足点并搜集信息 第四步&#xff1a;软连接劫持sudo提权 总结与思考 写在开头 本篇博客在自己的理解之上根据大佬红队笔记的视频进行打靶&#xff0c;详述了…

【HTML】表格行和列的合并

概述 当我们需要在 HTML 表格中展示复杂的数据时&#xff0c;行和列的合并可以帮助我们实现更灵活的布局和结构。通过合并行和列&#xff0c;我们可以创建具有更多层次和结构的表格&#xff0c;使数据更易于理解和分析。 在 HTML 表格中&#xff0c;我们可以使用 rowspan 和 …

KUKA机器人通过3点法设置工作台基坐标系的具体方法

KUKA机器人通过3点法设置工作台基坐标系的具体方法 具体方法和步骤可参考以下内容: 进入主菜单界面,依次选择“投入运行”—“测量”—基坐标,选择“3点法”, 在系统弹出的基坐标编辑界面,给基座标编号为3,命名为table1,然后单击“继续”按钮,进行下一步操作, 在弹出的…

华为云智能化组装式交付方案 ——金融级PaaS业务洞察及Web3实践的卓越贡献

伴随信息技术与金融业务加速的融合&#xff0c;企业应用服务平台&#xff08;PaaS&#xff09;已从幕后走向台前&#xff0c;成为推动行业数字化转型的关键力量。此背景下&#xff0c;华为云PaaS智能化组装式交付方案闪耀全场&#xff0c;在近日结束的华为全联接大会 2023上倍受…