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

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...