(笔记)插入排序

news/2024/2/28 12:20:22

插入排序

插入排序是一种简单且常见的排序算法,它通过重复将一个元素插入到已经排好序的一组元素中,来达到排序的目的。在插入排序算法中,将待排序序列分为已排序和未排序两个部分。初始时,已排序部分只包含一个记录,即待排序序列的第一个记录。然后,逐个将未排序部分的记录插入到已排序部分的适当位置,直到所有记录都插入到已排序部分为止。由于插入排序算法的思路简单,实现也容易,因此它在实际应用中被广泛使用。

代码实现

以下是插入排序的Java代码实现:

public static void insertionSort(int[] arr) {if (arr == null || arr.length <= 1) {return;}int n = arr.length;for (int i = 1; i < n; i++) {int value = arr[i];int j = i - 1;for (; j >= 0; j--) {if (arr[j] > value) {arr[j + 1] = arr[j];} else {break;}}arr[j + 1] = value;}
}

时间复杂度

插入排序的时间复杂度为$O(n^2),其中n为待排序序列的长度。虽然插入排序的时间复杂度比一些高级排序算法要高,但是在实际应用中,插入排序仍然是一种非常实用的算法,因为它对于小规模的数据排序效率非常高。同时,当待排序序列已经有序或基本有序时,插入排序的时间复杂度可以降低到$O(n),这也是插入排序具有优势的地方之一。

使用场景

插入排序适用于待排序序列较短的情况,特别是当待排序序列已经基本有序时,插入排序的效率非常高。在排序小规模数据时,插入排序是一个不错的选择。同时,由于插入排序的实现较为简单,因此适合用作其他排序算法的子过程。除此之外,在一些高级排序算法中,插入排序也被用来对小规模数据进行排序。例如,快速排序算法在排序过程中,当待排序序列的规模小于某个值时,会采用插入排序算法进行排序。


http://www.ppmy.cn/news/971326.html

相关文章

@PostConstruct和@PreDestroy与servlet生命周期的关系

