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

冒泡排序、选择排序、插入排序、希尔排序

冒泡排序

基本思想

 

代码实现

# 冒泡排序
def bubble_sort(arr):length = len(arr) - 1for i in range(length):flag = Truefor j in range(length - i):if arr[j] > arr[j + 1]:temp = arr[j]arr[j] = arr[j + 1]arr[j + 1] = tempflag = Falseprint(f'第{i + 1}趟的排序结果为:', arr)if flag:# 代码优化,如果某一趟排序中没有发生交换,表示序列已经有序,可以提前结束循环breakbubble_sort([3, 9, -1, 10, 20])
bubble_sort([3, 9, -1, 10, -2])

选择排序

基本思想

 

代码实现

# 选择排序
def select_sort(arr):for i in range(len(arr) - 1):  # 进行 n-1 趟排序min = arr[i]index = ifor j in range(i + 1, len(arr)):if min > arr[j]:min = arr[j]index = jif index != i:arr[index] = arr[i]arr[i] = minprint(f'第{i + 1}趟排序结果:', arr)select_sort([3, 9, -1, 10, -2])
select_sort([3, 9, -1, 10, 20])

插入排序

基本思想

代码实现

# 插入排序
def insert_sort(arr):# for 循环遍历的是待排序的序列,即无序的序列for i in range(len(arr) - 1):insert_val = arr[i + 1]  # 待插入有序列表的值# 以 insert_index 位置为分割点,可以把 insert_index 及其之前的元素理解为已排序的序列# insert_index 以后的元素是无序序列insert_index = i  # 待插入值的前一个值的下标,即有序列表的最后一个元素的位置# while 循环遍历的是已有序的序列# insert_index >= 0 保证下标不越界# 从后往前访问有序列表# insert_val < arr[insert_index] 当待插入的值比有序列表中的值还小时,往前遍历有序列表,继续比较while insert_index >= 0 and insert_val < arr[insert_index]:# 将 arr[insert_index] 值后移,空出前面的位置存放待插入的值arr[insert_index + 1] = arr[insert_index]# 继续访问有序列表的前一个元素insert_index -= 1# 退出循环时,表示找到了插入的位置# 插入的位置为 insert_index + 1 ,因为 insert_index 位置要么为 -1 ,要么为比待插入值小的数arr[insert_index + 1] = insert_valprint(f'第{i + 1}个待插入的值插入后的结果', arr)insert_sort([3, 9, -1, 10, -2])
insert_sort([3, 9, -1, 10, 20])

希尔排序

基本思想

 

 

代码实现

# 希尔排序——交换法(效率低)
def shell_sort1(arr):"""# 以 [8, 9, 1, 7, 2, 3, 5, 4, 6, 0] 为例进行分析# 希尔排序的第一轮# 第一轮将数组分为 10 // 2 = 5 组for i in range(5, len(arr)):# 遍历各组中所有的元素(共5组,每组2个元素),步长为5j = i - 5while j >= 0:# 如果当前元素大于加上步长后的哪个元素,说明需要交换if arr[j] > arr[j + 5]:temp = arr[j]arr[j] = arr[j + 5]arr[j + 5] = tempj -= 5print('希尔排序的第一轮结果:', arr)# 希尔排序的第二轮 [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]# 第二轮将数组分为 5 // 2 = 2 组for i in range(2, len(arr)):# 遍历各组中所有的元素(共2组,每组5个元素),步长为5j = i - 2while j >= 0:# 如果当前元素大于加上步长后的哪个元素,说明需要交换if arr[j] > arr[j + 2]:temp = arr[j]arr[j] = arr[j + 2]arr[j + 2] = tempj -= 2print('希尔排序的第二轮结果:', arr)# 希尔排序的第三轮 [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]# 第三轮将数组分为 2 // 2 = 1 组for i in range(1, len(arr)):# 遍历各组中所有的元素(共1组,每组10个元素),步长为5j = i - 1while j >= 0:# 如果当前元素大于加上步长后的哪个元素,说明需要交换if arr[j] > arr[j + 1]:temp = arr[j]arr[j] = arr[j + 1]arr[j + 1] = tempj -= 1print('希尔排序的第三轮结果:', arr)"""# 交换法希尔排序gap = len(arr) // 2while gap > 0:for i in range(gap, len(arr)):# 遍历各组中所有的元素,步长为gapj = i - gapwhile j >= 0:# 如果当前元素大于加上步长后的哪个元素,说明需要交换if arr[j] > arr[j + gap]:temp = arr[j]arr[j] = arr[j + gap]arr[j + gap] = tempj -= gapprint('本轮排序结果:', arr)gap //= 2# 希尔排序——移位法(效率更高)
def shell_sort2(arr):# 移位法希尔排序,效率更高gap = len(arr) // 2while gap > 0:for i in range(gap, len(arr)):j = itemp = arr[j]if arr[j] < arr[j - gap]:while j - gap >= 0 and temp < arr[j - gap]:arr[j] = arr[j - gap]j -= gaparr[j] = tempprint('本轮排序结果:', arr)gap //= 2shell_sort1([8, 9, 1, 7, 2, 3, 5, 4, 6, 0])
shell_sort2([8, 9, 1, 7, 2, 3, 5, 4, 6, 0])

