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

时间复杂度为O(n2)的三种简单排序算法

1.冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作。
在这里插入图片描述

/*** 冒泡排序* 原地排序:是* 稳定排序:是* 空间复杂度:O(1)* 时间复杂度:最好O(n)——最坏O(n^2)——平均O(n^2)[有序度推算]* @param arr*/public static void bubbleSort(int[] arr) {int n = arr.length;if(n<=1) return;for(int i=0;i<n;i++) {boolean flag = false;for(int j=0;j<n-i-1;j++) {if(arr[j]>arr[j+1]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;flag = true;}}if(!flag) break;}System.out.print("[ ");for(int i=0;i<n;i++) {System.out.print(arr[i]+" ");}System.out.println("]");}

2.插入排序

我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有⼀个元素,就是数组的第一个元素。插⼊算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插⼊位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。
在这里插入图片描述

/*** 插入排序* 原地排序:是* 稳定排序:是* 空间复杂度:O(1)* 时间复杂度:时间复杂度:最好O(n)——最坏O(n^2)——平均O(n^2)* @param arr*/public static void insertionSort(int[] arr) {int n = arr.length;//从下标为1的位置开始选择合适的位置插入,因为下标为0的只有一个元素,默认为有序for(int i=1;i<n;i++) {int value = arr[i];//记录要插入的数据int j=i-1;for(;j>=0;j--) {if(arr[j]>value) {arr[j+1] = arr[j];//移动数据}else {break;}}arr[j+1] = value;//保存比较小的数,插入}System.out.print("[ ");for(int i=0;i<n;i++) {System.out.print(arr[i]+" ");}System.out.println("]");}

3.选择排序

选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。
在这里插入图片描述

/*** 选择排序* 原地排序:是* 稳定排序:否* 空间复杂度:O(1)* 时间复杂度:时间复杂度:最好O(n^2)——最坏O(n^2)——平均O(n^2)* @param arr*/public static void selectionSort(int arr[]) {int n = arr.length;for(int i=0;i<n;i++) {int value = arr[i];int index = i;for(int j=i+1;j<n;j++) {if(arr[j]<value) {value = arr[j];index = j;}}if(i != index) {int temp = arr[i];arr[i] = arr[index];arr[index] = temp;}}System.out.println("============================");System.out.print("[ ");for(int k=0;k<n;k++) {System.out.print(arr[k]+" ");}System.out.println("]");}

相关文章:

时间复杂度为O(n2)的三种简单排序算法

1.冒泡排序 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较&#xff0c;看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少少一个元素移动到它应该在的位置&#xff0c;重复n次&#xff0c;就完成了n个数据的排序工作。 /*** …...

LeetCode 热题 100 JavaScript --226. 翻转二叉树

给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 3&#xff1a; 输入&#xff1a;root [] 输出&#xff1a;[] 提示&#xff1a; 树中节点数目范围在 [0, 100] 内 -100 < Node.val < 100 var invertTree function(root…...

hive所有窗口函数详情总结

hive窗口函数详情总结 解释语法hive开窗函数排序开窗函数样例数据RANK()DENSE_RANK()ROW_NUMBER() 分析开窗函数样例数据&#xff1a;last_valuefirst_valuelaglead 其他窗口函数cume_distpercent_rank 解释 开窗函数用于为行定义一个窗口&#xff08;指运算将要操作的行的集合…...

Talk | 新加坡国立大学博士生施宇钧:DragDiffusion-基于扩散模型的关键点拖拽图片编辑

本期为TechBeat人工智能社区第518期线上Talk&#xff01; 北京时间8月2日(周三)20:00&#xff0c; 新加坡国立大学博士生—施宇钧的Talk已准时在TechBeat人工智能社区开播&#xff01; 他与大家分享的主题是: “DragDiffusion-基于扩散模型的关键点拖拽图片编辑”&#xff0c;他…...

22 | 贝叶斯分类算法

文章目录 介绍什么是贝叶斯分类算法?贝叶斯分类算法的应用场景贝叶斯定理贝叶斯定理的基本原理贝叶斯定理的公式推导贝叶斯定理的应用举例代码介绍 什么是贝叶斯分类算法? 贝叶斯分类算法是一类基于贝叶斯定理的分类技术。在统计分类任务中,这些算法使用特定的假设来建立特…...

java.sql.SQLSyntaxErrorException: ORA-00909: 参数个数无效

问题&#xff1a; 在Select里采用Contact(%,#name,%)报错参数个数无效 原因&#xff1a; 回想以前用Mysql的时候就是这样用的&#xff0c;没有问题&#xff0c;在这里就出问题了&#xff0c;所以确定问题在oracle数据库上&#xff0c;经过查询得知&#xff0c;oracle和mysql…...

数据结构8-哈希表

数据结构8-哈希表 动态分配内存方式&#xff1a; #include <stdio.h> #include <stdlib.h>#define SIZE 20struct DataItem {int data; int key; };struct DataItem* hashArray[SIZE]; struct DataItem* dummyItem; struct DataItem* item;//获取键值 int has…...

vue3引用Font-Awesome字体图标库

环境&#xff1a;vue3tsviteelement plus 介绍&#xff1a;这里安装引用的是Font-Awesome 6.x 版本&#xff0c;有专业版&#xff08;付费&#xff09;&#xff0c;这里只介绍免费版字体使用方法 一、安装 1.使用npm安装&#xff0c;终端打开项目目录或者命令行cd到目录文件夹…...

Python: Django 服务部署可能遇到的一些问题

502 bad gateway 不要用 python3 manage.py runserver 启动服务&#xff0c; 而要用&#xff1a; daphne -b 0.0.0.0 -p <端口> <工程名>.asgi:application此外&#xff0c;在 setting.py 中&#xff0c;修改&#xff1a; import osSECRET_KEY os.environ.get(D…...

Python爬虫时遇到连接超时解决方案

在进行Python爬虫任务时&#xff0c;经常会遇到连接超时&#xff08;TimeoutError&#xff09;错误。连接超时意味着爬虫无法在规定的时间内建立与目标服务器的连接&#xff0c;导致请求失败。为了帮助您解决这个常见的问题&#xff0c;本文将提供一些解决办法&#xff0c;并提…...

这所国字头双一流,根本招不满,学硕都没人报!

一、学校及专业介绍 中国民航大学&#xff0c;位于天津市&#xff0c;是民航局、天津市、教育部共建高校&#xff0c;是天津市“双一流”建设高校和高水平特色大学建设高校。 1.1 招生情况 2023年中国民航大学电子信息与自动化学院&#xff0c;初试考806信号与系统的一共有两…...

macos 查询端口占用 命令

在 macOS 上查询端口占用的命令是通过使用lsof&#xff08;list open files&#xff09;工具来实现的。 lsof可以显示当前系统中打开的文件&#xff08;包括网络连接和端口&#xff09;的相关信息。 打开终端应用程序&#xff08;Terminal&#xff09;&#xff0c;然后输入以下…...

无代码开发:打破传统开发模式,引领数字化转型新方向

随着数字化转型的加速&#xff0c;企业对于高效、便捷的软件开发需求愈发旺盛。无代码开发作为一种新兴的软件开发模式&#xff0c;以其可视化、模块化的开发方式&#xff0c;为数字化转型提供了新的方向。本文将从无代码开发的优势、应用场景、如何实现等方面进行详细解读&…...

go-zero超强工具goctl的常用命令api,rpc,model及其构建的服务解析

goctl api 详情移步&#xff1a; go-zero的路由机制解析 基于go-zero的api服务刨析并对比与gin的区别 goctl rpc goctl支持多种rpc&#xff0c;较为流行的是google开源的grpc&#xff0c;这里主要介绍goctl rpc protoc的代码生成与使用。 protoc是grpc的命令&#xff0c;作用…...

手机python编程软件怎么用,手机python编程软件下载

大家好&#xff0c;小编来为大家解答以下问题&#xff0c;手机python编程软件保存的代码在哪里&#xff0c;手机python编程软件怎么运行&#xff0c;现在让我们一起来看看吧&#xff01; 原标题&#xff1a;盘点几个在手机上可以用来学习编程的软件 前天在悟空问答的时候&#…...

【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

家居行业解决方案 | 君子签电子签约助力家居企业减负增效

过去&#xff0c;家居行业因供需两端碎片化、服务链条较长等因素&#xff0c;导致线上发展较为缓慢&#xff0c;近年来&#xff0c;互联网的发展推动直播电商、兴趣电商兴起&#xff0c;促使家居行业数字化建设需求越来越为迫切。 合同管理作为家居行业企业经营的一项重要管理…...

Nodejs 第五章(Npm run 原理)

npm run xxx 发生了什么 按照下面的例子npm run dev 举例过程中发生了什么 读取package json 的scripts 对应的脚本命令(dev:vite),vite是个可执行脚本&#xff0c;他的查找规则是&#xff1a; 先从当前项目的node_modules/.bin去查找可执行命令vite如果没找到就去全局的node…...

150. 逆波兰表达式求值

给你一个字符串数组 tokens &#xff0c;表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意&#xff1a; 有效的算符为 、-、* 和 / 。 每个操作数&#xff08;运算对象&#xff09;都可以是一个整数或者另一个表达式。 两个…...

js中的设计模式

设计模式 代码整体的结构会更加清楚&#xff0c;管理起来会更加方便&#xff0c;更好地维护 设计模式是一种思想 发布订阅 模块化开发 导入很多模块 容器即数组存储未来要执行的方法&#xff0c;同addEventListener 数组塌陷问题* 由于删除了元素&#xff0c;导致从删除元素的位…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

倒装芯片凸点成型工艺

UBM&#xff08;Under Bump Metallization&#xff09;与Bump&#xff08;焊球&#xff09;形成工艺流程。我们可以将整张流程图分为三大阶段来理解&#xff1a; &#x1f527; 一、UBM&#xff08;Under Bump Metallization&#xff09;工艺流程&#xff08;黄色区域&#xff…...

Spring AOP代理对象生成原理

代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】&#xff0c;这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...