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

算法通关村-番外篇排序算法

大家好我是苏麟 , 今天带来番外篇 . 

冒泡排序 BubbleSort

最基本的排序算法,最常用的排序算法 .

我们以关键字序列{26,53,48,11,13,48,32,15}看一下排序过程:

动画演示 :

f167e5271a634801ad0a52224a97f083.gif

代码如下 : (基础版)

class Solution {public int[] sortArray(int[] nums) {for(int i = 0;i < nums.length - 1;i++){for(int j = 0;j < nums.length - i - 1;j++){if(nums[j] > nums[j + 1]){int temp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = temp;}}}return nums;}
}

 优化 :

class Solution {public int[] sortArray(int[] nums) {int flag = 1;for(int i = 0;flag && i < nums.length - 1;i++){flag = 0;for(int j = 0;j < nums.length - i - 1;j++){if(nums[j] > nums[j + 1]){int temp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = temp;flag = 1;}}}return nums;}
}

空间复杂度 仅仅使用一个辅助单元 ,因此空间复杂度为O(1)。

时间复杂度 假设待排序的元素个数为n,则总共需要进行n-1趟排序,对 j 个元素的子序列进行一趟排序需要进行j-1次关键字比较,因此总的比较次数为n(n-1)/2,因此时间复杂度为O(n^2)。

稳定性 冒泡排序的特点是稳定性好,因为排序过程中始终只交换相邻元素,比较对象大小相等时不交换,相对位置不变,故稳定。

选择排序 SelectSort

选择排序是默认前面都是已经排序好的,然后从后面 选择最小的放在前面排序好的的后面,首先第一轮循环的时候默认的排序好的为空,然后从后面选择最小的放到数组的第一个位置,第二轮循环的时候默认第个元素是已经 排序好的,然后从剩下的找出最小的放到数组的第二个位置,第三轮循环的时候默认前 两个都是已经排序好的,然后再从剩下的选择一个最小的放到数组的第三个位置,以此 类推。还是上面的序列,我们看一下选择排序是怎么做的:

动画演示 :

e8c243d5266747969938908d61b104e5.gif

代码 : 

    public static void SelectSort(int[] nums){int min;for (int i = 0;i < nums.length;i++){min = i;for (int j = i + 1;j < nums.length;j++){if (nums[i] > nums[j]){min = j;}}if (i != min){int temp = nums[i];nums[i] = nums[min];nums[min] = temp;}}}

空间复杂度:仅仅使用一个辅助单元 ,因此空间复杂度为O(1)

平均时间复杂度: 在待排序序列已经有序的情况下,简单选择排序不用移动元素。最坏情况下,也就是序列正好是逆序的,则要进行n(n-1)/2次比较,因此最坏时间复杂度为O(n^2).

稳定性:选择排序是不稳定算法

这期就到这里 , 下期见!

相关文章:

算法通关村-番外篇排序算法

大家好我是苏麟 , 今天带来番外篇 . 冒泡排序 BubbleSort 最基本的排序算法&#xff0c;最常用的排序算法 . 我们以关键字序列{26,53,48,11,13,48,32,15}看一下排序过程: 动画演示 : 代码如下 : (基础版) class Solution {public int[] sortArray(int[] nums) {for(int i …...

三种方式简单搭建http本地文件服务

有时候想写一个简单的html文件&#xff0c;然后加上一些image、js、css文件用于测试。希望有一个简单的http服务&#xff0c;总结了如下三种方式&#xff0c;欢迎讨论更多高效的方式。 &#xff08;一&#xff09;使用Web Server for Chrome浏览器扩展 之前写过一篇博文&#x…...

设计模式--适配器模式

实验8&#xff1a;适配器模式 本次实验属于模仿型实验&#xff0c;通过本次实验学生将掌握以下内容&#xff1a; 1、理解适配器模式的动机&#xff0c;掌握该模式的结构&#xff1b; 2、能够利用适配器模式解决实际问题。 [实验任务]&#xff1a;双向适配器 实现一个双向…...

Node.js教程-express框架

概述 Express是基于Node.js平台(建立在Node.js内置的http模块上)&#xff0c;快速、开放、极简的Web开发框架。 中文官网 http://www.expressjs.com.cn/。 Github地址&#xff1a;https://github.com/orgs/expressjs。 Express核心特性&#xff1a; 可设置中间件来响应 HTTP…...

location.origin兼容

if (!window.location.origin) {window.location.origin window.location.protocol "//" window.location.hostname (window.location.port ? : window.location.port: );}...

spring boot集成mybatis和springsecurity实现权限控制功能

上一篇已经实现了登录认证功能&#xff0c;这一篇继续实现权限控制功能&#xff0c;文中代码只贴出来和上一篇不一样的修改的地方&#xff0c;完整代码可结合上一篇一起整理spring boot集成mybatis和springsecurity实现登录认证功能-CSDN博客 数据库建表 权限控制的意思就是根…...

按键修饰符

