Java:插入排序
目录
排序的概念
插入排序
直接插入排序
哈希排序
排序的概念
排序:所谓的排序,就是使一串记录,按照某个或某些关键字的大小,递增或递减的排列起来的操作。
稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳 定的;否则称为不稳定的。

常见的排序算法有下面四种:
- 插入排序:直接插入排序,希尔排序
- 选择排序:选择排序,堆排序
- 交换排序:冒泡排序,快速排序
- 归并排序:归并排序
这里主要介绍Java如何实现插入排序中的直接排序和希尔排序。
插入排序
基本思想:把待排序的记录按照其关键码值的大小逐个插入到一个已经拍好的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。生活中的例子,就像我们在完扑克牌的时候机型排序一样。
直接插入排序
思路:
直接插入排序的过程就像是有一组无序数据,用第二个元素先和第一个元素比较,如果第一个元素比第二个元素大,那么二者就交换位置,否则继续往后推,随着往后推,每一次前一个元素都要不断和之前排序过的元素进行比较。
Sort类
public class Sort {/*** 时间复杂度:O(N^2)* 空间复杂度:O(1)* 稳定性:稳定的排序* @param array*///直接插入排序public static void insertSort(int[] arr){for (int i = 1; i < arr.length; i++) {int tmp = arr[i];int j = i-1;for (; j >= 0; j--) {if(arr[j] > tmp){arr[j+1] = arr[j];}else{arr[j+1] = tmp;break;}}//确保j位置的数,也就是前一个数能换位成功arr[j+1] = tmp;}}
}
Test类 测试类
public class Test {public static void main(String[] args) {int[] arr = {12,6,59,45,73,26,2};System.out.println("排序前:" + Arrays.toString(arr));Sort.insertSort(arr);System.out.println("排序前:" + Arrays.toString(arr));}
}
输出结果为:

关于i=1,且i < arr.length思路,因为数组是从0开始的,所以arr[6]的位置刚好是最后一位。
通过上面的动图我们不难发现,如果数组一开始越有序,直接插入排序的效率越高,这也为下面的哈希排序提供了思路。
稳定性
直接插入排序是稳定的,由上面图片能看到它是具有稳定性的,但如果是代码部分的 arr[j] > tmp 改为:arr[j] >= tmp,以上面的2a和2b为例,它们的顺序就会发生变化。那么这还能说直接插入排序是稳定的吗?
当然能,因为 本身是一个稳定的排序,那么可以实现为不稳定的。
但是,如果一个排序 本身是不稳定的,那就不能实现稳定的排序。
哈希排序
哈希排序可以看作是直接插入排序的优化,先通过 gap来不断简化 其中的有序性,然后再用直接插入排序,越有序,直接插入排序的时间复杂度越小,速度越快。