相关文章:

冒泡排序、选择排序、插入排序、希尔排序

冒泡排序 基本思想 代码实现 # 冒泡排序 def bubble_sort(arr):length len(arr) - 1for i in range(length):flag Truefor j in range(length - i):if arr[j] > arr[j 1]:temp arr[j]arr[j] arr[j 1]arr[j 1] tempflag Falseprint(f第{i 1}趟的排序结果为&#…...

OpenCV(二十三):中值滤波

1.中值滤波的原理 中值滤波&#xff08;Median Filter&#xff09;是一种常用的非线性图像滤波方法&#xff0c;用于去除图像中的椒盐噪声等离群点。它的原理是基于邻域像素值的排序&#xff0c;并将中间值作为当前像素的新值。 2.中值滤波函数 medianBlur() void cv::medianBl…...

Prompt Tuning训练过程

目录 0. 入门 0.1. NLP发展的四个阶段&#xff1a; Prompt工程如此强大&#xff0c;我们还需要模型训练吗&#xff1f; - 知乎 Prompt learning系列之prompt engineering(二) 离散型prompt自动构建 Prompt learning系列之训练策略篇 - 知乎 ptuning v2 的 chatglm垂直领域训练记…...

装备制造企业是否要转型智能装备后服务型公司?

一、从制造到服务&#xff1a;装备制造企业的转型之路 装备制造企业作为国家经济发展的重要支柱&#xff0c;面临着日益激烈的市场竞争。在这样的背景下&#xff0c;越来越多的装备制造企业开始意识到&#xff0c;通过转型为智能装备后服务型公司&#xff0c;可以更好地满足客…...

day-49 代码随想录算法训练营(19) 动态规划 part 10

121.买卖股票的最佳时机 思路一&#xff1a;贪心 不断更新最小买入值不断更新当前值和最小买入值的差值最大值 思路二&#xff1a;动态规划&#xff08;今天自己写出来了哈哈哈哈哈哈哈&#xff09; 1.dp存储&#xff1a;dp[i][0] 表示当前持有 dp[i][1]表示当前不持有2.状…...

检查文件名是否含不可打印字符的C++代码源码

本篇文章属于《518抽奖软件开发日志》系列文章的一部分。 我在开发《518抽奖软件》&#xff08;www.518cj.net&#xff09;的时候&#xff0c;有时候需要检查输入的是否是合法的文件名&#xff0c;文件名是否含不可打印字符等。代码如下&#xff1a; //----------------------…...

学习笔记-正则表达式

https://www.runoob.com/regexp/regexp-tutorial.html 正则表达式re(Regular Expression)是一种文本模式&#xff0c;包括普通字符&#xff08;例如&#xff0c;a 到 z 之间的字母&#xff09;和特殊字符&#xff08;称为"元字符"&#xff09;&#xff0c;可以用来描…...

Wireshark TS | 网络路径不一致传输丢包问题

问题背景 网络路径不一致&#xff0c;或者说是网络路径来回不一致&#xff0c;再专业点可以说是网络路径不对称&#xff0c;以上种种说法&#xff0c;做网络方向的工程师肯定会更清楚些&#xff0c;用简单的描述就是&#xff1a; A 与 B 通讯场景&#xff0c;C 和 D 代表中间…...

CMake高级用法实例分析(学习paddle官方的CMakeLists)

