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

Python系列(20)—— 排序算法

Python中的排序算法

一、引言

排序算法是计算机科学中的基本算法之一,用于将一组数据按照特定的顺序进行排列。Python提供了多种排序算法的实现,包括内置的排序函数和手动实现的排序算法。本文将介绍几种常见的排序算法,并通过代码实例来展示它们的实现。

二、冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法,通过重复遍历待排序的列表,比较相邻的元素并交换位置,直到列表有序为止。

代码实例

def bubble_sort(arr):n = len(arr)for i in range(n):# 标记,表示是否发生了交换swapped = Falsefor j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]swapped = True# 如果没有发生交换,说明列表已经有序,可以提前结束循环if not swapped:break# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的列表:", arr)

三、选择排序(Selection Sort)

选择排序通过每次从未排序的元素中选择最小(或最大)的元素,将其放置到已排序的序列的末尾(或开头),直到所有元素都排序完毕。

代码实例

def selection_sort(arr):n = len(arr)for i in range(n):# 找到未排序部分中的最小元素min_idx = ifor j in range(i+1, n):if arr[j] < arr[min_idx]:min_idx = j# 将最小元素交换到已排序部分的末尾arr[i], arr[min_idx] = arr[min_idx], arr[i]# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("排序后的列表:", arr)

四、插入排序(Insertion Sort)

插入排序通过将未排序的元素一个个插入到已排序的序列中,从而得到有序序列。

代码实例

def insertion_sort(arr):n = len(arr)for i in range(1, n):key = arr[i]j = i-1# 将大于key的元素向右移动while j >= 0 and key < arr[j]:arr[j+1] = arr[j]j -= 1arr[j+1] = key# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("排序后的列表:", arr)

五、快速排序(Quick Sort)

快速排序是一种分而治之的排序算法,通过选择一个基准元素,将列表分为两个子列表,一个包含小于基准的元素,另一个包含大于基准的元素,然后递归地对子列表进行排序。

代码实例

def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print("排序后的列表:", sorted_arr)

六、归并排序(Merge Sort)

归并排序也是一种分而治之的排序算法,它将一个列表分成两个等长(几乎等长)的子列表,递归地对子列表进行排序,然后将排序后的子列表合并成一个有序的列表。

代码实例

def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]left_half = merge_sort(left_half)right_half = merge_sort(right_half)return merge(left_half, right_half)def merge(left, right):merged = []left_index = 0right_index = 0# 合并两个已排序的列表while left_index < len(left) and right_index < len(right):if left[left_index] <= right[right_index]:merged.append(left[left_index])left_index += 1else:merged.append(right[right_index])right_index += 1# 将剩余的元素添加到结果列表中while left_index < len(left):merged.append(left[left_index])left_index += 1while right_index < len(right):merged.append(right[right_index])right_index += 1return merged# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print("排序后的列表:", sorted_arr)

七、总结

本文介绍了Python中几种常见的排序算法,包括冒泡排序、选择排序、插入排序、快速排序和归并排序,并通过代码实例展示了它们的实现。这些排序算法在不同的情况下各有优缺点,例如冒泡排序和选择排序对于小规模数据是有效的,但对于大规模数据效率较低。快速排序和归并排序在处理大规模数据时表现出色,但快速排序在最坏情况下的时间复杂度为 O ( n 2 ) O(n^2) O(n2),而归并排序的时间复杂度始终为 O ( n l o g n ) O(nlogn) O(nlogn)。了解这些算法的特点和适用场景,可以帮助你根据具体问题选择合适的排序算法。

相关文章:

Python系列(20)—— 排序算法

Python中的排序算法 一、引言 排序算法是计算机科学中的基本算法之一&#xff0c;用于将一组数据按照特定的顺序进行排列。Python提供了多种排序算法的实现&#xff0c;包括内置的排序函数和手动实现的排序算法。本文将介绍几种常见的排序算法&#xff0c;并通过代码实例来展…...

MySQL中json类型的字段

有些很复杂的信息&#xff0c;我们一般会用扩展字段传一个json串&#xff0c;字段一般用text类型存在数据库。mysql5.7以后支持json类型的字段&#xff0c;还可以进行sql查询与修改json内的某个字段的能力。 1.json字段定义 ip_info json DEFAULT NULL COMMENT ip信息, 2.按…...

算法学习——GCD与欧拉函数

欧几里得GCD&#xff1a; GCD算法是使用辗转相除法求最大公因数的算法&#xff0c;简单而言就是gcd(a,b) gcd(b,a mod b) 递归写法&#xff1a; int Gcd(int a, int b) {if(b 0)return a;return Gcd(b, a % b); } 迭代写法&#xff1a; int Gcd(int a, int b) {while(b …...

40. 组合总和 II(力扣LeetCode)

文章目录 40. 组合总和 II题目描述回溯算法 40. 组合总和 II 题目描述 给定一个候选人编号的集合 candidates 和一个目标数 target &#xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意&#xff…...

Ubuntu上Jenkins自动化部署Gitee上SpringBoot项目

文章目录 安装安装JDK安装Maven安装GitNodeJS安装&#xff08;可选&#xff09;安装Jenkins 配置Jenkins为Jenkins更换插件源设置jenkins时区安装插件全局工具配置添加Gitee凭证Gitee项目配置 部署后端1.新建任务2.配置源码管理3.构建触发器4.到Gitee中添加WebHook5.构建环境6.…...

延迟任务基于DeyalQueue

