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

冒泡排序,选择排序,插入排序,希尔排序,基数排序,堆排序代码分析(归并排序和快速排序后续更新)

所有的算法都是这样,算法思想最重要,其次是实现过程,最后才是实现的代码

上战伐谋,我们只要明确了其算法思想和实现过程,所有算法都是纸老虎,所有算法题都是纸老虎

笔者才疏学浅,也算是刚刚接触算法,暂时总结不出思想,但是笔者相信只要坚持下去,总有一天一定可以领悟到

冒泡排序和选择排序

手撕冒泡排序和选择排序

之前写的这篇博客讲的很清楚了,这里只展示代码

public static void bubbleSort(int[] arr){for(int j = 0; j<arr.length; j++){for(int i = 0;i<arr.length - 1; i++) {// 唯一需要注意的点,循环n-1次,让i+1遍历到数组末尾即可if(arr[i+1] > arr[i]) {int temp = arr[i];arr[i] = arr[i+1];arr[i+1] = arr[i];}}}
}
public static void selectSort(int[] arr){for (int i = 0; i < arr.length; i++) {// 假设第一个是最小的,所以当然minIndex = iint min = arr[i];int minIndex = i;// 内层抓数字和未排好的数字序列的第一个数字进行比较,下标当然从i+1开始for (int j = i + 1; j < arr.length; j++) {if (arr[j] < min) {// 替换新的minmin = arr[j];// 记录更小数字的下标minIndex = j;}}// 普通交换/*int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;*/// 进阶交换,我们发现arr[minIndex] = min,所以不需要再定义一个中间变量temp// 同时,arr[i]只有一份,所以不能先辅助arr[i]arr[minIndex] = arr[i];arr[i] = min;}}
}

插入排序

插入排序,不断插入后续数字并且保证有序性,所以被称为插入排序

要点:

  1. 默认第一个数字有序,逐渐递增有序序列
  2. 内层循环实际上是冒泡排序的倒排
 public static void insertSort(int[] arr) {// 因为默认第一个数字有序,所以i从1开始,i指针循环n-1次for (int i = 1; i < arr.length; i++) {// j从i开始,逐渐向后移动// 因为比较的是arr[j]和arr[j-1],所以j要>=1 for (int j = i; j >= 1; j--) {// 如果arr[j]前一个数字比arr[j]大,就交换位置if (arr[j] < arr[j - 1]) {int temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;}}}}

希尔排序

插入排序存在插入的小数字越小,位置越靠后,后移的次数越多的问题,实际上会形成很多多余的交换位置

希尔排序就是为了解决这个问题而诞生的,在**“最后的交换”**之前,先让大数字尽可能往后移动,小数字尽可能往前移动

这里的**“最后的交换”**,实际上就是插入排序

是的,你没听错,希尔排序的最后一轮交换,实际上就是插入排序

希尔排序运用了分组的思想

先分成n/2组,然后是n/4……最后step = 1时,就是插入排序

public static void shellSort(int[] arr) {int step = arr.length / 2;// 只要步长不是0,就一直循环while (step != 0) {// i指针先从步长位置开始循环for (int i = step; i < arr.length; i++) {// 比较arr[j]和arr[j+step]的大小,保证组内有序for (int j = i - step; j >=0; j--) {if (arr[j] > arr[j + step]) {int temp = arr[j];arr[j] = arr[j + step];arr[j + step] = temp;}}}// 每次循环步长减半step /= 2;}}

基数排序

又叫桶排序

排序方法很简单,就是先比较数字的个位,然后比较十位,比较百位……,最后就能排号序

但是实现起来比较复杂,有很多需要注意的细节

个人认为,八大排序里面,除了快排和归并,其次最难写的就是基数排序

public static void bucketSort(int[] arr) {int max = arr[0];for (int ele : arr) {max = Math.max(ele, max);}int maxLength = ("" + max).length();// 1. 先定义好0~9十个桶,桶高是数组的长度int[][] baseBucket = new int[10][arr.length];// 2. 桶计数器int[] bucketCount = new int[10];for (int m = 1; m <= maxLength; m++) {int m1 = 1;// 循环数组获取个位数据,放到桶中for (int i = 0; i < arr.length; i++) {// 求余数int left = (arr[i] / m1) % 10;// 查询目前桶中本列下一个插入位置int height = bucketCount[left];// 插入baseBucket[left][height] = arr[i];// 桶计数器+1bucketCount[left] = ++bucketCount[left];}m1 = m1 * 10;// 下策:遍历二维数组取出数字// 上策:遍历桶计数器,不等于0就放进arrint i = 0;for (int j = 0; j < 10; j++) {if (bucketCount[j] != 0) {for (int k = 0; k < bucketCount[j]; k++) {arr[i] = baseBucket[j][k];i++;}// 下策:新创建一个桶计数器// 上策:清空桶计数器// 用完就清空bucketCount[j] = 0;}}}}

堆排序

堆排序(排序思想+排序流程+代码)

这篇博客写的很清楚了,这里只展示代码

public static void heapSort(int[] arr) {for (int p = arr.length; p >= 0; p--) {sort(arr, p, arr.length);}for (int i = arr.length - 1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;sort(arr, 0, i);}}public static void sort(int[] arr, int parent, int length) {int maxChild = 2 * parent + 1;while (maxChild < length) {int rightChild = maxChild + 1;if (rightChild < length && arr[rightChild] > arr[maxChild]) {maxChild = rightChild;}if (arr[parent] < arr[maxChild]) {int temp = arr[parent];arr[parent] = arr[maxChild];arr[maxChild] = temp;parent = maxChild;maxChild = 2 * maxChild + 1;} else {break;}}}

相关文章:

冒泡排序,选择排序,插入排序,希尔排序,基数排序,堆排序代码分析(归并排序和快速排序后续更新)

所有的算法都是这样&#xff0c;算法思想最重要&#xff0c;其次是实现过程&#xff0c;最后才是实现的代码 上战伐谋&#xff0c;我们只要明确了其算法思想和实现过程&#xff0c;所有算法都是纸老虎&#xff0c;所有算法题都是纸老虎 笔者才疏学浅&#xff0c;也算是刚刚接…...

从入门到精通:NTP卫星时钟服务器技术指南

从入门到精通&#xff1a;NTP卫星时钟服务器技术指南 从入门到精通&#xff1a;NTP卫星时钟服务器技术指南 一、 产品功能 卫星时钟服务器是一款采用GPS或北斗卫星提供高精度网络时间服务的产品。卫星天线安装简便&#xff08;根据天线所放位置提示实时卫星颗数&#xff09;&a…...

OpenResty基于来源IP和QPS来限流

Nginx 经典限流法 ngx_http_limit_req_module 和 ngx_http_limit_conn_module&#xff0c;可以在代理层面对服务进行限流和熔断。 http {# 请求限流定义1:# - $binary_remote_addr&#xff1a;限制对象(客户端)# - zone&#xff1a;定义限制(策略)名称# - 10m&#xff1a;用十…...

面对AI技术创业的挑战以及提供给潜在创业者的一些建议

面对AI创业的挑战 AI技术创业虽然机遇众多&#xff0c;但也面临不少挑战&#xff0c;理解这些挑战并寻找应对策略是创业成功的关键。 技术挑战 AI技术的快速发展意味着创业者需要持续学习和更新知识库&#xff0c;以保持技术竞争力。同时&#xff0c;AI项目往往需要处理大量数…...

`require`与`import`的区别

require与import的区别主要体现在以下几个方面&#xff1a; 1.加载时间不同。require是在运行时加载模块&#xff0c;这意味着模块的加载和执行可以在代码的任何地方进行&#xff0c;也可以在运行时根据条件动态地加载不同的模块&#xff1b;import是在编译时加载模块&#xf…...

中介者模式:优雅解耦的利器

在软件设计中&#xff0c;随着系统功能的不断扩展&#xff0c;对象之间的依赖关系往往会变得错综复杂&#xff0c;导致系统难以维护和扩展。为了降低对象之间的耦合度&#xff0c;提高系统的可维护性和可扩展性&#xff0c;设计模式应运而生。中介者模式&#xff08;Mediator P…...

Ubuntu20.04安装MatlabR2018a

一、安装包 安装包下载链接 提取码&#xff1a;kve2 网上相关教程很多&#xff0c;此处仅作为安装软件记录&#xff0c;方便后续软件重装&#xff0c;大家按需取用。 二、安装 1. 相关文件一览 下载并解压文件后&#xff0c;如下图所示&#xff1a; 2. 挂载镜像并安装 2…...

基于SpringBoot的图书馆管理系统设计与实现

介绍 基于&#xff1a;java8 SpringBoot thymeleaf MySQL8.0.17 mybatis-plus maven Xadmin 实现图书馆管理系统 系统要实现如下的基本管理功能&#xff1a; &#xff08;1&#xff09;用户分为两类&#xff1a;管理员&#xff0c;一般用户。 &#xff08;2&#xff09…...

网易云首页单页面html+css

网页设计与网站建设作业htmlcss 预览 源码查看https://hpc.baicaitang.cn/2083.html...

acwing算法提高之图论--最小生成树的典型应用

目录 1 介绍2 训练 1 介绍 本专题用来记录使用prim算法或kruskal算法求解的题目。 2 训练 题目1&#xff1a;1140最短网络 C代码如下&#xff0c; #include <iostream> #include <cstring>using namespace std;const int N 110, INF 0x3f3f3f3f; int g[N][N…...

springcloud基本使用二(远程调用)

创建两个springboot maven子项目 子项目名称分别为order-server和user-server 配置user-server子项目: 所需依赖: <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId> </dependenc…...

代码随想录刷题day42| 01背包理论基础分割等和子集

文章目录 day41学习内容一、 01背包之二维数组解法1.1、什么是01背包1.2、动态规划五部曲1.2.1、 确定dp数组&#xff08;dp table&#xff09;以及下标的含义1.2.2、确定递推公式1.2.3、 dp数组如何初始化1.2.4、确定遍历顺序1.2.5、计算并返回最终结果 二、 01背包之一维数组…...

Python文件操作命令

文件操作 我知道你最近很累&#xff0c;是那种看不见的、身体上和精神上的疲惫感&#xff0c;但是请你一定要坚持下去。就算无人问津也好&#xff0c;技不如人也好&#xff0c;千万别让烦躁和焦虑毁了你的热情和定力。别贪心&#xff0c;我们不可能什么都有&#xff0c;也别灰心…...

CSS面试题---基础

1、css选择器及优先级 选择器优先级&#xff1a;内联样式>id选择器>类选择器、属性选择器、伪类选择器>标签选择器、微元素选择器 注意&#xff1a; !important优先级最高&#xff1b; 如果优先级相同&#xff0c;则最后出现的样式生效&#xff1b; 继承得到的样式优先…...

OpenHarmony实战开发-分布式数据管理

​介绍 本示例展示了在eTS中分布式数据管理的使用&#xff0c;包括KVManager对象实例的创建和KVStore数据流转的使用。 通过设备管理接口ohos.distributedDeviceManager &#xff0c;实现设备之间的kvStore对象的数据传输交互&#xff0c;该对象拥有以下能力详见 ;1、注册和解…...

微服务(基础篇-007-RabbitMQ部署指南)

目录 05-RabbitMQ快速入门--介绍和安装_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1LQ4y127n4?p65&vd_source60a35a11f813c6dff0b76089e5e138cc 1.单机部署 1.1.下载镜像 1.2.安装MQ 2.集群部署 2.1.集群分类 2.2.设置网络 视频地址&#xff1a; 05-Rab…...

C语言一维数组及二维数组详解

引言&#xff1a; 小伙伴们&#xff0c;我发现我正文更新的有些慢&#xff0c;但相信我&#xff0c;每一篇文章真的都很用心在写的&#xff0c;哈哈&#xff0c;在本篇博客当中我们将详细讲解一下C语言中的数组知识&#xff0c;方便大家后续的使用&#xff0c;有不会的也可以当…...

11.图像边缘检测的原理与实现

数字图像处理(19): 边缘检测算子(Roberts算子、Prewitt算子、Sobel算子 和 Laplacian算子) 数字图像处理(20): 边缘检测算子(Canny算子) 1.边缘检测介绍 1.1 边缘检测的基本原理 边缘是图像的基本特征&#xff0c;所谓的边缘就是指的图像的局部不连续性。灰度或者结构等信息的…...

RVM安装ruby笔记

环境 硬件&#xff1a;Macbook Pro 系统&#xff1a;macOS 14.1 安装公钥 通过gpg安装公钥失败&#xff0c;报错如下&#xff1a; 换了几个公钥地址&#xff08;hkp://subkeys.pgp.net&#xff0c;hkp://keys.gnupg.net&#xff0c;hkp://pgp.mit.edu&#xff09;&#xff0c;…...

电力系统负荷预测方法

电力系统负荷是什么&#xff1f; 所谓的电力负荷预测是指以电力负荷变化以及外界因素变化为基础&#xff0c;以特定的数学方法或者建立数学模型的方式为手段&#xff0c;通过对电力负荷历史数据进行分析&#xff0c;对电力系统的需求做出估计以及研究相关因素对电力负荷的影响…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

aurora与pcie的数据高速传输

设备&#xff1a;zynq7100&#xff1b; 开发环境&#xff1a;window&#xff1b; vivado版本&#xff1a;2021.1&#xff1b; 引言 之前在前面两章已经介绍了aurora读写DDR,xdma读写ddr实验。这次我们做一个大工程&#xff0c;pc通过pcie传输给fpga&#xff0c;fpga再通过aur…...

MLP实战二:MLP 实现图像数字多分类

任务 实战&#xff08;二&#xff09;&#xff1a;MLP 实现图像多分类 基于 mnist 数据集&#xff0c;建立 mlp 模型&#xff0c;实现 0-9 数字的十分类 task: 1、实现 mnist 数据载入&#xff0c;可视化图形数字&#xff1b; 2、完成数据预处理&#xff1a;图像数据维度转换与…...

使用VMware克隆功能快速搭建集群

自己搭建的虚拟机&#xff0c;后续不管是学习java还是大数据&#xff0c;都需要集群&#xff0c;java需要分布式的微服务&#xff0c;大数据Hadoop的计算集群&#xff0c;如果从头开始搭建虚拟机会比较费时费力&#xff0c;这里分享一下如何使用克隆功能快速搭建一个集群 先把…...

npm install 相关命令

npm install 相关命令 基本安装命令 # 安装 package.json 中列出的所有依赖 npm install npm i # 简写形式# 安装特定包 npm install <package-name># 安装特定版本 npm install <package-name><version>依赖类型选项 # 安装为生产依赖&#xff08;默认&…...

SpringSecurity+vue通用权限系统

SpringSecurityvue通用权限系统 采用主流的技术栈实现&#xff0c;Mysql数据库&#xff0c;SpringBoot2Mybatis Plus后端&#xff0c;redis缓存&#xff0c;安全框架 SpringSecurity &#xff0c;Vue3.2Element Plus实现后台管理。基于JWT技术实现前后端分离。项目开发同时采 …...