cmake基础学习教程 https://juejin.cn/post/6844903557183832078 官方完整CMakeLists cmake_minimum_required(VERSION 3.0) project(PaddleObjectDetector CXX C)option(WITH_MKL "Compile demo with MKL/OpenBlas support,defaultuseMKL." ON) o…...

数据采集: selenium 自动翻页接口调用时的验证码处理

写在前面 工作中遇到&#xff0c;简单整理理解不足小伙伴帮忙指正 对每个人而言&#xff0c;真正的职责只有一个&#xff1a;找到自我。然后在心中坚守其一生&#xff0c;全心全意&#xff0c;永不停息。所有其它的路都是不完整的&#xff0c;是人的逃避方式&#xff0c;是对大…...

IDEA安装翻译插件

IDEA安装翻译插件 File->Settings->Plugins 在Marketplace中&#xff0c;找到Translation&#xff0c;点击Install 更换翻译引擎 勾选自动翻译文档 翻译 鼠标右击->点击Translate...

DBeaver使用

一、导出表结构 二、导出数据CSV 导出数据时DBeaver并没有导出表结构&#xff0c;所以表结构需要额外保存&#xff1b; 导入数据CSV 导入数据时会因外键、字段长度导致失败&#xff1b;...

Nougat:一种用于科学文档OCR的Transformer 模型

随着人工智能领域的不断进步&#xff0c;其子领域&#xff0c;包括自然语言处理&#xff0c;自然语言生成&#xff0c;计算机视觉等&#xff0c;由于其广泛的用例而迅速获得了大量的普及。光学字符识别(OCR)是计算机视觉中一个成熟且被广泛研究的领域。它有许多用途&#xff0c…...

redis八股1

参考Redis连环60问&#xff08;八股文背诵版&#xff09; - 知乎 (zhihu.com) 1.是什么 本质上是一个key-val数据库,把整个数据库加载到内存中操作&#xff0c;定期通过异步操作把数据flush到硬盘持久化。因为纯内存操作&#xff0c;所以性能很出色&#xff0c;每秒可以超过10…...

人工智能基础-趋势-架构

在过去的几周里&#xff0c;我花了一些时间来了解生成式人工智能基础设施的前景。在这篇文章中&#xff0c;我的目标是清晰概述关键组成部分、新兴趋势&#xff0c;并重点介绍推动创新的早期行业参与者。我将解释基础模型、计算、框架、计算、编排和矢量数据库、微调、标签、合…...

Date日期工具类(数据库日期区间问题)

文章目录 前言DateUtils日期工具类总结 前言 在我们日常开发过程中&#xff0c;当涉及到处理日期和时间的操作时&#xff0c;字符串与Date日期类往往要经过相互转换&#xff0c;且在SQL语句的动态查询中&#xff0c;往往月份的格式不正确&#xff0c;SQL语句执行的效果是不同的…...

为什么需要 TIME_WAIT 状态

还是用一下上一篇文章画的图 TCP 的 11 个状态&#xff0c;每一个状态都缺一不可&#xff0c;自然 TIME_WAIT 状态被赋予的意义也是相当重要&#xff0c;咱们直接结论先行 上文我们提到 tcp 中&#xff0c;主动关闭的一边会进入 TIME_WAIT 状态&#xff0c; 另外 Tcp 中的有 …...

Linux——(第七章)文件权限管理

目录 一、基本介绍 二、文件/目录的所有者 1.查看文件的所有者 2.修改文件所有者 三、文件/目录的所在组 1.修改文件/目录所在组 2.修改用户所在组 四、权限的基本介绍 五、rwx权限详解 1.rwx作用到文件 2.rwx作用到目录 六、修改权限 一、基本介绍 在Linux中&…...

Scala在大数据领域的崛起:当前趋势和未来前景

文章首发地址 Scala在大数据领域有着广阔的前景和现状。以下是一些关键点&#xff1a; Scala是一种具有强大静态类型系统的多范式编程语言&#xff0c;它结合了面向对象编程和函数式编程的特性。这使得Scala非常适合处理大数据&#xff0c;因为它能够处理并发、高吞吐量和复杂…...

前端面试经典题--页面布局

题目 假设高度已知&#xff0c;请写出三栏布局&#xff0c;其中左、右栏宽度各为300px&#xff0c;中间自适应。 五种解决方式代码 浮动解决方式 绝对定位解决方式 flexbox解决方式 表格布局 网格布局 源代码 <!DOCTYPE html> <html lang"en"> <…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...