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

【例题】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跟插入排序一致,此时所有数据顺序都排好了。

比如有一组示例数据如下

7291546

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,交换位置。

这样处理后的数组为:

1247596

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,交换位置。

这样处理后的数组为:

1245679
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 希尔排序模板题

插入排序每次只能将数据移动一位。 已知插入排序代码为&#xff1a; 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希尔排序在插入排序的基础上&#xff0c;将数据移动n/2,n/4,…,1位。 for i in range(ga…...

【C/C++】速通涉及string类的经典编程题

【C/C】速通涉及string类的经典编程题 一.字符串最后一个单词的长度代码实现&#xff1a;&#xff08;含注释&#xff09; 二.验证回文串解法一&#xff1a;代码实现&#xff1a;&#xff08;含注释&#xff09; 解法二&#xff1a;&#xff08;推荐&#xff09;1. 函数isalnum…...

MySQL:库表的基本操作

库操作 查看 查看存在哪些数据库&#xff1a; show databases;查看自己当前处于哪一个数据库&#xff1a; select database(); 由于我不处于任何一个数据库中&#xff0c;此处值为NULL 查看当前有哪些用户连接到了MySQL&#xff1a; show processlist; 创建 创建一个数据库 语…...

JS领域的AI工程利器分享

JavaScript&#xff0c;这个在网页开发中广为人知的脚本语言&#xff0c;正逐渐在AI工程领域展现出其独特的魅力。对于那些希望将大语言模型&#xff08;LLM&#xff09;融入项目的开发者来说&#xff0c;以下五个JavaScript工具将是关键资源。 1. TensorFlow.js TensorFlow.…...

2024/9/20 使用QT实现扫雷游戏

有三种难度初级6x6 中级10x10 高级16x16 完成游戏 游戏失败后&#xff0c;无法再次完成游戏&#xff0c;只能重新开始一局 对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提交类型

说明&#xff1a;Git提交类型指的是代码commit时&#xff0c;写在comment前面的标志&#xff0c;表示此次commit的提交类型&#xff0c;如下&#xff1a; Git提交类型 常见的Git提交类型有&#xff1a; feat&#xff1a;新特性、新功能或优化&#xff1b; fix&#xff1a;修复…...

C++速通LeetCode简单第18题-杨辉三角(全网唯一递归法)

全网唯一递归法&#xff1a; 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作为单线程模型,为什么效率高、速度快呢?

前言&#xff1a; 效率高、速度快是相较于数据库来说的&#xff08;MySQL、Orcale、SQL server&#xff09; 文章目录 一、单线程模式的工作流程二、为什么快&#xff1f; 一、单线程模式的工作流程 这里我们所说的单线程是指&#xff1a;Redis只使用一个线程&#xff0c;来处…...

人工智能——猴子摘香蕉问题

一、实验目的 求解猴子摘香蕉问题&#xff0c;根据猴子不同的位置&#xff0c;求解猴子的移动范围&#xff0c;求解对应的过程&#xff0c;针对不同的目标状态进行求解。 二、实验内容 根据场景有猴子、箱子、香蕉&#xff0c;香蕉挂天花板上。定义多种谓词描述位置、状态等…...

对ViT 中Patch Embedding理解

借鉴了这个博主的ViT Patch Embedding理解-CSDN博客&#xff0c;再加了一些理解。 就通过代码来理解吧 假设输入图像的维度为HxWxC&#xff0c;分别表示高&#xff0c;宽和通道数。 PatchEmbed 的类&#xff0c;它继承了 nn.Module&#xff0c;实现了将输入的2维图像&#…...

Redis基本命令详解

1. 基本命令 命令不区分大小写&#xff0c;而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-&#xff08;volatile&#xff09; volatile不保证原子性 synchronized保证内存可见性 wait()和notify() wait()方法 notify() 理解notify()和notifyAll() wait和sleep的对比 volatile关键字 volati…...

计算机毕业设计之:基于微信小程序的校园流浪猫收养系统

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

SpringBoot:关于Redis的配置失效(版本问题)

我们使用redis时发现yaml配置中的redis相关配置不生效&#xff0c;后面发现将配置修改甚至删除所有相关redis的配置&#xff0c;springboot依然能使用redis里面默认的db0并且不报错。上网查阅了一些文章&#xff0c;也都没有解决今天分享下&#xff0c;我的处理方法, SpringBo…...

halcon 快速定义字典

定义一个名为params的字典 Params : dict{} 等价于用 create_dict (Params ) 为字典添加键值对&#xff0c;在halcon中箭只能是字符串&#xff0c;值可以是任何类型的obj或者tuple Params.remove_outer_edges : true Params.max_gap : 150 等价于用 set_dict_object (true,…...

Sublime text3怎么关闭提示更新

问题 sublime text 3有新版本后,会不停地在每次启动后弹窗提示更新版本 第一步 软件安装之前&#xff0c;切记是软件安装之前&#xff01;&#xff01;&#xff01;需要在hosts中添加以下内容(屏蔽官网联网检测)&#xff1a;hosts的位置一般在C:\Windows\System32\drivers\etc…...

生成式语言模型技术栈

生成式语言模型的最新技术栈正在快速发展&#xff0c;尤其是随着大规模预训练模型&#xff08;LLMs&#xff09;和生成式AI的应用不断扩展。以下是当今最前沿的生成式语言模型技术栈&#xff0c;涵盖从模型开发到优化、推理和部署的各个环节。 1. 基础模型开发 基础模型开发包…...

进程分析工具Process Explorer使用

进程分析工具Process Explorer使用 Process Explorer让使用者能了解看不到的在后台执行的处理程序&#xff0c;能显示目前已经载入哪些模块&#xff0c;分别是正在被哪些程序使用着&#xff0c;还可显示这些程序所调用的DLL进程&#xff0c;以及他们所打开的句柄。Process Expl…...

vue 中如何实现鼠标拖动出发滚动条的跟随移动?

使用场景 在做弹窗、表单或 tab 切换需求的时候&#xff0c;有时候因为内容过长会导致出现滚动条&#xff0c;但是只能拖动滚动条时会导致操作不便&#xff0c;我们会希望实现通过拖动内容区实现滚动条的滑动。这样操作就会简单多了。 实现思路 如果要实现鼠标辅助触发滚动条…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

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

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

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...