数据结构——八大排序(上)
数据结构中的八大排序算法是计算机科学领域经典的排序方法,它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍:
一、插入排序(Insertion Sort)
- 核心思想:将数组中的所有元素依次跟前面已经排好的元素相比较,如果选择的元素比已排序的元素小,则交换,再和前一个比较,直到全部元素都比较过。
- 时间复杂度:O(n^2),其中n是待排序元素的个数。在元素接近有序时,时间复杂度可以降低到O(n)。
- 空间复杂度:O(1),因为排序过程中只需要常量的额外空间。
- 稳定性:稳定,即相同元素在排序后的相对位置不变。
package 排序;import java.util.Arrays;public class Insert{//插入排序public static void main(String[] args) {int[] arr= {5,7,4,2,0,3,1,6};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int i=1;i<arr.length;i++) {for(int j=i-1;j>=0;j--) {if(arr[j]>arr[j+1]) {int temp =arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}else {break;}}}}
}
二、希尔排序(Shell Sort)
- 核心思想:希尔排序是插入排序的一种优化版本,也称为缩小增量排序。它先将数组分成若干子数组,每个子数组进行插入排序,然后逐渐缩小子数组的大小,直到整个数组有序。
- 时间复杂度:不固定,但通常在O(n2)之间,取决于gap的取值方法。
- 空间复杂度:O(1)。
- 稳定性:不稳定,因为相同元素可能在不同的子数组中进行排序,导致相对位置改变。
package 排序;import java.util.Arrays;public class Shell{//希尔排序(缩小增量)public static void main(String[] args) {int[] arr= {5,7,4,2,0,3,1,6};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int grep=arr.length/2;grep>0;grep=grep/2) { for(int i=grep;i<arr.length;i++) {for(int j=i-grep;j>=0;j=j-grep) {if(arr[j]>arr[j+grep]) {int temp =arr[j];arr[j]=arr[j+grep];arr[j+grep]=temp;}else {break;}}}}}
}
三、冒泡排序(Bubble Sort)
- 核心思想:相邻两个元素进行比较,如果前一个比后一个大,则交换它们的位置。这样,每一轮循环都会将一个最大的元素“冒泡”到数组的末尾。
- 时间复杂度:O(n^2),因为每一轮都需要遍历整个数组。
- 空间复杂度:O(1)。
- 稳定性:稳定,因为相同元素不会进行交换。
package 排序;import java.util.Arrays;public class Bubble{//冒泡public static void main(String[] args) {int[] arr= {5,6,71,25,31,42,36,9,4};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int j=0;j<arr.length;j++) {for(int i=0;i<arr.length-1;i++) {if(arr[i]>arr[i+1]) {int temp =arr[i];arr[i]=arr[i+1];arr[i+1]=temp;}}}}
}
四、快速排序(Quick Sort)
- 核心思想:选择一个元素作为基准(pivot),将数组分成两部分,一部分小于基准,一部分大于基准。然后递归地对这两部分进行排序。
- 时间复杂度:平均情况下为O(nlogn),但在最坏情况下(如数组已经有序)会蜕化为冒泡排序,时间复杂度为O(n^2)。不过,通过随机选择基准或三数取中法等方法可以降低最坏情况的发生概率。
- 空间复杂度:O(logn)(递归调用栈空间),但在最坏情况下会达到O(n)(当数组极度不平衡时)。
- 稳定性:不稳定,因为相同元素可能在不同的分区过程中被交换。
package 排序;import java.util.Arrays;public class Quick{//快速排序public static void main(String[] args) {int[] arr= {5,6,71,25,36,9,4};int left=0;int right=arr.length-1;sort(arr,left,right);System.out.println(Arrays.toString(arr));}private static void sort(int[] arr,int left,int right) {if(left>=right) {return;}int base=arr[left];int i=left;int j=right;while(i!=j) {while(arr[j]>=base&&i<j) {j--;}//i游标从前往后走找比基准数大的while(arr[i]<=base&&i<j) {i++;}//i和j进行交换int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}//i和j相遇 基准数和相遇位置进行交换arr[left]=arr[i];arr[i]=base;//排序左边sort(arr,left,i-1);//排序右边sort(arr,i+1,right);}}
相关文章:
数据结构——八大排序(上)
数据结构中的八大排序算法是计算机科学领域经典的排序方法,它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍: 一、插入排序(Insertion Sort) 核心思想:将数组中的所有元素依次跟前面已经排好的元…...
vxe-table 导入导出功能全解析
一、vxe-table 导入导出功能概述 vxe-table 的导入导出功能在数据处理中具有至关重要的作用。在现代数据管理和处理的场景中,高效地导入和导出数据是提高工作效率的关键。 对于导入功能而言,它允许用户将外部的表格数据,如 Excel 文件&…...
常用STL的操作以及特点
C 标准模板库(STL)提供了很多常用的数据结构和算法,极大简化了开发工作。STL 包括容器(如 vector、list、map 等)、算法(如排序、查找等)以及迭代器。以下是一些常用 STL 容器的操作以及它们的特…...
025 elasticsearch索引管理-Java原生客户端
文章目录 pom.xml1创建索引2.创建索引并设置settings信息3.创建索引并设置mapping信息4.删除索引库5.给未设置mapping的索引设置mapping elasticsearch版本7.10.2,要求java客户端与之相匹配,推荐Springboot版本是2.3以上版本 依赖配置使用的是JUnit 5&am…...
Gin框架操作指南10:服务器与高级功能
官方文档地址(中文):https://gin-gonic.com/zh-cn/docs/ 注:本教程采用工作区机制,所以一个项目下载了Gin框架,其余项目就无需重复下载,想了解的读者可阅读第一节:Gin操作指南&#…...
AIGC技术的学习 系列一
文章目录 前言一、AIGC技术演进1.1 图像视频生成1.2. 文本生成1.3. 多模态生成1.4. 小结二、CAD&CAE软件介绍2.1. CAD软件2.2. CAE软件2.3. 小结三、AIGC技术与CAD&CAE软件的集成案例3.1. 土建设计领域3.2. 机械设计领域四、结语五、参考文献总结前言 在全球智能制造的…...
Milvus×Dify半小时轻松构建RAG系统
最近,检索增强生成(RAG)技术在AI界引起了广泛关注。作为一种将知识库与生成模型结合的新型架构,RAG大大提升了AI应用的实际表现。而在构建RAG系统时,Milvus作为业界领先的开源向量数据库,扮演着关键角色。本…...
wireshark 解密浏览器https数据包
一、导出浏览器证书有两种方法 1、在浏览器快捷方式追加启动参数: --ssl-key-log-file"d:\log\2.log" C:\Users\Administrator\AppData\Local\Google\Chrome\Application\chrome.exe --ssl-key-log-file"d:\log\2.log" 2、环境变量中新建用…...
【HTML】构建网页的基石
我的主页:2的n次方_ HTML 是一种超文本标记语言,不仅有文本,还能包含图片,音频等 1. HTML 的文件基本结构 html 标签是整个 html 文件的最顶层标签,head 标签中写页面的属性,body 标签是页面中显示的…...
rust不允许在全局区定义普通变量!
文章目录 C 中的全局变量Rust 中的全局变量设计哲学的体现 在 C 和 Rust 中,全局变量的处理方式体现了这两种语言设计哲学上的一些根本性差异: C 中的全局变量 C 允许在全局作用域中定义变量。这些变量在程序的整个生命周期内都存在,从程序开…...
量化投资中的数据驱动决策:大数据如何改变金融市场
随着科技的进步,金融行业迎来了前所未有的变革,量化投资作为其中的代表,逐渐成为投资市场的主流。量化投资是基于数学模型、数据分析以及算法策略的投资方式,与传统依赖经验和直觉的投资方法相比,它的核心优势在于能够…...
MySQL 设计数据表
一个数据表主要包含信息有 : 表名、主键、字段、数据类型、索引,本节主要介绍表的命名规范、字段命名、字段的数据类型选择。 新建的表都是新建在 “item_name” 数据库中的,新建 “item_name” 数据库命令如下 : CREATE DATABASE item_name;新建数据库…...
【大数据技术基础 | 实验一】配置SSH免密登录
文章目录 一、实验目的二、实验要求三、实验原理(一)大数据实验一体机(二)SSH免密认证 四、实验环境五、实验内容和步骤(一)搭建集群服务器(二)添加域名映射(三ÿ…...
地级市碳排放效率测算2006-2021年
为了测算碳排放效率,研究者们采用了多种方法,其中超效率SBM(Slack-Based Measure)和超效率CCR(Charnes, Cooper and Rhodes)模型是常用的两种方法。这些模型可以有效地评估决策单元的相对有效性,…...
周易解读:四象
四 象 在前面呢,我是讲完了太极与两仪的知识。这一节,我们来讲解四象的内容。 关于四象的知识,它在正式的周易的经文里面,它并没有多少用处。但是呢,在基础知识的学习里面,四象的知识,大家是…...
Java设计模式梳理:行为型模式(策略,观察者等)
行为型模式 行为型模式关注的是各个类之间的相互作用,将职责划分清楚,使得我们的代码更加地清晰。 策略模式 策略模式太常用了,所以把它放到最前面进行介绍。它比较简单,我就不废话,直接用代码说事吧。 下面设计的…...
【MySQL】入门篇—基本数据类型:使用LIMIT限制结果集
为了提高查询效率和用户体验,MySQL提供了LIMIT子句,用于限制查询结果的行数。LIMIT不仅可以提高性能,还可以帮助用户快速获取所需的数据,尤其在分页显示数据时非常有用。 应用场景: 分页显示:在网页应用中…...
PostgreSQL与MySQL在语法上的区别
PostgreSQL与MySQL在语法上的区别 在数据库管理系统中,PostgreSQL和MySQL都是非常受欢迎的选择。虽然它们都是一种关系型数据库管理系统(RDBMS),但它们在语法上有一些显著的区别。本文将介绍PostgreSQL和MySQL在语法上的主要区别。 数据类型 PostgreS…...
frameworks 之InputDispatcher
frameworks 之InputDispatcher 1. 填充Iq2.进入循环3.进入oq4. 发布消息,并将数据放进去wq5. 接收消息6. 移除wq android 输入事件 主要分 2个流程 事件读取 和 事件分发。本文讲解事件分发流程。 涉及到的类如下 -frameworks/native/services/inputflinger/Input…...
ESP32-IDF GPIO 专题
目录 一、基本介绍1、配置结构体2、API2.1 gpio_config2.2 gpio_reset_pin2.3 gpio_set_intr_type2.4 gpio_intr_enable2.5 gpio_intr_disable2.6 gpio_set_level2.7 gpio_get_level2.8 gpio_set_direction2.9 gpio_set_pull_mode2.10 gpio_isr_register2.11 gpio_install_isr_…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...
