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

数据结构——八大排序(上)

        数据结构中的八大排序算法是计算机科学领域经典的排序方法,它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍:

一、插入排序(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);}}

相关文章:

数据结构——八大排序(上)

数据结构中的八大排序算法是计算机科学领域经典的排序方法&#xff0c;它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍&#xff1a; 一、插入排序&#xff08;Insertion Sort&#xff09; 核心思想&#xff1a;将数组中的所有元素依次跟前面已经排好的元…...

vxe-table 导入导出功能全解析

一、vxe-table 导入导出功能概述 vxe-table 的导入导出功能在数据处理中具有至关重要的作用。在现代数据管理和处理的场景中&#xff0c;高效地导入和导出数据是提高工作效率的关键。 对于导入功能而言&#xff0c;它允许用户将外部的表格数据&#xff0c;如 Excel 文件&…...

常用STL的操作以及特点

C 标准模板库&#xff08;STL&#xff09;提供了很多常用的数据结构和算法&#xff0c;极大简化了开发工作。STL 包括容器&#xff08;如 vector、list、map 等&#xff09;、算法&#xff08;如排序、查找等&#xff09;以及迭代器。以下是一些常用 STL 容器的操作以及它们的特…...

025 elasticsearch索引管理-Java原生客户端

文章目录 pom.xml1创建索引2.创建索引并设置settings信息3.创建索引并设置mapping信息4.删除索引库5.给未设置mapping的索引设置mapping elasticsearch版本7.10.2&#xff0c;要求java客户端与之相匹配&#xff0c;推荐Springboot版本是2.3以上版本 依赖配置使用的是JUnit 5&am…...

Gin框架操作指南10:服务器与高级功能

官方文档地址&#xff08;中文&#xff09;&#xff1a;https://gin-gonic.com/zh-cn/docs/ 注&#xff1a;本教程采用工作区机制&#xff0c;所以一个项目下载了Gin框架&#xff0c;其余项目就无需重复下载&#xff0c;想了解的读者可阅读第一节&#xff1a;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系统

最近&#xff0c;检索增强生成&#xff08;RAG&#xff09;技术在AI界引起了广泛关注。作为一种将知识库与生成模型结合的新型架构&#xff0c;RAG大大提升了AI应用的实际表现。而在构建RAG系统时&#xff0c;Milvus作为业界领先的开源向量数据库&#xff0c;扮演着关键角色。本…...

wireshark 解密浏览器https数据包

一、导出浏览器证书有两种方法 1、在浏览器快捷方式追加启动参数&#xff1a; --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】构建网页的基石

我的主页&#xff1a;2的n次方_ HTML 是一种超文本标记语言&#xff0c;不仅有文本&#xff0c;还能包含图片&#xff0c;音频等 1. HTML 的文件基本结构 html 标签是整个 html 文件的最顶层标签&#xff0c;head 标签中写页面的属性&#xff0c;body 标签是页面中显示的…...

rust不允许在全局区定义普通变量!

文章目录 C 中的全局变量Rust 中的全局变量设计哲学的体现 在 C 和 Rust 中&#xff0c;全局变量的处理方式体现了这两种语言设计哲学上的一些根本性差异&#xff1a; C 中的全局变量 C 允许在全局作用域中定义变量。这些变量在程序的整个生命周期内都存在&#xff0c;从程序开…...

量化投资中的数据驱动决策:大数据如何改变金融市场

随着科技的进步&#xff0c;金融行业迎来了前所未有的变革&#xff0c;量化投资作为其中的代表&#xff0c;逐渐成为投资市场的主流。量化投资是基于数学模型、数据分析以及算法策略的投资方式&#xff0c;与传统依赖经验和直觉的投资方法相比&#xff0c;它的核心优势在于能够…...

MySQL 设计数据表

一个数据表主要包含信息有 : 表名、主键、字段、数据类型、索引&#xff0c;本节主要介绍表的命名规范、字段命名、字段的数据类型选择。 新建的表都是新建在 “item_name” 数据库中的&#xff0c;新建 “item_name” 数据库命令如下 : CREATE DATABASE item_name;新建数据库…...

【大数据技术基础 | 实验一】配置SSH免密登录

文章目录 一、实验目的二、实验要求三、实验原理&#xff08;一&#xff09;大数据实验一体机&#xff08;二&#xff09;SSH免密认证 四、实验环境五、实验内容和步骤&#xff08;一&#xff09;搭建集群服务器&#xff08;二&#xff09;添加域名映射&#xff08;三&#xff…...

地级市碳排放效率测算2006-2021年

为了测算碳排放效率&#xff0c;研究者们采用了多种方法&#xff0c;其中超效率SBM&#xff08;Slack-Based Measure&#xff09;和超效率CCR&#xff08;Charnes, Cooper and Rhodes&#xff09;模型是常用的两种方法。这些模型可以有效地评估决策单元的相对有效性&#xff0c…...

周易解读:四象

四 象 在前面呢&#xff0c;我是讲完了太极与两仪的知识。这一节&#xff0c;我们来讲解四象的内容。 关于四象的知识&#xff0c;它在正式的周易的经文里面&#xff0c;它并没有多少用处。但是呢&#xff0c;在基础知识的学习里面&#xff0c;四象的知识&#xff0c;大家是…...

Java设计模式梳理:行为型模式(策略,观察者等)

行为型模式 行为型模式关注的是各个类之间的相互作用&#xff0c;将职责划分清楚&#xff0c;使得我们的代码更加地清晰。 策略模式 策略模式太常用了&#xff0c;所以把它放到最前面进行介绍。它比较简单&#xff0c;我就不废话&#xff0c;直接用代码说事吧。 下面设计的…...

【MySQL】入门篇—基本数据类型:使用LIMIT限制结果集

为了提高查询效率和用户体验&#xff0c;MySQL提供了LIMIT子句&#xff0c;用于限制查询结果的行数。LIMIT不仅可以提高性能&#xff0c;还可以帮助用户快速获取所需的数据&#xff0c;尤其在分页显示数据时非常有用。 应用场景&#xff1a; 分页显示&#xff1a;在网页应用中…...

PostgreSQL与MySQL在语法上的区别

PostgreSQL与MySQL在语法上的区别 在数据库管理系统中&#xff0c;PostgreSQL和MySQL都是非常受欢迎的选择。虽然它们都是一种关系型数据库管理系统(RDBMS)&#xff0c;但它们在语法上有一些显著的区别。本文将介绍PostgreSQL和MySQL在语法上的主要区别。 数据类型 PostgreS…...

frameworks 之InputDispatcher

frameworks 之InputDispatcher 1. 填充Iq2.进入循环3.进入oq4. 发布消息&#xff0c;并将数据放进去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_…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

用鸿蒙HarmonyOS5实现国际象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的国际象棋小游戏的完整实现代码&#xff0c;使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├── …...

AWSLambda之设置时区

目标 希望Lambda运行的时区是东八区。 解决 只需要设置lambda的环境变量TZ为东八区时区即可&#xff0c;即Asia/Shanghai。 参考 使用 Lambda 环境变量...

短视频时长预估算法调研

weighted LR o d d s T p 1 − p ( 1 − p ) o d d s T p ( T p o d d s ∗ p ) o d d s p o d d s T o d d s odds \frac{Tp}{1-p} \newline (1-p)odds Tp \newline (Tp odds * p) odds \newline p \frac{odds}{T odds} \newline odds1−pTp​(1−p)oddsTp(Tpodds…...