【唐叔学算法】第19天:交换排序-冒泡排序与快速排序的深度解析及Java实现
引言
排序算法是计算机科学中的基础问题,而交换排序作为其中一类经典的排序方法,因其简单直观的思想和易于实现的特点,在初学者中广受欢迎。交换排序的核心思想是通过不断交换相邻元素来达到排序的目的。本文将深入探讨两种典型的交换排序算法:冒泡排序和快速排序,分析它们的原理、实现细节、时间复杂度和空间复杂度,并通过Java代码进行具体实现。
冒泡排序:简单却经典的排序算法
算法原理
冒泡排序(Bubble Sort)是一种基础的交换排序算法,其核心思想是通过重复地遍历待排序的序列,依次比较相邻的两个元素,如果它们的顺序错误就交换它们的位置。这样,每一轮遍历都会将当前未排序部分的最大(或最小)元素“冒泡”到序列的末尾。
算法步骤
- 从序列的起始位置开始,比较相邻的两个元素。
- 如果前一个元素大于后一个元素,则交换它们的位置。
- 对序列中的每一对相邻元素重复上述操作,直到序列末尾。
- 重复以上步骤,直到没有需要交换的元素为止。
时间复杂度与空间复杂度
- 时间复杂度:
- 最坏情况:O(n²),当输入序列是逆序时,需要进行n(n-1)/2次比较和交换。
- 最好情况:O(n),当输入序列已经有序时,只需进行一次遍历即可。
- 平均情况:O(n²)。
- 空间复杂度:O(1),冒泡排序是原地排序算法,不需要额外的存储空间。
Java实现
public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {boolean swapped = false; // 优化:如果某一轮没有交换,说明已经有序for (int j = 0; j < n - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 交换int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true;}}if (!swapped) {break; // 如果没有交换,提前退出}}}public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);System.out.println("Sorted array: ");for (int i : arr) {System.out.print(i + " ");}}
}
快速排序:高效的分治排序算法
算法原理
快速排序(Quick Sort)是一种基于分治思想的交换排序算法。其核心思想是选择一个“基准元素”(pivot),将序列分为两部分:一部分比基准元素小,另一部分比基准元素大,然后递归地对这两部分进行排序。
算法步骤
- 选择一个基准元素(通常选择第一个元素、最后一个元素或中间元素)。
- 将序列分为两部分:小于基准元素的部分和大于基准元素的部分。
- 对这两部分分别递归地进行快速排序。
- 合并结果。
时间复杂度与空间复杂度
- 时间复杂度:
- 最坏情况:O(n²),当每次选择的基准元素都是序列的最大或最小值时,快速排序会退化为冒泡排序。
- 最好情况:O(n log n),当每次选择的基准元素都能将序列均匀地分为两部分时。
- 平均情况:O(n log n)。
- 空间复杂度:O(log n),快速排序的空间复杂度主要取决于递归调用的栈空间。
Java实现
public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high); // 获取基准元素的位置quickSort(arr, low, pivotIndex - 1); // 递归排序左子序列quickSort(arr, pivotIndex + 1, high); // 递归排序右子序列}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high]; // 选择最后一个元素作为基准int i = low - 1; // i指向小于基准的元素的位置for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;// 交换int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将基准元素放到正确的位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1; // 返回基准元素的位置}public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};quickSort(arr, 0, arr.length - 1);System.out.println("Sorted array: ");for (int i : arr) {System.out.print(i + " ");}}
}
对比与总结
冒泡排序 vs 快速排序
| 特性 | 冒泡排序 | 快速排序 |
|---|---|---|
| 时间复杂度 | O(n²) | 平均 O(n log n),最坏 O(n²) |
| 空间复杂度 | O(1) | O(log n) |
| 稳定性 | 稳定 | 不稳定 |
| 适用场景 | 小规模数据或基本有序数据 | 大规模数据或随机数据 |
选择与应用
- 冒泡排序:虽然时间复杂度较高,但实现简单,适合教学和小规模数据的排序。
- 快速排序:虽然实现稍复杂,但时间复杂度较低,适合处理大规模数据,是实际应用中最常用的排序算法之一。
通过本文的讲解和Java实现,希望读者能够深入理解冒泡排序和快速排序的原理和实现细节,并在实际编程中根据需求灵活选择合适的排序算法。
相关文章:
【唐叔学算法】第19天:交换排序-冒泡排序与快速排序的深度解析及Java实现
引言 排序算法是计算机科学中的基础问题,而交换排序作为其中一类经典的排序方法,因其简单直观的思想和易于实现的特点,在初学者中广受欢迎。交换排序的核心思想是通过不断交换相邻元素来达到排序的目的。本文将深入探讨两种典型的交换排序算…...
合并 Python 中的字典
合并 Python 中的字典 如何在 Python 中合并字典? 这取决于你对“合并”一词的具体定义。 在 Python 中使用 | 操作符合并字典 首先,让我们讨论合并字典的最简单方法,这通常已经足够满足你的需求。 以下是两个字典: >>…...
使用Python实现自动化文档生成工具:提升文档编写效率的利器
友友们好! 我的新专栏《Python进阶》正式启动啦!这是一个专为那些渴望提升Python技能的朋友们量身打造的专栏,无论你是已经有一定基础的开发者,还是希望深入挖掘Python潜力的爱好者,这里都将是你不可错过的宝藏。 在这个专栏中,你将会找到: ● 深入解析:每一篇文章都将…...
uniapp使用live-pusher实现模拟人脸识别效果
需求: 1、前端实现模拟用户人脸识别,识别成功后抓取视频流或认证的一张静态图给服务端。 2、服务端调用第三方活体认证接口,验证前端传递的人脸是否存在,把认证结果反馈给前端。 3、前端根据服务端返回的状态,显示在…...
【JavaSE】【网络原理】初识网络
目录 一、网络互联二、局域网与广域网三、网络通信基础3.1 IP地址3.2 端口号3.3 网络协议3.4 五元组 四、协议分层4.1 OSI七层网络模型4.2 TCP/IP五层(四层)网络模型4.3 网络设备 五、网络数据通信基本流程。5.1 封装和分用5.2 简述过程 一、网络互联 网络互联: 网…...
鸿蒙之路的坑
1、系统 Windows 10 家庭版不可用模拟器 对应的解决方案【坑】 升级系统版本 直接更改密钥可自动升级系统 密钥找对应系统的(例:windows 10专业版) 升级完之后要激活 坑1、升级完后事先创建好的模拟器还是无法启动 解决:删除模拟…...
Python生日祝福烟花
1. 实现效果 2. 素材加载 2个图片和3个音频 shoot_image pygame.image.load(shoot(已去底).jpg) # 加载拼接的发射图像 flower_image pygame.image.load(flower.jpg) # 加载拼接的烟花图 烟花不好去底 # 调整图像的像素为原图的1/2 因为图像相对于界面来说有些大 shoo…...
Ubuntu环境 nginx.conf详解(二)
1、nginx.conf 结构详解: http 块:用于配置 HTTP 服务器的相关设置,包括处理 HTTP 和 HTTPS。 stream 块:用于配置 TCP/UDP 代理服务器,适用于需要进行四层负载均衡的情况。 ... # 全局块 events {...} …...
shardingsphere分库分表项目实践4-sql解析sql改写
为什么要sql解析重写? 如果我们的系统数据库实现了分表,那么我们的sql中表名需要根据参数动态确定,那么代码怎么写? 方案1: 自己手动拼接, 比如 update t_user_${suffix} , ${suffix} 作为一个变量传递…...
mysql数据库中,一棵3层的B+树,假如数据节点大小是1k,那这棵B+可以存多少条记录(2100万的由来)
在MySQL中,3层的B树可以存储的数据量取决于多个因素,包括页大小、每行数据的大小以及索引项的大小。以下是一个详细的计算过程: 一、假设条件 页大小:在InnoDB存储引擎中,B树的每个节点(页)大…...
Git 操作全解:从基础命令到高级操作的实用指南
文章目录 1.基本命令1.初始化仓库2.克隆远程仓库3.查看当前仓库状态4.查看提交日志5.添加文件到暂存区6.提交更改7.查看仓库的配置信息 2.分支操作1.查看所有分支2.创建新分支3.切换名称4.创建并切换到新分支5.删除分支6.查看当前分支 3.合并分支1.合并分支2.解决合并冲突 4.远…...
华院计算参与项目再次被《新闻联播》报道
12月17日,央视《新闻联播》播出我国推进乡村振兴取得积极进展。其中,华院计算参与的江西省防止返贫监测帮扶大数据系统被报道,该系统实现了由原来的“人找人”向“数据找人”的转变,有效提升监测帮扶及时性和有效性,守…...
从一次线上故障聊聊接口自动化测试
1、背景 3月初,运营同事配置了个还未上线的页面到网站首页 banner,导致用户点了报错。尽管这次很明确是运营人为操作失误引起的故障,但过往此类核心页面的访问异常,我们已不是第一次遇见。 从平台整体利益触发,我们各…...
Element-ui的使用教程 基于HBuilder X
文章目录 1.Element-ui简介2.使用HBuilderX 创建一个基于Vue3的项目 (由于是使用的基于Vue3的Element-ui)3.安装element-ui4.在项目里完全引用element-ui5.引用组件6.运行项目 1.Element-ui简介 Element,一套为开发者、设计师和产品经理准备…...
Chapter 03 复合数据类型-1
1.列表 Python内置的一种有序、可变的序列数据类型; 列表的定义: [ ]括起来的逗号分隔的多个元素组成的序列 列表对象的创建: (1)直接赋值 >>> list1 []#创建一个空列表赋值给list1 >>> list…...
【Python知识】Python面向对象编程知识
Python面向对象编程知识 概述1. 类(Class)2. 对象(Object)3. 封装(Encapsulation)4. 继承(Inheritance)5. 多态(Polymorphism)6. 抽象(Abstractio…...
CSharp: Oracle Stored Procedure query table
存储过程查询postgreSQL,Oracle 和sql server,Mysql 有区别。程序调用也是有区别。 oracle sql script: CREATE OR REPLACE PROCEDURE procSelectSchool(paramSchoolId IN char,p_cursor OUT SYS_REFCURSOR ) AS BEGINOPEN p_cursor FORSELECT *FROM SchoolWHERE SchoolId p…...
“协同过滤技术实战”:网上书城系统的设计与实现
2.1 JSP技术介绍 Java Server Pages这三个英文词汇的首字母的组合就是JSP。所以JSP是一个简写的名字,代表动态网页开发技术。JSP与Java的关系可以使用公式表示,即:JSP HTMLJava,HTML就是编写静态内容的标记语言。JSP则是可以编写网…...
Dhatim FastExcel 读写 Excel 文件
Dhatim FastExcel 读写 Excel 文件 一、说明1、主要特点2、应用场景 二、使用方法1、引入依赖2、Sheet 数据3、读取 Excel4、写入 Excel 一、说明 Github 地址:Dhatim FastExcel Dhatim FastExcel是一个高性能、轻量级的Java库,专门用于读取和写入Exce…...
YOLO11全解析:从原理到实战,全流程体验下一代目标检测
前言 一、模型介绍 二、网络结构 1.主干网络(Backbone) 2.颈部网络(Neck) 3.头部网络(Head) 三、算法改进 1.增强的特征提取 2.优化的效率和速度 3.更高的准确性与更少的参数 4.环境适应性强 5.…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)
在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...
