当前位置: 首页 > 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"> <…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

React核心概念:State是什么?如何用useState管理组件自己的数据?

系列回顾&#xff1a; 在上一篇《React入门第一步》中&#xff0c;我们已经成功创建并运行了第一个React项目。我们学会了用Vite初始化项目&#xff0c;并修改了App.jsx组件&#xff0c;让页面显示出我们想要的文字。但是&#xff0c;那个页面是“死”的&#xff0c;它只是静态…...

AWS vs 阿里云:功能、服务与性能对比指南

在云计算领域&#xff0c;Amazon Web Services (AWS) 和阿里云 (Alibaba Cloud) 是全球领先的提供商&#xff0c;各自在功能范围、服务生态系统、性能表现和适用场景上具有独特优势。基于提供的引用[1]-[5]&#xff0c;我将从功能、服务和性能三个方面进行结构化对比分析&#…...

Redis——Cluster配置

目录 分片 一、分片的本质与核心价值 二、分片实现方案对比 三、分片算法详解 1. ‌范围分片&#xff08;顺序分片&#xff09;‌ 2. ‌哈希分片‌ 3. ‌虚拟槽分片&#xff08;Redis Cluster 方案&#xff09;‌ 四、Redis Cluster 分片实践要点 五、经典问题解析 C…...