5种排序算法
文章目录
- 一,排序算法时间复杂度比较
- 二,插入排序
- 三,冒泡排序
- 四,快速排序
- 五,堆排序
- 六,二分归并排序
一,排序算法时间复杂度比较
| 算法 | 最坏情况下 | 平均情况下 |
|---|---|---|
| 插入排序 | O(n² ) | O(n²) |
| 冒泡排序 | O(n²) | O(n²) |
| 快速排序 | O(n²) | O(nlogn) |
| 堆排序 | O(nlogn) | O(nlogn) |
| 二分归并排序 | O(nlogn) | O(nlogn) |
二,插入排序
假设原始序列为:[5,7,1,3,6,2,4]
首先假设第一个元素5已经排好,然后插入第二个元素7但是7比5大所以7放在5的右边,接着是第三个元素1,1比7小所以再7左边并且1比5小所以放在5的左边。第四个元素3于7比较比7小在7左边并且比5小所以在5左边但是3比1小所以插入到1和5之间,其他的类似。。。。
| 原始序列 | 5 | 7 | 1 | 3 | 6 | 2 | 4 |
|---|---|---|---|---|---|---|---|
| 插入零次 | 5 | 7 | 1 | 3 | 6 | 2 | 4 |
| 插入一次 | 5 | 7 | 1 | 3 | 6 | 2 | 4 |
| 插入二次 | 1 | 5 | 7 | 3 | 6 | 2 | 4 |
| 插入三次 | 1 | 3 | 5 | 7 | 6 | 2 | 4 |
| 插入四次 | 1 | 3 | 5 | 6 | 7 | 2 | 4 |
| 插入五次 | 1 | 2 | 3 | 5 | 6 | 7 | 4 |
| 插入六次 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
a = [5,7,1,3,6,2,4]
n = len(a)
for i in range(1, n):key = a[i] # 当前待插入元素j = i - 1 # 已排序部分的最后一个元素的索引while j >= 0 and a[j] > key:a[j + 1] = a[j] # 向后移动元素j -= 1a[j + 1] = key # 插入元素到正确位置
print(a)
#[1, 2, 3, 4, 5, 6, 7]
三,冒泡排序
假设原始序列为:[5,7,1,3,6,2,4]
首先5和7比较,5比7小不交换顺序,7和1比较,7比1大交换顺序,7和3比较,7比3大交换顺序,7和6比较7比6大交换顺序,7和4比较,7比4大交换顺序。以此类推
| 原始序列 | 5 | 7 | 1 | 3 | 6 | 2 | 4 |
|---|---|---|---|---|---|---|---|
| 冒泡一次 | 5 | 1 | 3 | 6 | 2 | 4 | 7 |
| 冒泡二次 | 1 | 3 | 5 | 2 | 4 | 6 | 7 |
| 冒泡三次 | 1 | 3 | 2 | 4 | 5 | 6 | 7 |
| 冒泡四次 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
a = [5,7,1,3,6,2,4]
n = len(a)
for i in range(n):for j in range(0, n-i-1):if a[j] > a[j+1]:a[j], a[j+1] = a[j+1], a[j]
print(a)
#[1, 2, 3, 4, 5, 6, 7]
四,快速排序
假设原始序列为:[5,7,1,3,6,2,4]
首先以第一个元素5为划分的标准,从前面找第一个比5大的从后面找第一个比5小的交换位置,然后再找下一个比大的和比5小的交换位置。第二次交换是发生在两个相邻的元素之间做的所以说2前面的都比5小,6后面的都比5大所以2的位置是第一个元素5的位置,然后交换2和5的位置,这样5的位置就定下来了,再分别对两边递归调用同样的方法。
| 原始序列 | 5 | 7 | 1 | 3 | 6 | 2 | 4 |
|---|---|---|---|---|---|---|---|
| 交换一次 | 5 | 4 | 1 | 3 | 6 | 2 | 7 |
| 交换二次 | 5 | 4 | 1 | 3 | 2 | 6 | 7 |
| 划分 | 2 | 4 | 1 | 3 | 5 | 6 | 7 |
| 递归运行 | 2 | 4 | 1 | 3 | 5 | 6 | 7 |
a = [5,7,1,3,6,2,4]
def fast_sort(a):if len(a) <= 1:return abasis = a[0]left_num = [i for i in a[1::] if i < basis]middle = [i for i in a if i == basis]right_num = [i for i in a[1::] if i > basis]return fast_sort(left_num) + middle + fast_sort(right_num)
print(fast_sort(a))
#[1, 2, 3, 4, 5, 6, 7]
五,堆排序
pass
六,二分归并排序
它将待排序的列表递归地分成两个子列表,直到每个子列表只包含一个元素。然后,将这些子列表按照顺序合并,形成一个有序的列表。
假设原始序列为:[5,7,1,3,6,2,4]
首先先把序列一份为二 (标注和没标注的),然后对每个子列里面也分别进行二分归并排序,然后把已经排好的子数合并(两个序列的首元素比较哪个小就把哪个拿走,知道一个数组空了就把另一个数组全部接在后面)。
| 原始序列 | 5 | 7 | 1 | 3 | 6 | 2 | 4 |
|---|---|---|---|---|---|---|---|
| 归分 | 5 | 4 | 1 | 3 | 6 | 2 | 7 |
| 递归排序 | 1 | 3 | 4 | 5 | 2 | 6 | 7 |
| 开始组合 | 1 | 3 | 4 | 5 | 2 | 6 | 7 |
| 原 | 3 | 4 | 5 | 2 | 6 | 7 | |
| 新数组 | 1 | ||||||
| 原 | 3 | 4 | 5 | 6 | 7 | ||
| 新数组 | 1 | 2 | |||||
| 原 | 4 | 5 | 6 | 7 | |||
| 新数组 | 1 | 2 | 3 | ||||
| 原 | 5 | 6 | 7 | ||||
| 新数组 | 1 | 2 | 3 | 4 | |||
| 原 | 6 | 7 | |||||
| 新数组 | 1 | 2 | 3 | 4 | 5 | ||
| 原 | |||||||
| 新数组 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
a = [5, 7, 1, 3, 6, 2, 4]def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = arr[:mid]right = arr[mid:]left = merge_sort(left)right = merge_sort(right)return merge(left, right)def merge(left, right):merged = []i = j = 0while i < len(left) and j < len(right):if left[i] <= right[j]:merged.append(left[i])i += 1else:merged.append(right[j])j += 1while i < len(left):merged.append(left[i])i += 1while j < len(right):merged.append(right[j])j += 1return mergedprint(merge_sort(a))
相关文章:
5种排序算法
文章目录 一,排序算法时间复杂度比较二,插入排序三,冒泡排序四,快速排序五,堆排序六,二分归并排序 一,排序算法时间复杂度比较 算法最坏情况下平均情况下插入排序O(n )O(n)冒泡排序O(n)O(n)快速…...
TCP/IP(七)TCP的连接管理(四)
一 全连接队列 nginx listen 参数backlog的意义 nginx配置文件中listen后面的backlog配置 ① TCP全连接队列概念 全连接队列: 也称 accept 队列 ② 查看应用程序的 TCP 全连接队列大小 实验1: ss 命令查看 LISTEN状态下 Recv-Q/Send-Q 含义附加:…...
LeetCode【84】柱状图中的最大矩形
题目: 思路: https://blog.csdn.net/qq_28468707/article/details/103682528 https://www.jianshu.com/p/2b9a36a548fa 清晰 代码: public int largestRectangleArea(int[] heights) {int[] heightadd new int[heights.length 1];for (i…...
C++:关于模拟实现vector和list中迭代器模块的理解
文章目录 list和vector的迭代器对比list的实现过程完整代码 本篇是关于vector和list的模拟实现中,关于迭代器模块的更进一步理解,以及在前文的基础上增加对于反向迭代器的实现和库函数的对比等 本篇是写于前面模拟实现的一段时间后,重新回头…...
HTML 笔记 表格
1 表格基本语法 tr:table row th:table head 2 表格属性 2.1 基本属性 表格的基本属性是指表格的行、列和单元格但并不是每个表格的单元格大小都是统一的,所以需要设计者通过一些属性参数来修改表格的样子,让它们可以更更多样…...
3.1 C/C++ 使用字符与指针
C/C语言是一种通用的编程语言,具有高效、灵活和可移植等特点。C语言主要用于系统编程,如操作系统、编译器、数据库等;C语言是C语言的扩展,增加了面向对象编程的特性,适用于大型软件系统、图形用户界面、嵌入式系统等。…...
[代码学习]einsum详解
einsum详解 该函数用于对一组输入 Tensor 进行 Einstein 求和,该函数目前仅适用于paddle的动态图。 Einstein 求和是一种采用 Einstein 标记法描述的 Tensor 求和,输入单个或多个 Tensor,输出单个 Tensor。 paddle.einsum(equation, *opera…...
女性必看——“黄体破裂”到底有多可怕?
前几天的亚运会上发生了这样一件事: 雅思敏(化名)是一名国外皮划艇运动员,在亚运会上奋力完成皮划艇比赛后,突然开始 剧烈腹痛、面色苍白,大汗淋漓,经过进一步检查,确诊卵巢黄体破裂…...
colab切换目录的解决方案
大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...
基于SSM的生活缴费系统的设计与实现
末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:采用JSP技术开发 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目&#x…...
【WebLogic】WebLogic 2023年7月补丁导致JVM崩溃的解决方案
受影响版本: Oracle WebLogic 12c(12.2.1.4.0)Oracle WebLogic 14c(14.1.1.0.0) 问题描述: Oracle官方在2023年7月发布的最新版本的OPatch(13.9.4.2.13)存在一个新出现的Bug&#…...
简单OpenSL ES学习
初识OpenSL ES OpenSL ESObjects和Interfaces 所有的Object在OpenSl里面我们拿到的都是一个SLObjectItf:SLObjectItf_创建引擎创建过程要设计得这么麻烦?(object的生命周期)这么多参数,参数类型这么多学习障碍太大&…...
Linux网络编程- struct packet_mreq setsockopt()
struct packet_mreq struct packet_mreq 是一个数据结构,用于 Linux 中的原始数据包套接字,当我们想改变套接字的行为以接收特定类型的数据包时,它与 setsockopt() 函数配合使用。 下面是 struct packet_mreq 的定义: struct p…...
C++学习day4
作业: 1> 思维导图 2> 整理代码 1. 拷贝赋值函数课上代码 //拷贝赋值函数课上代码 #include<iostream> using namespace std;//创建类 class Stu { private://私有的string name;int socer;int *age;//此处注意用到指针类型 public://共有的//无参构…...
从零学算法54
54.给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 螺旋遍历:从左上角开始,按照 向右、向下、向左、向上 的顺序 依次 提取元素,然后再进入内部一层重复相同的步骤,直到…...
Logback日志框架使用详解以及如何Springboot快速集成
Logback简介 日志系统是用于记录程序的运行过程中产生的运行信息、异常信息等,一般有8个级别,从低到高为All < Trace < Debug < Info < Warn < Error < Fatal < OFF off 最高等级,用于关闭所有日志记录fatal 指出每个…...
Nginx概念
Nginx概念 Nginx 是一款面向性能设计的 HTTP 服务器,相较于 Apache、lighttpd 具有占有内存少,稳定性高等优势,同时也是一个非常高效的反向代理、负载平衡服务器 nginx使用的是反应器模式,主事件循环等待操作系统发出准备事件的信…...
vim基础指令(自用)
这个是自己随便写的,类似于笔记 vim 多模式编辑器 查看指令: gg: 定位光标到最开始行 shift(按)g 定位到最结尾行 nshift(按)g 定位到任意行 shift$ 定位到本行结尾 0 定位到本行开头 w:跨单词移动 h.j.k,l: 左下上右 …...
【centos7安装ElasticSearch】
概述 最近工作中有用到ES ,当然少不了自己装一个服务器捣鼓。本文的ElasticSearch 的版本: 7.17.3 一、下载 ElasticSearch 点此下载 下载完成后上传至 Linux 服务器,本文演示放在: /root/ 下,进行解压࿱…...
ElementPlus Switch 开关基础使用
昨天开发用到开关组件 后台返回字段是 can_write 默认是0 or 1 但是Switch 组件绑定的默认值默认是 true or false 直接绑定会导致默认是关闭状态 在页面一加载 值发生变化时 会自己调用 查了文档 需要使用 active-value 和 inactive-value 来指定绑定的数据类型 …...
Qwen3-TTS开源镜像实操:与LangChain集成构建多语种AI Agent语音接口
Qwen3-TTS开源镜像实操:与LangChain集成构建多语种AI Agent语音接口 1. 项目概述与核心价值 Qwen3-TTS-12Hz-1.7B-VoiceDesign是一个强大的多语言文本转语音模型,专为现代AI应用场景设计。这个模型最大的特点是能够处理10种主要语言,包括中…...
NVIDIA Profile Inspector显卡性能调优实战指南:从问题诊断到专业配置
NVIDIA Profile Inspector显卡性能调优实战指南:从问题诊断到专业配置 【免费下载链接】nvidiaProfileInspector 项目地址: https://gitcode.com/gh_mirrors/nv/nvidiaProfileInspector 一、显卡性能异常定位:精准找到游戏卡顿根源 游戏性能问题…...
VS Code玩转Arduino开发——插件配置与工程搭建全攻略
1. 为什么选择VS Code开发Arduino? 很多Arduino爱好者刚开始接触开发时,都会使用官方提供的Arduino IDE。这个编辑器确实简单易用,但随着项目复杂度提升,你会发现它缺少很多现代编辑器该有的功能——代码补全、语法高亮、项目管理…...
RWKV7-1.5B-G1A快速原型:使用VMware虚拟机搭建隔离的模型测试环境
RWKV7-1.5B-G1A快速原型:使用VMware虚拟机搭建隔离的模型测试环境 1. 为什么需要虚拟机测试环境 在测试新的大语言模型时,最头疼的问题就是环境配置冲突。你可能遇到过这种情况:好不容易装好CUDA驱动,结果发现和现有项目的PyTor…...
从零封装Vue版JSMpeg播放器:支持截图/录制/旋转的直播流组件开发指南
从零封装Vue版JSMpeg播放器:支持截图/录制/旋转的直播流组件开发指南 1. 技术选型与架构设计 在Web端实现低延迟视频直播需要解决三个核心问题:编解码效率、传输协议选择和渲染性能。基于JSMpeg的方案优势在于: 超低延迟(可达50ms…...
Z-Image Turbo提示词调试技巧:从失败案例反推有效表达逻辑
Z-Image Turbo提示词调试技巧:从失败案例反推有效表达逻辑 1. 为什么提示词调试如此重要 如果你用过AI绘画工具,一定遇到过这种情况:脑子里想的是赛博朋克少女,生成出来的却是模糊不清的怪异图像。这不是模型的问题,…...
基于Mirage Flow的Java智能助手开发:SpringBoot集成与API封装
基于Mirage Flow的Java智能助手开发:SpringBoot集成与API封装 最近在做一个内部知识库项目,需要给系统加个智能问答的“大脑”。一开始想直接用现成的SaaS服务,但考虑到数据安全和定制化需求,还是决定自己动手,把大模…...
【PyCon 2024闭门报告首发】:基于237个微基准测试的Python 3.14 JIT编译策略矩阵分析
第一章:PyCon 2024闭门报告核心结论与JIT演进全景核心共识:CPython JIT不再追求“全量即时编译” PyCon 2024闭门技术委员会明确指出,CPython 3.13 的JIT策略已从早期“通用LLVM后端”转向聚焦于“热点字节码的增量式优化”。其目标并非替代C…...
【BLE系列-第四篇】数据链路层(LL)实战:广播与连接参数优化指南
1. BLE数据链路层核心参数解析 低功耗蓝牙(BLE)的数据链路层(LL)就像交通系统中的红绿灯和道路规划,它决定了设备间如何高效、稳定地建立通信。在实际开发中,我经常遇到工程师对着几十个参数发愁࿱…...
BongoCat:让桌面交互充满生命力的开源伴侣
BongoCat:让桌面交互充满生命力的开源伴侣 【免费下载链接】BongoCat 让呆萌可爱的 Bongo Cat 陪伴你的键盘敲击与鼠标操作,每一次输入都充满趣味与活力! 项目地址: https://gitcode.com/gh_mirrors/bong/BongoCat 在数字化工作与娱乐…...