通过间隔分为不同的组,组内进行排序,然后再缩短gap来进行再次排序。
代码为
public static void shellInsert(int[] array){int gap = array.length;while(gap > 1){gap /= 2;shell(array, gap);}
}private static void shell(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i-gap;for (; j >= 0; j-= gap) {if(array[j] > tmp){array[j+gap] = array[j];}else{array[j+gap] = tmp;break;}}array[j+gap] = tmp;}
}
到这里,插入排序中的直接插入排序和希尔排序就结束了,接下来我会继续给出剩下排序的思路和代码。
相关文章:
Java:插入排序
目录 排序的概念 插入排序 直接插入排序 哈希排序 排序的概念 排序:所谓的排序,就是使一串记录,按照某个或某些关键字的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在多个…...
How FAR ARE WE FROM AGI?(ICLR AGI Workshop 2024)概览
关注B站可以观看更多实战教学视频:hallo128的个人空间 How FAR ARE WE FROM AGI?官网 How FAR ARE WE FROM AGI?(ICLR AGI Workshop 2024) 该研讨会将于2024年5月11日在奥地利维也纳以混合模式举行,作为 ICLR 2024年会议的一部…...
leetcode刷题day33|动态规划Part02(62.不同路径、63. 不同路径 II、 343.整数拆分、96.不同的二叉搜索树)
62.不同路径 机器人从(0 , 0) 位置出发,到(m - 1, n - 1)终点。 动规五部曲 1、确定dp数组(dp table)以及下标的含义 dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路…...
基于Python大数据的B站热门视频的数据分析及可视化系统
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码 精品专栏:Java精选实战项目…...
matlab-批处理图像质量变化并形成折线图 (PSNR)
%修改路径就能用,图片分辨率要一致 %clc;clear all;close all;tic;%清理内存 file_pathE:\test\resources\image\;% 批量图像所在的文件夹下 file_save_pathE:\test\resources\SaveImage\;% 要存储的地址 img_path_listdir(strcat(file_path,*.jpg));% 获取批量bm…...
[Doc][Ros2]ros2中Qos(Quality of Service,服务质量)介绍
在 ROS 2 中,QoS(Quality of Service,服务质量)是用于控制节点之间消息传递的可靠性、历史存储和数据持久性等方面的机制。通过 QoS 设置,用户可以更细粒度地控制消息传递的行为,确保在不同网络环境或应用场景中满足特定的通信需求。 几个常用的包: QoSProfile: 含义…...
SpringBoot日志集成-LogBack
Log4J:最早的Java日志框架之一,由Apache基金会发起,提供灵活而强大的日志记录机制JDK自带的日志框架:java.util.logging.Logg,是JDK1.4之后提供的日志API,已淘汰logback: logback一个开源的日志…...
Google BigTable架构详解
文章目录 什么是BigTable?架构图一、整体架构二、数据存储与索引存储模型 三、数据拆分与存储四、元数据管理五、读写流程 其他内容概览负载平衡其他存储和数据库选项 什么是BigTable? Bigtable是Google开发的一个高性能、可扩展的分布式存储系统,用于管理大规模…...
【python】如何切换ipynb的kernel至指定conda环境
需求介绍 打开(若无新建环境) 环境 conda env list conda activate cvml conda install ipykernel python -m ipykernel install --name cvml 以上完成后,打开jupyter 创建一个python文件 在kernel——>change kernel——>python[conda env:cvml] 参考资料…...
Linux【基础指令汇总】
目录 Linux命令的特点 1、文件管理 ls命令 cp命令 mkdir命令 mv命令 pwd命令 2、文档编辑 cat命令 echo命令 rm命令 tail命令 rmdir命令 3、系统管理 rpm命令 find命令 startx命令 uname命令 vmstat命令 4、磁盘管理 df命令 fdisk命令 lsblk命令 hdpar…...
SpringCloud-EurekaClient
创建Module pom.xml <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-netflix-eureka-client</artifactId></dependency> spring:application:name: provider # 应用程序的名称,…...
配置Scrapy项目
配置Scrapy项目是一个涉及多个步骤的过程,在上一篇博客中已经写了安装Scrapy、创建Scrapy项目的步骤。 接下来应该定义Item类、编写爬虫程序以及配置settings.py文件等。以下是一个详细的配置Scrapy项目的步骤: 一、定义Item类 在项目目录下…...
航顺芯片HK32MCU受邀出席汽车芯片国产化与技术创新闭门研讨会
[中国,北京,2024年9月21日]近日,深圳市航顺芯片技术研发有限公司(以下简称“航顺芯片”)产品总监郑增忠受邀出席由中国设备管理协会新能源汽车产业发展促进中心主办的“汽车芯片国产化与技术创新闭门研讨会”。 会上航…...
【深度学习】(6)--图像数据增强
文章目录 图像数据增强一、作用二、增强方法三、代码体现四、增强体现 总结 图像数据增强 数据增强(Data Augmentation),也称为数据增广,是一种在机器学习和深度学习中常用的技术,它通过对现有数据进行各种变换和处理…...
Vscode 远程切换Python虚拟环境
在VSCode中远程切换Python虚拟环境是一个涉及多个步骤的过程,包括安装必要的扩展、连接到远程服务器、创建或激活虚拟环境,并在VSCode中选择相应的Python解释器。以下是一个详细的步骤指南,包括代码示例,旨在帮助我们完成这一过程…...
Sqoop面试整理
Sqoop(SQL-to-Hadoop)是一个用于在Hadoop和关系型数据库之间传输数据的工具。以下是一些可能在Sqoop面试中会被问到的问题及其答案: 1. 什么是Sqoop?为什么使用它? 回答: Sqoop是一个用来在Hadoop和关系型数据库(如MySQL、Oracle、PostgreSQL等)之间高效传输大数据的工具…...
PyCharm 的安装和配置
环境要求: OS:Windows / macOS / Linux (此处使用 Windows 10 进行演示)Python:包括但不限于 Anaconda,miniconda,Python。在 Windows 下只要能找到 python.exe 即可 Download 进入 PyCharm 官网,选择对…...
【工具类:FastJsonRedisSerializer】
工具类:FastJsonRedisSerializer 依赖yml文件FastJsonRedisSerializer.java 依赖 <!-- 主要用于处理 JSON 数据的序列化和反序列化--><!-- 序列化:将对象转换为一种可以存储或传输的格式(如 JSON、XML、二进制等)…...
Spring Cloud Alibaba-(6)Spring Cloud Gateway【网关】
Spring Cloud Alibaba-(1)搭建项目环境 Spring Cloud Alibaba-(2)Nacos【服务注册与发现、配置管理】 Spring Cloud Alibaba-(3)OpenFeign【服务调用】 Spring Cloud Alibaba-(4)Sen…...
芯科科技2024年Works With开发者大会登陆上海,物联网和人工智能的变革性融合带来无限精彩
谷歌、三星等生态大厂将带来重磅演讲和圆桌讨论,亦可切身体验多样化无线技术实作 中国,北京 – 2024年9月25日 – 安全、智能无线连接技术领域的全球领导厂商Silicon Labs(亦称“芯科科技”,NASDAQ:SLAB)&a…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
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是一个异步的、基于事件驱动的网络应用框架,用于…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
VisualXML全新升级 | 新增数据库编辑功能
VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...
DiscuzX3.5发帖json api
参考文章:PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下,适配我自己的需求 有一个站点存在多个采集站,我想通过主站拿标题,采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...
聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇
根据 QYResearch 发布的市场报告显示,全球市场规模预计在 2031 年达到 9848 万美元,2025 - 2031 年期间年复合增长率(CAGR)为 3.7%。在竞争格局上,市场集中度较高,2024 年全球前十强厂商占据约 74.0% 的市场…...
从实验室到产业:IndexTTS 在六大核心场景的落地实践
一、内容创作:重构数字内容生产范式 在短视频创作领域,IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色,生成的 “各位吴彦祖们大家好” 语音相似度达 97%,单条视频播放量突破百万…...
【记录坑点问题】IDEA运行:maven-resources-production:XX: OOM: Java heap space
问题:IDEA出现maven-resources-production:operation-service: java.lang.OutOfMemoryError: Java heap space 解决方案:将编译的堆内存增加一点 位置:设置setting-》构建菜单build-》编译器Complier...
