【蓝桥杯-筑基篇】排序算法
🍓系列专栏:蓝桥杯
🍉个人主页:个人主页
目录
前言:
一、冒泡排序
二、选择排序
三、插入排序
四、图书推荐
前言:
算法工具推荐:
还在为数据结构发愁吗?这款可视化工具,帮助你更好的了解其数据结构数据结构和算法动态可视化 (Chinese) - VisuAlgo
一、冒泡排序
1.什么是冒泡排序?
冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向 上冒。
思想:
我们要把相邻的元素两两比较,当一个元素大于右侧相邻元素时,交换它们的位置;当一个元素小于右侧相邻元素时,位置不变
动图演示:
2.冒泡排序代码实现
代码1:
import java.util.Arrays;public class bubble {public static void main(String[] args) {int arr[]={5,8,6,3,9,2,1,7};System.out.println("排序前:"+Arrays.toString(arr));BubbleSort(arr);System.out.println("排序后:"+Arrays.toString(arr));}private static void BubbleSort(int[] arr) {int temp=0; //临时存储变量int n=0; //统计排序次数for (int i = 1; i < arr.length; i++) {n++;for (int j = 0; j < arr.length-i; j++) {if (arr[j]>arr[j+1]){temp=arr[j+1];arr[j+1]=arr[j];arr[j]=temp;}}System.out.println("第"+n+"轮:"+Arrays.toString(arr));}}}
3.冒泡排序代码优化
优化:
因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。
代码2(第一次优化):
import java.util.Arrays;public class bubble {public static void main(String[] args) {int arr[]={5,8,6,3,9,2,1,7};System.out.println("排序前:"+Arrays.toString(arr));BubbleSort(arr);System.out.println("排序后:"+Arrays.toString(arr));}private static void BubbleSort(int[] arr) {int temp=0; //临时存储变量int n=0; //统计排序次数for (int i = 1; i < arr.length; i++) {n++;boolean flag=true;for (int j = 0; j < arr.length-i; j++) {if (arr[j]>arr[j+1]){temp=arr[j+1];arr[j+1]=arr[j];arr[j]=temp;flag=false;}}if (flag==true){break;}System.out.println("第"+n+"轮:"+Arrays.toString(arr));}}}
与第1版代码相比,第2版代码做了小小的改动,利用布尔变量flag作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,则说明数列已然有序,然后直接跳出大循环。
这只是冒泡序优化的第一步,我们还可以进一步来提开它的性能。为了说明问题,这次以一个新的数列为例。
为了说明问题,这次以一个新的数列为例
arr={3,4,2,1,5,6,7,8}
import java.util.Arrays;public class bubble {public static void main(String[] args) {int arr[]={3,4,2,1,5,6,7,8};System.out.println("排序前:"+Arrays.toString(arr));BubbleSort(arr);System.out.println("排序后:"+Arrays.toString(arr));}private static void BubbleSort(int[] arr) {int temp=0; //临时存储变量int n=0; //统计排序次数for (int i = 1; i < arr.length; i++) {n++;boolean flag=true;for (int j = 0; j < arr.length-i; j++) {System.out.println("排序:"+Arrays.toString(arr));if (arr[j]>arr[j+1]){temp=arr[j+1];arr[j+1]=arr[j];arr[j]=temp;flag=false;}}if (flag==true){break;}System.out.println("第"+n+"轮:"+Arrays.toString(arr));}}}
第一轮中:
元素4和5比较,发现4小于5,所以位置不变。
元素5和6比较,发现5小于6,所以位置不变。
元素6和7比较,发现6小于7,所以位置不变。
元素7和8比较,发现7小于8,所以位置不变。
第二轮中:
元素3和4比较,发现3小于4,所以位置不变。
元素4和5比较,发现4小于5,所以位置不变。
元素5和6比较,发现5小于6,所位位置不变。
元素6和7比较,发现6小于7,所以位置不变。
元素7和8比较,发现7小于8,所以位置不变。
.................................................................
按照现有的逻辑,有序区的长度和排序的轮数是相等的。例如第1轮排序过后的有序区长度是1,第2轮排序过后的有序区长度是2....
实际上,数列真正的有序区可能会大于这个长度,如上述例子中在第2轮排序时,后面的5个元素实际上都已经属于有序区了。因此后面的多次元素比较是没有意义的。
那么,该如何避免这种情况呢?我们可以在每一轮排序后, 记录下来最后一次元素交换的位置,该位置即为无序数列的边界,再往后就是有序区了。
4.冒泡排序代码再次优化
代码3:
import java.util.Arrays;public class bubble {public static void main(String[] args) {int arr[]={3,4,2,1,5,6,7,8};System.out.println("排序前:"+Arrays.toString(arr));BubbleSort(arr);System.out.println("排序后:"+Arrays.toString(arr));}private static void BubbleSort(int[] arr) {int temp=0; //临时存储变量int n=0; //统计排序次数int lastIndex= 0;//记录最后一次交换的位置int sortBorder= arr.length-1;//无序数列的边界for (int i = 1; i < arr.length; i++) {n++;boolean flag=true;for (int j = 0; j < sortBorder; j++) {System.out.println("排序:"+Arrays.toString(arr));if (arr[j]>arr[j+1]){temp=arr[j+1];arr[j+1]=arr[j];arr[j]=temp;lastIndex=j;flag=false;}}sortBorder=lastIndex;if (flag==true){break;}System.out.println("第"+n+"轮:"+Arrays.toString(arr));}}}
二、选择排序
基本介绍:
选择式排序也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。
思想:
选择排序 (select sorting) 也是一种简单的排序方法。它的基本思想是: 第一次从 arr[0]~arr[n-1]中选取最小值,与arr[0]交换,第二次从 ar[1]~arr[n-1]中选取最小值,与 arr[1]交换,第三次从 ar[2]~arr[n-1]中选取最小值,与 arr[2]交换,.................,第 i 次从arr[i-1]~arr[n-1]中选取最小值,与 arr[i-1]交换,.............,第n-1 次从arr[n-2] ~ arr [n-1]中选取最小值,与 arr[n-2]交换,总共通过 n-1 次,得到一个按排序码从小到大排列的有序序列。
1.选择排序
//普通选择排序public static void sort1(int[] array){int count = 0;//统计运行次数int cnt = 0; //交换次数for(int i=0;i<array.length-1;i++) {int min=array[i];int minIndex=i;count++;for(int j=i+1;j<array.length;j++){if(min>array[j]) {min=array[j];minIndex=j;}}if(minIndex!=i){cnt++;array[minIndex]=array[i];array[i]=min;}}System.out.println(Arrays.toString(array));System.out.println("运行次数:"+count+"次 交换次数:"+cnt);}
2.优化版
import java.util.Arrays;
import java.util.Random;/*** 选择排序优化*/
class SelectionSort2 {public static void main(String[] args) {//产生一个随机数组Random r = new Random();int arr[] = new int[2000];for(int i=0;i<arr.length;i++){arr[i] =r.nextInt(1000);}//因为本优化版本每次循环找出最大以及最小值,所以执行执行:arr.length/2int ArrLength = (arr.length/2);int temp1,temp2;long count = 0;//记录开始时间long startStamp = System.currentTimeMillis();//算法开始for(int j=0;j<ArrLength;j++){int minIndex = j;int maxIndex= j;for(int i=j;i<arr.length-j;i++){if (arr[minIndex] > arr[i]) {minIndex = i;}if (arr[maxIndex] < arr[i]) {maxIndex= i;}count++;}temp1 = arr[minIndex];arr[minIndex] = arr[j];arr[j] = temp1;if(j!=maxIndex) { //maxIndex不能再原本的minIndex位置上temp2 = arr[maxIndex];arr[maxIndex] = arr[arr.length - j - 1];}else{temp2 = arr[minIndex];arr[minIndex] = arr[arr.length - j - 1];}arr[arr.length - j - 1] = temp2;}//计算算法结束时间long endStamp = System.currentTimeMillis();System.out.println("用时总长:"+(endStamp-startStamp));System.out.println("循环次数:"+count);System.out.println(Arrays.toString(arr));}
}
三、插入排序
插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n -1 个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。
Java实现插入排序的代码如下:
public static void insertionSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}
上面的代码使用了两重循环,外层循环枚举未排序部分的元素,内层循环在已排序部分中找到适当的位置并进行插入。
这段代码的时间复杂度为O(n^2),空间复杂度为O(1)。
四、图书推荐
《经典算法的起源》是一本计算机算法方面的科普性书籍,作者以通俗易懂、引人入胜的叙述方式介绍各种算法思想,避免使用一些过于严谨的专业术语。比如,用“大海捞针”来形容一种搜索算法就非常形象,顾名思义,广大读者更容易理解该搜索策略。本书适合对计算机知识有兴趣的初中生、高中生或其他相关人员阅读。计算机专业一、二年级的大学生阅读此书,也会对相关知识的起源有深刻的印象。
本书的目的是向非专业人士介绍算法,使读者理解算法如何运作,而不是阐述算法在生活中的作用。有些书籍在某些方面做了杰出工作,如介绍如何改善大数据的处理,讨论将人工智能和计算设备融入日常生活对人类生存条件的改变。本书对“发生什么”不感兴趣,对“如何发生”感兴趣。为此,本书给出一些真实的算法,不仅描述它们做什么,更重要的是关注它们如何运作。本书将提供详细的解释说明,而非粗略的介绍。
本书由机械工业出版社提供
相关文章:

【蓝桥杯-筑基篇】排序算法
🍓系列专栏:蓝桥杯 🍉个人主页:个人主页 目录 前言: 一、冒泡排序 二、选择排序 三、插入排序 四、图书推荐 前言: 算法工具推荐: 还在为数据结构发愁吗?这款可视化工具,帮助你更好的了解…...

编辑器进化 VSCode + Vim
本文作者为 360 奇舞团前端工程师VSCode 是一款非常流行的代码编辑器。它支持多种编程语言,拥有丰富的插件和调试功能,不论是处理前端工程还是后端工程,VSCode 都能提供给开发者优秀的用户体验。鉴于 VSCode 超高的流行度,我会默认…...

LearnOpenGL-高级OpenGL-6.天空盒
本人刚学OpenGL不久且自学,文中定有代码、术语等错误,欢迎指正 我写的项目地址:https://github.com/liujianjie/LearnOpenGLProject 文章目录天空盒介绍如何采样OpenGL纹理目标例子0:天空盒效果环境映射反射例子1:Cube…...

Printk打印内核日志
一、背景 Linux 内核中提供了内核日志打印的工具printk。它的使用方式C语言中的printf是类似的。接下来我们介绍一下printk的使用方式。本文以打印Binder中的日志为例,进行演示。 printk的方法声明和日志级别binder驱动中增加 打印代码android系统中查看日志信息 …...

界面控件DevExpress WPF 202计划发布的新功能合集
DevExpress WPF拥有120个控件和库,将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpress WPF能创建有着强大互动功能的XAML基础应用程序,这些应用程序专注于当代客户的需求和构建未来新一代支持触摸的解决方案。本文将介绍今年DevExpr…...

Spring Cloud Alibaba 微服务2,注册中心演变 + Nacos注册中心与配置中心
目录专栏导读一、什么是Nacos?二、注册中心演变及其设计思想1、RestTemplate调用远程服务2、通过Nginx维护服务列表(upStream)3、通过Nacos实现注册中心4、心跳版Nacos三、Nacos Discovery四、Nacos核心功能1、服务注册2、服务心跳3、服务同步…...

Navicat 图形化界面工具
Navicat 介绍 Navicat是一套可创建多个连接的数据库管理工具,用以方便管理 MySQL、Oracle、SQL Server等不同类型的数据库 目录 Navicat 介绍 Navicat 下载 Navicat 安装 Navicat 使用 Navicat连接MySQL数据库 Navicat创建数据库和表 Navicat 下载 1、点击这…...

2023年网络安全比赛--attack(新)数据包分析中职组(超详细)
一、竞赛时间 180分钟 共计3小时 任务环境说明: 1 分析attack.pcapng数据包文件,通过分析数据包attack.pcapng找出恶意用户第一次访问HTTP服务的数据包是第几号,将该号数作为Flag值提交; 2.继续查看数据包文件attack.pcapng,分析出恶意用户扫描了哪些端口,将全部的端口号…...
C语言之extern(七十)
extern同一个文件:修饰变量声明#include <stdio.h>int add(){extern int x,y;return x y; }int main(){printf("%d\n", add()); }int x 10; int y 20;extern文件之间:修饰函数声明<1>.add.cint sum(){extern int x ;extern in…...

树的前中后序的Morris遍历
目录 一.Morris遍历 1.什么是Morris遍历 2.基本思想 3.Morris遍历的优点和缺点 4.知识回顾----二叉树的线索化 二.中序Morris遍历 1.中序Morris遍历的分析 2.中序Morris遍历的思路 3.具体的代码实现 三.前序Morris遍历 1.前序Morris遍历的思路 2.具体的代码实现 四…...

到底什么是线程?线程与进程有哪些区别?
上一篇文章我们讲述了什么是进程,进程的基本调度 http://t.csdn.cn/ybiwThttp://t.csdn.cn/ybiwT 那么本篇文章我们将了解一下什么是线程?线程与进程有哪些区别?线程应该怎么去编程? 目录 http://t.csdn.cn/ybiwThttp://t.csdn…...

你真的知道如何系统高效地学习数据结构与算法吗?
文章目录前言:什么是数据结构?什么是算法?学习这个算法需要什么基础?学习的重点在什么地方?一些可以让你事半功倍的学习技巧1.边学边练,适度刷题2.多问、多思考、多互动3.打怪升级学习法4.知识需要沉淀&…...

Linux操作系统基础的常用命令
1,Linux简介Linux是一种自由和开放源码的操作系统,存在着许多不同的Linux版本,但它们都使用了Linux内核。Linux可安装在各种计算机硬件设备中,比如手机、平板电脑、路由器、台式计算机。1.1Linux介绍Linux出现于1991年,…...

Jasypt加密库基本使用方法
目录 1 Jasypt简介... 2 基础知识回顾... 3 Jasypt基本加密器... 4 JasyptPBE加密器... 5 Jasypt池化加密器... 6 Jasypt客户端工具... 7 JasyptSpringboot基本用法... 8 JasyptSpringboot自定义加密器... 9 JasyptSprin…...
C++并发编程之五 高级线程管理
文章目录5.1.1 线程池5.1.1 线程池 在前面我们引入了线程的通信和同步手段,那么为什么还要引入线程池呢? 线程池是一种管理多个线程的技术,它可以减少线程的创建和销毁的开销,提高并发性能。线程池中有一定数量的空闲线程&#x…...

单片机——IIC协议与24C02
1、基础知识 1.1、IIC串行总线的组成及工作原理 I2C总线只有两根双向信号线。一根是数据线SDA,另一根是时钟线SCL。 1.2、I2C总线的数据传输 I2C总线进行数据传送时,时钟信号为高电平期间,数据线上的数据必须保持稳定,只有在时钟…...

案例05-将不必要的逻辑放到前端(发送调查问卷)
目录一:背景介绍背景二:思路&方案重大问题:解决办法优点:三:总结一:背景介绍 本篇博客书写的意义是警示大家不必把不必要的逻辑放到前端。 明确前后端分离的意义。 背景 下面的主要逻辑是࿱…...

【每日一题】——矩阵相等判定
🌏博客主页:PH_modest的博客主页 🚩当前专栏:每日一题 💌其他专栏: 🔴 每日反刍 🟢 读书笔记 🟡 C语言跬步积累 🌈座右铭:广积粮,缓称…...

Linux防火墙的关闭
查看防火墙的状态打开终端输入如下命令systemctl status firewalld如图所示:running表示防火墙目前处于打开状态输入命令进行关闭防火墙:systemctl stop firewalld如图所示正常的用户是没有权限的,需要输入管理员的密码才能够进行关闭防火墙。…...

Request和Response的概述
⭐作者介绍:大二本科网络工程专业在读,持续学习Java,输出优质文章⭐作者主页:︶ㄣ释然⭐如果觉得文章写的不错,欢迎点个关注😉有写的不好的地方也欢迎指正,一同进步😁Request和Respo…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器
一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下,音视频内容犹如璀璨繁星,点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频,到在线课堂中知识渊博的专家授课,再到影视平台上扣人心弦的高清大片,音…...