在键盘监听事件时&#xff0c;我们经常需要判断详细的按键&#xff0c;此时&#xff0c;可以为键盘相关的事件添加按键修饰符&#xff0c;例如&#xff1a; 键盘修饰符案例&#xff1a;...

新版IDEA中Git的使用(一)

说明&#xff1a;本文介绍如何在新版IDEA中使用Git 创建项目 首先&#xff0c;在GitLab里面创建一个项目&#xff08;git_demo&#xff09;&#xff0c;克隆到桌面上。 然后在IDEA中创建一个项目&#xff0c;项目路径放在这个Git文件夹里面。 Git界面 当前分支&Commit …...

【性能测试】真实企业,性能测试流程总结分析(一)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 性能测试什么时候…...

20231224解决outcommit_id.xml1 parser error Document is empty的问题

20231224解决outcommit_id.xml1 parser error Document is empty的问题 2023/12/24 18:13 在开发RK3399的Android10的时候&#xff0c;出现&#xff1a;rootrootrootroot-X99-Turbo:~/3TB/Rockchip_Android10.0_SDK_Release$ make installclean PLATFORM_VERSION_CODENAMEREL…...

电子电器架构刷写方案——General Flash Bootloader

电子电器架构刷写方案——General Flash Bootloader 我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 注&#xff1a;文章1万字左右&#xff0c;深度思考者入&#xff01;&#xff01;&#xff01; 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免…...

【Linux】僵尸与孤儿 进程等待

目录 一&#xff0c;僵尸进程 1&#xff0c;僵尸进程 2&#xff0c;僵尸进程的危害 二&#xff0c;孤儿进程 1&#xff0c;孤儿进程 三&#xff0c;进程等待 1&#xff0c;进程等待的必要性 2&#xff0c;wait 方法 3&#xff0c;waitpid 方法 4&#xff0c;回收小结…...

Java小案例-Sentinel的实现原理

前言 Sentinel是阿里开源的一款面向分布式、多语言异构化服务架构的流量治理组件。 主要以流量为切入点&#xff0c;从流量路由、流量控制、流量整形、熔断降级、系统自适应过载保护、热点流量防护等多个维度来帮助开发者保障微服务的稳定性。 核心概念 要想理解一个新的技…...

【Leetcode Sheet】Weekly Practice 21

Leetcode Test 1901 寻找峰值Ⅱ(12.19) 一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。 给你一个 从 0 开始编号 的 m x n 矩阵 mat &#xff0c;其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置 [i,j] 。 …...

C语言使用qsort和bsearch实现二分查找

引言 在计算机科学领域&#xff0c;查找是一项基本操作&#xff0c;而二分查找是一种高效的查找算法。本博客将详细解释一个简单的C语言程序&#xff0c;演示如何使用标准库函数qsort和bsearch来对一个整数数组进行排序和二分查找。 代码解析 包含头文件 #include <stdi…...

MySQL的替换函数及补全函数的使用

前提&#xff1a; mysql的版本是8.0以下的。不支持树形结构递归查询的。但是&#xff0c;又想实现树形结构的一种思路 提示&#xff1a;如果使用的是MySQL8.0及其以上的&#xff0c;想要实现树形结构&#xff0c;请参考&#xff1a;MySQL数据库中&#xff0c;如何实现递归查询…...

2022第十二届PostgreSQL中国技术大会-核心PPT资料下载

一、峰会简介 本次大会以“突破•进化•共赢 —— 安全可靠&#xff0c;共建与机遇”为主题&#xff0c;助力中国数据库基础软件可掌控、可研究、可发展、可生产&#xff0c;并推动数据库生态的繁荣与发展。大会为数据库从业者、数据库相关企业、数据库行业及整个IT产业带来崭…...

2024 年 10大 AI 趋势

2025 年&#xff0c;全球人工智能市场预计将达到惊人的 1906.1 亿美元&#xff0c;年复合增长率高达 36.62%。 人工智能软件正在迅速改变我们的世界&#xff0c;而且这种趋势在未来几年只会加速。 我们分析了未来有望彻底改变 2024 年的 10 个AI趋势。从生成式人工智能的兴起到…...

Uboot

什么是Bootloader? Linux系统要启动就必须需要一个 bootloader程序&#xff0c;也就说芯片上电以后先运行一段bootloader程序。 这段 **bootloader程序会先初始化时钟&#xff0c;看门狗&#xff0c;中断&#xff0c;SDRAM&#xff0c;等外设&#xff0c;然后将 Linux内核从f…...

ECMAScript 的未来:预测 JavaScript 创新的下一个浪潮

以下是简单概括关于JavaScript知识点以及一些目前比较流行的比如&#xff1a;es6 想要系统学习&#xff1a; 大家有关于JavaScript知识点不知道可以去 &#x1f389;博客主页&#xff1a;阿猫的故乡 &#x1f389;系列专栏&#xff1a;JavaScript专题栏 &#x1f389;ajax专栏&…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...