【例题】lanqiao4403 希尔排序模板题

插入排序每次只能将数据移动一位。
已知插入排序代码为:
def insert_sort(a):for i in range(1,len(a)):j=i-1while j>=0 and a[j]>a[i]:a[j+1]=a[j]j-=1a[j+1]=a[i]return a
希尔排序在插入排序的基础上,将数据移动n/2,n/4,…,1位。
for i in range(gap, n):
temp = a[i]:把a[i]的值赋给temp,用于比较
j = i j指针从i开始,表示的是从后往前遍历比大小的下标。
当j >= gap(为了确保后面的j-gap下标还在数组索引里,不会超出范围) and a[j - gap] > temp(j-temp对应的数大于j对应的数,把j-gap的数放到原来的j的位置,然后再往前对比):
此时j下标对应的数是原来j-gap对应的数:
a[j] = a[j - gap]
因为根据插入排序原理,把要插入的数的大小temp跟前面已经排序好的数以步长为1( j -= 1)从后往前进行对比,希尔排序也是把要插入的数的大小temp跟前面已经排序好的数从后往前对比,但是是以步长为gap往前遍历。所以: j -= gap
跳出while循环的条件是已经把前面gap步长遇到的所有值排好序了,而且原来的a[j]=a[j-gap]是把j-gap比temp大的值放到了j的位置,那原来的j-gap的位置就空了出来,j-=gap操作后,原来的j-gap就是新的j的位置,把temp放到这个位置:a[j] = temp。实现了如果a[j - gap] > temp(a[i]),那么交换位置的操作。
用gap //= 2不断缩小步长,直到gap=1跟插入排序一致,此时所有数据顺序都排好了。
比如有一组示例数据如下
| 7 | 2 | 9 | 1 | 5 | 4 | 6 |
|---|
a数组长度是7
这里的gap初始值是7//2=3
a[i]初始值从3开始,a[3]=1。
接下来就是以gap的步长往前遍历,把数组分为4组:
a[j-temp] temp
7 1
2 6
9 4
1 6
然后进行对比,如果a[j - gap] > temp,交换位置。
这样处理后的数组为:
| 1 | 2 | 4 | 7 | 5 | 9 | 6 |
|---|
gap //= 2,gap=1。
a[i]初始值从1开始,a[1]=2。
接下来就是以gap的步长往前遍历比大小:
a[j-temp] temp
1 2
# 1247596
--------------
2 4
1 4
# 1247596
--------------
4 7
2 7
1 7
# 1247596
--------------
7 5
# 5,7互换
4 5
2 5
1 5
# 1245796
--------------
7 9
5 9
4 9
2 9
1 9
# 1245796
--------------
9 6
# 6,9互换
7 6
# 6,7互换
5 6
4 6
2 6
1 6
# 1245679
然后进行对比,如果a[j - gap] > temp,交换位置。
这样处理后的数组为:
| 1 | 2 | 4 | 5 | 6 | 7 | 9 |
|---|
def shell_sort(a):n = len(a)gap = n // 2while gap > 0:for i in range(gap, n):temp = a[i]j = iwhile j >= gap and a[j - gap] > temp:a[j] = a[j - gap]j -= gapa[j] = tempgap //= 2
希尔排序(Shell Sort)比插入排序(Insertion Sort)更高效的原因是因为希尔排序通过使用间隔序列在排序过程中引入了数据交换的“跳跃”。这种跳跃允许算法在内部循环中进行更远距离的交换,从而减少了元素比较和移动的次数。
对比代码如下:
import random
import timedef insertion_sort(arr):comparisons = 0moves = 0for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:comparisons += 1arr[j + 1] = arr[j]moves += 1j -= 1comparisons += 1arr[j + 1] = keyreturn comparisons, movesdef shell_sort(arr):comparisons = 0moves = 0gap = len(arr) // 2while gap > 0:for i in range(gap, len(arr)):temp = arr[i]j = iwhile j >= gap and arr[j - gap] > temp:comparisons += 1arr[j] = arr[j - gap]moves += 1j -= gapcomparisons += j >= gaparr[j] = tempgap //= 2return comparisons, moves# 生成随机数组
array_size = 1000
random_array = [random.randint(1, 10000) for _ in range(array_size)]# 复制数组以保持原始数组不变
insertion_array = random_array.copy()
shell_array = random_array.copy()# 插入排序
start_time = time.time()
insertion_comparisons, insertion_moves = insertion_sort(insertion_array)
insertion_time = time.time() - start_time# 希尔排序
start_time = time.time()
shell_comparisons, shell_moves = shell_sort(shell_array)
shell_time = time.time() - start_timeprint(f"Insertion Sort: Comparisons={insertion_comparisons}, Moves={insertion_moves}, Time={insertion_time:.6f}s")
print(f"Shell Sort: Comparisons={shell_comparisons}, Moves={shell_moves}, Time={shell_time:.6f}s")
Insertion Sort: Comparisons=245538, Moves=244539, Time=0.035560s
Shell Sort: Comparisons=14866, Moves=7356, Time=0.000997s
相关文章:
【例题】lanqiao4403 希尔排序模板题
插入排序每次只能将数据移动一位。 已知插入排序代码为: def insert_sort(a):for i in range(1,len(a)):ji-1while j>0 and a[j]>a[i]:a[j1]a[j]j-1a[j1]a[i]return a希尔排序在插入排序的基础上,将数据移动n/2,n/4,…,1位。 for i in range(ga…...
【C/C++】速通涉及string类的经典编程题
【C/C】速通涉及string类的经典编程题 一.字符串最后一个单词的长度代码实现:(含注释) 二.验证回文串解法一:代码实现:(含注释) 解法二:(推荐)1. 函数isalnum…...
MySQL:库表的基本操作
库操作 查看 查看存在哪些数据库: show databases;查看自己当前处于哪一个数据库: select database(); 由于我不处于任何一个数据库中,此处值为NULL 查看当前有哪些用户连接到了MySQL: show processlist; 创建 创建一个数据库 语…...
JS领域的AI工程利器分享
JavaScript,这个在网页开发中广为人知的脚本语言,正逐渐在AI工程领域展现出其独特的魅力。对于那些希望将大语言模型(LLM)融入项目的开发者来说,以下五个JavaScript工具将是关键资源。 1. TensorFlow.js TensorFlow.…...
2024/9/20 使用QT实现扫雷游戏
有三种难度初级6x6 中级10x10 高级16x16 完成游戏 游戏失败后,无法再次完成游戏,只能重新开始一局 对Qpushbutton进行重写 mybutton.h #ifndef MYBUTTON_H #define MYBUTTON_H #include <QObject> #include <QWidget> #include <QPus…...
09.20 C++对C的扩充以及C++中的封装、SeqList
SeqList.h #ifndef SEQLIST_H #define SEQLIST_H#include <iostream> #include<memory.h> #include<stdlib.h> #include<string.h>using namespace std;//typedef int datatype; //类型重命名 using datatype int;//封装一个顺序表 class Seq…...
Git提交类型
说明:Git提交类型指的是代码commit时,写在comment前面的标志,表示此次commit的提交类型,如下: Git提交类型 常见的Git提交类型有: feat:新特性、新功能或优化; fix:修复…...
C++速通LeetCode简单第18题-杨辉三角(全网唯一递归法)
全网唯一递归法: vector<vector<int>> generate(int numRows) {vector<int> v;vector<vector<int>>vn;if (numRows 1){v.push_back(1);vn.push_back(v);v.clear();return vn;//递归记得return}if (numRows 2){v.push_back(1);vn.p…...
Redis作为单线程模型,为什么效率高、速度快呢?
前言: 效率高、速度快是相较于数据库来说的(MySQL、Orcale、SQL server) 文章目录 一、单线程模式的工作流程二、为什么快? 一、单线程模式的工作流程 这里我们所说的单线程是指:Redis只使用一个线程,来处…...
人工智能——猴子摘香蕉问题
一、实验目的 求解猴子摘香蕉问题,根据猴子不同的位置,求解猴子的移动范围,求解对应的过程,针对不同的目标状态进行求解。 二、实验内容 根据场景有猴子、箱子、香蕉,香蕉挂天花板上。定义多种谓词描述位置、状态等…...
对ViT 中Patch Embedding理解
借鉴了这个博主的ViT Patch Embedding理解-CSDN博客,再加了一些理解。 就通过代码来理解吧 假设输入图像的维度为HxWxC,分别表示高,宽和通道数。 PatchEmbed 的类,它继承了 nn.Module,实现了将输入的2维图像&#…...
Redis基本命令详解
1. 基本命令 命令不区分大小写,而key是区分大小写的 # select 数据库间的切换 数据库共计16个 127.0.0.1:6379> select 1# dbsize 返回当前数据库的 key 的数量 127.0.0.1:6379[1]> dbsize# keys * 查看数据库所有的key 127.0.0.1:6379[1]> keys *# fl…...
Java之线程篇四
目录 volatile关键字 volatile保证内存可见性 代码示例 代码示例2-(volatile) volatile不保证原子性 synchronized保证内存可见性 wait()和notify() wait()方法 notify() 理解notify()和notifyAll() wait和sleep的对比 volatile关键字 volati…...
计算机毕业设计之:基于微信小程序的校园流浪猫收养系统
博主介绍: ✌我是阿龙,一名专注于Java技术领域的程序员,全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师,我在计算机毕业设计开发方面积累了丰富的经验。同时,我也是掘金、华为云、阿里云、InfoQ等平台…...
SpringBoot:关于Redis的配置失效(版本问题)
我们使用redis时发现yaml配置中的redis相关配置不生效,后面发现将配置修改甚至删除所有相关redis的配置,springboot依然能使用redis里面默认的db0并且不报错。上网查阅了一些文章,也都没有解决今天分享下,我的处理方法, SpringBo…...
halcon 快速定义字典
定义一个名为params的字典 Params : dict{} 等价于用 create_dict (Params ) 为字典添加键值对,在halcon中箭只能是字符串,值可以是任何类型的obj或者tuple Params.remove_outer_edges : true Params.max_gap : 150 等价于用 set_dict_object (true,…...
Sublime text3怎么关闭提示更新
问题 sublime text 3有新版本后,会不停地在每次启动后弹窗提示更新版本 第一步 软件安装之前,切记是软件安装之前!!!需要在hosts中添加以下内容(屏蔽官网联网检测):hosts的位置一般在C:\Windows\System32\drivers\etc…...
生成式语言模型技术栈
生成式语言模型的最新技术栈正在快速发展,尤其是随着大规模预训练模型(LLMs)和生成式AI的应用不断扩展。以下是当今最前沿的生成式语言模型技术栈,涵盖从模型开发到优化、推理和部署的各个环节。 1. 基础模型开发 基础模型开发包…...
进程分析工具Process Explorer使用
进程分析工具Process Explorer使用 Process Explorer让使用者能了解看不到的在后台执行的处理程序,能显示目前已经载入哪些模块,分别是正在被哪些程序使用着,还可显示这些程序所调用的DLL进程,以及他们所打开的句柄。Process Expl…...
vue 中如何实现鼠标拖动出发滚动条的跟随移动?
使用场景 在做弹窗、表单或 tab 切换需求的时候,有时候因为内容过长会导致出现滚动条,但是只能拖动滚动条时会导致操作不便,我们会希望实现通过拖动内容区实现滚动条的滑动。这样操作就会简单多了。 实现思路 如果要实现鼠标辅助触发滚动条…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...
论文阅读:Matting by Generation
今天介绍一篇关于 matting 抠图的文章,抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法,已经有很多的工作和这个任务相关。这两年 diffusion 模型很火,大家又开始用 diffusion 模型做各种 CV 任务了&am…...
高分辨率图像合成归一化流扩展
大家读完觉得有帮助记得关注和点赞!!! 1 摘要 我们提出了STARFlow,一种基于归一化流的可扩展生成模型,它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流(TARFlow&am…...
