插入排序:简单而有效的排序方法
在计算机科学中,排序算法是一个重要且常见的主题,它们用于对数据进行有序排列。插入排序(Insertion Sort)是其中一个简单但有效的排序算法。本文将详细解释插入排序的原理和步骤,并提供Java语言的实现示例。
插入排序的原理及性能分析
插入排序的核心思想是逐个将未排序的元素插入到已排序的部分中,构建有序序列。这个过程类似于整理扑克牌,每次拿出一张牌并将其插入到已排序的牌堆中。
插入排序的步骤
插入排序的步骤可以简单概括为以下几个阶段:
-
初始状态: 将数组的第一个元素视为已排序部分,其余部分为未排序部分。
-
逐个插入: 从未排序部分选择一个元素,将其插入到已排序部分的正确位置。为了插入,将已排序部分中大于待插入元素的元素向右移动一个位置。
-
重复: 重复上述插入步骤,直到所有元素都被插入到已排序部分。
-
完成: 当算法完成时,整个数组就被排序了。
Java实现插入排序
以下是使用Java语言实现插入排序算法的示例代码:
public class Test {public static void main(String[] args) {int[] arr = new int[]{5,2,4,6,7,1,3};insertionSort(arr);}public static void insertionSort(int[] arr){System.out.println("原始数组:"+ Arrays.toString(arr));//获取数组长度int len = arr.length;// 循环 len-1 次,进行数组排序。第一次将数组的第一个元素视为已排序的部分,// 每次将未排序部分的第一个元素插入到已排序的部分。for(int i = 1 ; i< len ; i++){//目标元素,未排序部分的第一个元素,即当前循环中要插入排序的元素int target = arr[i];//已排序元素中的最后一个元素的下标int j = i-1;// 循环已排序的部分的数组,找到目标元素应该存放的下标while (j>= 0 && arr[j] > target ){// 如果插入元素小于当前元素,则将当前元素后移一位arr[j+1] = arr[j];// 当前已排序的数据比较元素的下标前移一位j--;}//将目标元素插入到正确的位置arr[j+1] = target;// 打印每趟排序完成后的数组状态,以便查看排序进度System.out.println("第"+i+"趟排序完成的数组:"+ Arrays.toString(arr));}System.out.println("排序完成的数组:"+ Arrays.toString(arr));}
}
以上代码演示了如何使用插入排序对一个整数数组进行排序。插入排序算法的核心思想是逐个将未排序的元素插入到已排序的部分,直到整个数组排序完成。
性能及优缺点的分析
插入排序(Insertion Sort)是一种简单但性能较差的排序算法,其性能取决于输入数据的初始顺序。以下是对插入排序性能的分析:
- 时间复杂度
在最坏情况下,插入排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2),其中n是数组的长度。这是因为在最坏情况下,每个元素都需要与已排序部分中的所有元素进行比较和移动。在最好情况下,如果输入数据已经接近有序,插入排序的时间复杂度可以降至O(n),因为很少需要移动元素。
- 空间复杂度
插入排序是一种稳定排序算法,其空间复杂度为O(1),因为它只需要常量级别的额外空间来存储临时变量。
- 稳定性
插入排序是一种稳定的排序算法,即具有相等键值的元素在排序后仍然保持相对顺序。
- 适用性
插入排序适用于小型数据集或已接近排序状态的数据集。对于大型数据集,插入排序的性能会变得相对较差,并且不如一些更高级的排序算法,如快速排序或归并排序。
- 优点
插入排序的优点是实现简单,易于理解和调试。在某些情况下,它可能比其他排序算法更快,尤其是对于小型数据集。
- 缺点
插入排序的缺点是其时间复杂度较高,特别是在大型数据集上。对于大规模数据,更高效的排序算法通常更受欢迎。
总结
总的来说,插入排序是一种简单但性能较差的排序算法,主要用于教学和小型数据集。在实际应用中,通常会选择更高效的排序算法,以提高排序速度。
相关文章:
插入排序:简单而有效的排序方法
在计算机科学中,排序算法是一个重要且常见的主题,它们用于对数据进行有序排列。插入排序(Insertion Sort)是其中一个简单但有效的排序算法。本文将详细解释插入排序的原理和步骤,并提供Java语言的实现示例。 插入排序的…...
OpenGL之光照贴图
我们需要拓展之前的系统,引入漫反射和镜面光贴图(Map)。这允许我们对物体的漫反射分量和镜面光分量有着更精确的控制。 漫反射贴图 我们希望通过某种方式对物体的每个片段单独设置漫反射颜色。我们仅仅是对同样的原理使用了不同的名字:其实都是使用一张覆盖物体的图像,让我…...
隐私交易成新刚需,Unijoin 凭什么优势杀出重围?
随着区块链技术的普及和发展,全球加密货币用户在持续增长,根据火币研究院公布的数据,2022年全球加密用户已达到 3.2亿人,目前全球人口总数超过了 80亿,加密货币用户渗透率已达到了 4%。 尤其是在 2020 年开启的 DeFi 牛…...
小谈设计模式(12)—迪米特法则
小谈设计模式(12)—迪米特法则 专栏介绍专栏地址专栏介绍 迪米特法则核心思想这里的“朋友”指当前对象本身以参数形式传入当前对象的对象当前对象的成员变量直接引用的对象目标 Java程序实现程序分析 总结 专栏介绍 专栏地址 link 专栏介绍 主要对目…...
Foxit PDF
Foxit PDF 福昕PDF 软件,可以很好的编辑PDF文档。 调整PDF页面大小 PDF文档中,一个页面大,一个页面小 面对这种情况,打开Foxit PDF 右键单击需要调整的页面,然后选择"调整页面大小". 可以选择…...
《Python趣味工具》——ppt的操作(刷题版)
前面我们对PPT进行了一定的操作,并将其中的文字提取到了word文档中。现在就让我们来刷几道题巩固巩固吧! 文章目录 1. 查看PPT(上)2. 查看PPT(中)3. 查看PPT(下)4. PPT的页码5. 大学…...
实战型开发--3/3,clean code
编程的纯粹 hmmm,一开始在这个环节想聊一些具体的点,其实也就是《clean code》这本书中的点,但这个就还是更流于表面; 因为编码的过程,就更接近于运动员打球,艺术家绘画,棋手下棋的过程&#x…...
家用无线路由器如何用网线桥接解决有些房间无线信号覆盖不好的问题(低成本)
环境 光猫ZXHN F677V9 水星MW325R 无线百兆路由器 100M宽带,2.4G无线网络 苹果手机 安卓平板电脑 三室一厅94平 问题描述 家用无线路由器如何用网线桥接解决有些房间无线信号不好问题低成本解决,无线覆盖和漫游 主路由器用的运营商的光猫自带无…...
【Golang】网络编程
网络编程 网络模型介绍 OSI七层网络模型 在软件开发中我们使用最多的是上图中将互联网划分为五个分层的模型: 物理层数据链路层网络层传输层应用层 物理层 我们的电脑要与外界互联网通信,需要先把电脑连接网络,我们可以用双绞线、光纤、…...
使用策略模式优化多重if/else
一、为什么需要策略模式? 作为前端程序员,我们经常会遇到这样的场景,例如 进入一个营销活动页面,会根据后端下发的不同 type ,前端页面展示不同的弹窗。 async getMainData() {try {const res await activityQuery()…...
逆强化学习
1.逆强化学习的理论框架 1.teacher的行为被定义成best 2.学习的网络有两个,actor和reward 3.每次迭代中通过比较actor与teacher的行为来更新reward function,基于新的reward function来更新actor使得actor获得的reward最大。 loss的设计相当于一个排序问…...
postgresql新特性之Merge
postgresql新特性之Merge 创建测试表测试案例 创建测试表 create table cps.public.test(id integer primary key,balance numeric,status varchar(1));测试案例 官网介绍 merge into test t using ( select 1 id,0 balance,Y status) s on(t.id s.id) -- 当匹配上了,statu…...
【注解】注解解析与应用场景
注解解析与应用场景 1.注解解析 注解解析就是判断类上、方法上、成员变量上是否存在注解,并把注解里的内容给解析出来 2.如何解析注解? 思想:要解析谁上面的注解,就应该先拿到谁(通过反射)如果要解析类…...
mysql面试题14:讲一讲MySQL中什么是全同步复制?底层实现?
该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:讲一讲mysql中什么是全同步复制?底层实现? MySQL中的全同步复制(Synchronous Replication)是一种复制模式,主服务器在写操作完成后,必须等待…...
Linux驱动设备号分配与自动创建设备节点
Linux 驱动设备号 对于 Linux 系统,为了识别和管理设备,每个设备便使用一个唯一的编号来标记设备,每个注册到内核的设备都需要一个编号,这个编号就是设备号,为了细分设备号分为主设备号和次设备号。 由于 Linux 的设…...
基于MFC和OpenCV实现人脸识别
基于MFC和OpenCV实现人脸识别 文章目录 基于MFC和OpenCV实现人脸识别1. 项目说明1. 创建项目2. 启动窗口3. 登录窗口-添加窗口、从启动窗口跳转4. 启动窗口-美化按钮5. 登录窗口-美化按钮、雪花视频6. 注册窗口-美化按钮、雪花视频、从启动窗口跳转7. 注册窗口-开启摄像头8. 注…...
力扣 -- 377. 组合总和 Ⅳ
解题步骤: 参考代码: class Solution { public:int combinationSum4(vector<int>& nums, int target) {int nnums.size();vector<double> dp(target1);//初始化dp[0]1;//填表for(int i1;i<target;i){for(int j0;j<n;j){//填表if(…...
阿里云新账户什么意思?老用户、产品首购详细说明
阿里云新账户、老账号、产品首购和同人账号什么意思?阿里云账号分为云新账户、老账户、产品首购、同人账号和同一用户,阿里云官方推出的活动很多是限制账号类型的,常见的如阿里云新用户,什么是阿里云新用户?是指从未在…...
C++ YAML使用
C++工程如何使用YAML-cpp 一、前期准备工作 1、已安装minGW、cmake、make等本地工具。 2、下载YAML-cpp第三方开源代码(一定要下载最新的release版本,不然坑很多)。 3、生成YAML-cpp静态库 (1)在yaml-cpp-master下建立build文件夹; (2)在该文件夹下生成MakaFile文…...
十二、Django之模板的继承+用户列表
模板的继承 新建layout.html: {% load static %} <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><link rel"stylesheet" href"{% static plugins…...
wzsc_文件上传(条件竞争)
打开题目链接,很常见的文件上传框 经过尝试,发现上传东西后会调用upload.php,猜测文件被传到upload目录下 随便传了几个类型的文件,访问upload目录 发现.php文件以及.htaccess、.user.ini这种配置文件都没有传上去 但是通过抓包…...
unplugin-vue-components和unplugin-auto-import插件
unplugin-auto-import:自动按需引入 vue\vue-router\pinia 等的 api unplugin-vue-components:自动按需引入 第三方的组件库组件 和 我们自定义的组件 使用此类插件,不需要手动编写import {xxx} from vue这样的代码了,提升开发效…...
docker系列文章目录
docker系列专栏笔记总算完成了,平时下班比较晚,利用晚上的一些时间整理了这一系列的学习笔记。 docker系列教程包含以下几个方面: docker环境篇 介绍docker环境的搭建,已经管理平台工具(portainer)的简单使用。 docker常用命令篇…...
第80步 时间序列建模实战:GRNN回归建模
基于WIN10的64位系统演示 一、写在前面 这一期,我们使用Matlab进行GRNN模型的构建。 使用的数据如下: 采用《PLoS One》2015年一篇题目为《Comparison of Two Hybrid Models for Forecasting the Incidence of Hemorrhagic Fever with Renal Syndrom…...
《C和指针》笔记33:指针数组
除了创建整型数组一样,也可以声明指针数组。 int *api[10];为了弄清这个复杂的声明,我们假定它是一个表达式,并对它进行求值。下标引用的优先级高于间接访问,所以在这个表达式中,首先执行下标引用。因此,a…...
C/C++字符函数和字符串函数详解————内存函数详解与模拟
个人主页:点我进入主页 专栏分类:C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 欢迎大家点赞,评论,收藏。 一起努力,一起奔赴大厂。 目录 1.前言 2 .memcpy函数 3.memmove函…...
CAcUiDockControlBar初始位置 2023/8/19 下午3:51:18
2023/8/19 下午3:51:18 CAcUiDockControlBar初始位置 2023/8/19 下午3:52:00 CAcUiDockControlBar的初始位置是根据其在程序代码中的设置而确定的。通常情况下,它的初始位置可以通过以下几种方式进行设置: 使用Create函数:在创建CAcUiDockControlBar对象时,可以调用Cre…...
CDH6.3.2 的pyspark读取excel表格数据写入hive中的问题汇总
需求:内网通过Excel文件将数据同步到外网的CDH服务器中,将CDH中的文件数据写入hive中。 CDH版本为:6.3.2 spark版本为:2.4 python版本:2.7.5 操作系统:CentOS Linux 7 集群方式:yarn-cluster …...
2120 -- 预警系统题解
Description OiersOiers 国的预警系统是一棵树,树中有 �n 个结点,编号 1∼�1∼n,树中每条边的长度均为 11。预警系统中只有一个预警信号发射站,就是树的根结点 11 号结点,其它 �−1…...
C++入门-day01
一、认识C C融合了三种不同的编程方式 C代表的过程性语言在C基础上添加的类、结构体puls代表的面向对象语言C模板支持泛型编程 C完全兼容C的特性 Tips:侯捷老师提倡的Modren C是指C11、C14、C17和C20这些新标准所引入的一系列新特性和改进。在我们练习的时候也应当去…...
网页设计基础教程视频教程/seo优化裤子关键词
qt中有时候使用new后并没有使用delete,原因是 Qt 自动回收是靠父子关系。父亲销毁了。他的孩子也销毁。 #include "mainwindow.h" #include <QApplication> #include <QTextCodec> #include <QLabel> int main(int argc, char *argv[…...
wordpress图片加载快/实训百度搜索引擎的总结
题目要求:根据《福建省电网销售电价表》,居民生活用电按3个梯度收费:月用电量150千瓦时及以下部分,每千瓦时0.4463元,151—400千瓦时部分为0.4663元,401千瓦时以上部分为0.5663元,请编写程序&am…...
商城网站制作教程/大数据分析培训机构
地球更智慧,人类怎么办?阿祥(比特网)2008年已经过去,IBM给世界留下了一个想象,也是一个方向,那就是“智慧地球”。早有10年前的1998年1月31日,美国副总统戈尔在加利福尼亚科学中心放出惊人之论,第一次提出…...
怎么做网站教程html文本文档/在线刷seo
基于9款CSS3鼠标悬停相册预览特效里面包含九款不同方式的相册展开特效代码。效果图如下: 在线预览 源码下载 实现的代码。 html代码: <div class"albums"><div class"albums-inner"><div class"albums-tab&q…...
wordpress建站应用/长沙推广公司
1.什么是BIO?什么是NIO?什么是AIO? BIO是同步阻塞式IO,一个连接对应一个线程.每当有一个客户端请求连接,都要在服务端创建一个线程来服务这个客户端(因为这时候会阻塞,不能够接受其他客户端的连接请求),如果有很多客户端,就会对应成千上万个服务端线程,这会导致服务端负载过…...
阿里云做的网站如何发布/每日精选12条新闻
课程首页在:http://blog.csdn.net/sxhelijian/article/details/11890759【项目5-字符串统计】阅读下面的程序,完成类似的功能#include<iostream> #include<cstdio> using namespace std; int main() { char str[50]; int i0,n0; cout…...