执行顺序结果 /*** 服务器加载Servlet* ---> 创建servlet实例&#xff0c;实现servlet构造函数* ---> 执行注解PostConstruct* ---> servlet.Init()* ---> servlet/service() 方法* ---> 执行注解PreDestroy* ---> servlet.destroy()* ---> 服务器卸载Se…

产品再次跳票 法拉第未来的融资价值却渐渐浮现?

从“生态化反”到“极智科技顶奢”&#xff0c;贾跃亭讲故事的出众能力&#xff0c;总是能为旗下企业和产品赚足市场眼球。 但仅有宏大的前景描绘&#xff0c;似乎难以触动理性的资本市场&#xff0c;其创立的新能源车企法拉第未来&#xff08;NASDAQ&#xff1a;FFIE&#xf…

互联网摸鱼日报(2023-05-04)

互联网摸鱼日报&#xff08;2023-05-04&#xff09; InfoQ 热门话题 7天花5万美元&#xff0c;我们成功复制了 Stable Diffusion&#xff0c;成本大降88%&#xff01;训练代码已开源 百度爱番番 RT-CDP 架构实践 JEP 444&#xff1a;JKD 21 中出现虚拟线程&#xff0c;开创并…

互联网摸鱼日报(2022-12-19)

互联网摸鱼日报&#xff08;2022-12-19&#xff09; InfoQ 热门话题 中芯国际回应半导体万亿补贴传闻&#xff1b;字节跳动内部会&#xff1a;“去肥增瘦”人员调整将持续进行&#xff1b;美参议院通过禁止政府设备使用TikTok的法案 | AI一周资讯 通信行程卡正式下线&#xf…

王小川讽刺李彦宏活在平行宇宙,百度回击;字节盈利增八成,首超腾讯阿里;优酷回应非会员收看3000秒广告 | EA周报...

EA周报 2023年4月14日 每个星期1分钟&#xff0c;元宝带你喝一杯IT人的浓缩咖啡&#xff0c;了解天下事、掌握IT核心技术。 周报看点 1、优酷回应非会员收看3000秒广告&#xff1a;Bug已修复 2、王小川讽刺李彦宏活在平行宇宙&#xff0c;百度肖阳回击 3、字节跳动首度超越腾讯…

互联网摸鱼日报(2023-01-07)

互联网摸鱼日报&#xff08;2023-01-07&#xff09; InfoQ 热门话题 展望后端研发工程师的 2023 | InfoQ《极客有约》 2023年&#xff0c;这9个项目助你成为前端高手 IDC MarketScape &#xff1a;百度智能云位居领导者象限&#xff0c;预测2025年中国物联网平台支出将增至4…

元宇宙当年吹的牛,一个个都烂了尾

作者&#xff5c;孙鹏越 编辑&#xff5c;大 风 2021年底开始火热的元宇宙&#xff0c;还未撑过自己的“三年之痒”&#xff0c;便早早成为昨日黄花。 元宇宙曾是科技界最热门的话题&#xff0c;无论是从业人员还是网民&#xff0c;都将其视为计算机的未来&#xff0c;也许也…

云炬股市学习笔记20220118

2022年以来&#xff0c;股市没有迎来开门红&#xff0c;而且连续下跌&#xff0c;一度有了股灾的感觉。目前的股市行情基本上就是一种结构性行情&#xff0c;指数相对稳定&#xff0c;并没有特别大的涨跌。但个股的表现却是两级分化明显&#xff0c;有的个股接连上涨&#xff0…

【转载】elasticsearch 倒排索引原理

由于整型数字 integer 可以被高效压缩的特质&#xff0c;integer 是最适合放在 postings list 作为文档的唯一标识的&#xff0c;ES 会对这些存入的文档进行处理&#xff0c;转化成一个唯一的整型 id&#xff08;这个id是document的id&#xff09;。 再说下这个 id 的范围&…

第一章、计算机网络和英特网

文章目录 1.1 什么是因特网1.1.1具体构成描述1.1.2 服务描述1.1.3 什么是协议 1.2 网络边缘1.2.1 接入网1.2.2 物理媒体 1.3 网络核心1.3.1 分组交换1.3.2 电路交换1.3.3 网络的网络 1.4 分组交换网中的时延、丢包和吞吐量1.4.1 分组交换网中的时延概述1.4.2 排队时延和丢包1.4…

python连接SAP HANA 数据库

SAP 官方有关Python连接HANA数据库方式 https://developers.sap.com/tutorials/hana-clients-python.html 实例 #!/usr/bin/python3# Import your dependencies import platform from hdbcli import dbapi# verify the architecture of Python print("Platform architect…

无人机自主探索FUEL:代码阅读1--边界簇检测更新与视点生成

~/src/catkin_fuel_refactored/fuel_refactored/fuel_planner/bagbag中包含三个.sh文件&#xff0c;为rosbag指令&#xff0c;给出了录包指令以及有用话题信息 FIS 1、增量边界检测与聚类 路径&#xff1a;~/fuel_planner/active_perception/src/frontier_finder.cpp 主要函…

Elemui表单合并

原代码形式 <template><el-table:data"tableData"borderstyle"width: 100%"><el-table-columnprop"date"label"日期"width"180"></el-table-column><el-table-columnprop"name"label…

split函数和merge函数

OpenCV 中的split函数和merge函数 及示例_opencv split_zqx951102的博客-CSDN博客 #include <QApplication> #include <opencv2/imgcodecs.hpp> #include <opencv2/highgui.hpp> #include <opencv2/imgproc.hpp> #include <iostream> #include &…

什么是Java的Spring框架?

首先&#xff0c;我们来聊一下Spring框架的起源。据说&#xff0c;Spring框架的创始人之一——Rod Johnson曾经是一名Java程序员&#xff0c;他发现当时有很多类似的框架&#xff0c;每个框架都有自己的配置和编码标准&#xff0c;让人们无所适从。于是&#xff0c;他想要创建一…

界面控件DevExpress WPF数据编辑器组件,让数据处理更灵活!(二)

界面控件DevExpress WPF编辑器库可以帮助用户提供直观的用户体验&#xff0c;具有无与伦比的运行时选项和灵活性。WPF数据编辑器提供了全面的掩码和数据验证支持&#xff0c;可以独立使用&#xff0c;也可以作为容器控件(如DevExpress WPF Grid和WPF TreeList)中的单元格编辑器…

【HDFS单测】单测中MiniDFSCluster获取某个DataNode对象

本文提供两种在HDFS单元测试编写过程中获取DataNode对象的方法,如果大家还有其他方法,欢迎在评论区补充。 根据datanode ipc端口获取DataNode对象根据索引在cluster里所有的datanode列表里拿DataNode对象一、根据ipc端口获取某个DataNode: /** @return the datanode having …

chatgpt赋能python:如何让Python输出结果不换行?

如何让Python输出结果不换行&#xff1f; Python是一门高级编程语言&#xff0c;它是开发应用程序的首选语言之一。当使用Python编写应用程序时&#xff0c;我们经常需要输出一些内容到控制台。但是&#xff0c;Python默认情况下&#xff0c;每输出一行内容都会自动换行&#…

chatgpt赋能python:Python换行输出:如何在Python中实现换行输出?

Python换行输出&#xff1a;如何在Python中实现换行输出&#xff1f; 在Python编程中&#xff0c;如何将输出内容分行呈现&#xff0c;是开发者经常会遇到的问题。Python提供了多种方式来实现换行输出&#xff0c;这篇文章将会介绍其中三种。 1. 使用转义字符 \n 在Python中…

chatgpt赋能Python-pythonprint自动换行

Python Print 自动换行 Python是一种广泛使用的高级编程语言&#xff0c;因为它是一种解释型语言&#xff0c;可以轻松地编写脚本和快速原型设计。在Python编程中&#xff0c;我们通常使用print函数来输出和调试程序。当我们输出较长的文本时&#xff0c;可能会遇到自动换行问…
最新文章