数据结构——八大排序(上)
数据结构中的八大排序算法是计算机科学领域经典的排序方法,它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍:
一、插入排序(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_…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...