一&#xff0c;延迟任务应用场景&#xff1f; 一般用于处理订单&#xff0c;将redis中的数据延迟存入数据库&#xff0c;实现异步存储减少DB的压力 二&#xff0c; 延迟任务的实现方案有很多 DelayQueue Redisson MQ 时间轮 原理 JDK自带延迟队列&#xff0c;基于阻塞队列…...

Linux 查询端口被占用命令

Linux 查询端口被占用命令 1、lsof -i:端口号 用于查看某一端口的占用情况&#xff0c;比如查看8000端口使用情况&#xff0c;lsof -i:8000 lsof -i:8080&#xff1a;查看8080端口占用 lsof abc.txt&#xff1a;显示开启文件abc.txt的进程 lsof -c abc&#xff1a;显示abc进…...

【c++】string类---标准库中的string类

1. 为什么要学习string类 1.1 C语言中的字符串 C语言中&#xff0c;字符串是以\0结尾的一些字符的集合&#xff0c;为了操作方便&#xff0c;C标准库中提供了一些str系列 库函数&#xff0c;但是这些库函数与字符串是分离开的&#xff0c;不太符合OOP的思想&#xff0c;而且…...

GO语言学习笔记(与Java的比较学习)(五)

Map 概念 map 是引用类型&#xff0c;可以使用如下声明&#xff1a; var map1 map[keytype]valuetype var map1 map[string]int 在声明的时候不需要知道 map 的长度&#xff0c;map 是可以动态增长的。 未初始化的 map 的值是 nil&#xff08;即零值为nil&#xff09;&…...

Sora:探索大型视觉模型的前世今生、技术内核及未来趋势

Sora&#xff0c;一款由OpenAI在2024年2月推出的创新性文生视频的生成式AI模型&#xff0c;能够依据文字说明&#xff0c;创作出既真实又富有想象力的场景视频&#xff0c;展现了其在模拟现实世界方面的巨大潜能。本文基于公开技术文档和逆向工程分析&#xff0c;全面审视了Sor…...

基于springboot实现图书馆管理系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现图书馆管理系统演示 摘要 电脑的出现是一个时代的进步&#xff0c;不仅仅帮助人们解决了一些数学上的难题&#xff0c;如今电脑的出现&#xff0c;更加方便了人们在工作和生活中对于一些事物的处理。应用的越来越广泛&#xff0c;通过互联网我们可以更方便地…...

MATLAB环境下基于高斯滤波器-广义拉普拉斯算子的细胞核自动检测

作为病理图像分析的基础&#xff0c;细胞核检测可为细胞形态、纹理等多种相关分析提供支持&#xff0c;对于临床诊断具有重要意义。但是细胞核的人工识别过程十分费时费力&#xff0c;并且不同医生之间存在主观标注差异。因此&#xff0c;利用计算机技术进行自动检测能够更为客…...

【探索AI】十一 深度学习之第1周:深度学习概述与基础

深度学习概述与基础 深度学习的发展历史与现状神经网络的基本原理前向传播与反向传播算法常见的激活函数与优化算法深度学习框架&#xff08;如TensorFlow或PyTorch&#xff09;进行基础操作 深度学习的发展历史与现状 深度学习的发展历史可以追溯到上世纪40年代&#xff0c;当…...

【简说八股】Spring事务失效可能是哪些原因?

Spring事务介绍 Spring事务是指在Spring框架中对数据库操作进行管理的一种机制&#xff0c;它确保一组数据库操作要么完全执行成功&#xff08;提交&#xff09;&#xff0c;要么完全不执行&#xff08;回滚&#xff09;&#xff0c;从而保持数据一致性和完整性。 Spring框架…...

【语音识别】- CTC损失计算的原理

文章目录 1.符号定义与目标函数2.前向计算 α s ( t ) \alpha_s(t) α...

MySQL字符集和比较规则

MySQL字符集和比较规则 字符集和比较规则简介 字符集&#xff1a; 描述字符与二进制数据的映射关系 比较规则&#xff1a;比较指定字符集中的字符的规则 字符集 我们知道&#xff0c;计算机无法直接存储字符串&#xff0c;实际存储的都是二进制数据。字符集是有限的&#xff…...

备忘录模式(Memento Pattern)

定义 备忘录模式&#xff08;Memento Pattern&#xff09;是一种行为设计模式&#xff0c;它允许在不破坏封装性的前提下捕获一个对象的内部状态&#xff0c;并在以后将对象恢复到该状态。备忘录模式通常用于实现撤销操作&#xff08;Undo&#xff09;或历史记录&#xff08;H…...

LeetCode 刷题 [C++] 第121题.买卖股票的最佳时机

题目描述 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的…...

ORACLE 基础

一.ORACLE简介 1.1什么是oracle ORACLE 数据库系统是美国 ORACLE 公司&#xff08;甲骨文&#xff09;提供的以分布式数据库为核心的一组软件产品&#xff0c;是目前最流行的客户/服务器(CLIENT/SERVER)或 B/S 体系结构的数据库之一。 ORACLE 通常应用于大型系统的数据库产品。…...

Adobe illustrator CEP插件调试

1.创建插件CEP面板&#xff0c;可以参考&#xff1a;http://blog.nullice.com/%E6%8A%80%E6%9C%AF/CEP-%E5%BC%80%E5%8F%91%E6%95%99%E7%A8%8B/%E6%8A%80%E6%9C%AF-CEP-%E5%BC%80%E5%8F%91%E6%95%99%E7%A8%8B-Adobe-CEP-%E6%89%A9%E5%B1%95%E5%BC%80%E5%8F%91%E6%95%99%E7%A8%8…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...