当前位置: 首页 > 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;对电力系统的需求做出估计以及研究相关因素对电力负荷的影响…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...