十大排序——6.插入排序

这篇文章我们来介绍一下插入排序

目录

1.介绍

2.代码实现

3.总结与思考


1.介绍

插入排序的要点如下所示:

首先将数组分为两部分[ 0 ... low-1 ],[ low ... arr.length-1 ],然后,我们假设左边[ 0 ... low-1 ]是已排好序的部分右边[ low ... arr.length-1 ]是未排序的部分,然后每次从未排序的部分取出low位置的元素,插入到已排序区域

过程实例:

初始数据:65,27,59,64,58

     【27,65】59,64,58

     【27,59,65】64,58

     【27,59,64,65】58

              【27,58,59,64,65】

第一次插入:把数组分为[ 65 ]和[ 27,59,64,58 ] 两部分,然后后面一组的第一个元素即27插入到前面一直中,即把27和65进行比较,27<65,把27插入到65前面,此时【27,65】为一个有序列,后面属于无序列

第二次插入:把数组分为[ 27,65 ]和[59,64,58 ] 两部分,然后后面一组的第一个元素即59插入到前面一直中,即把59与65比较,59<65,把59和27比较,59>27,把59插入到27与65之间(后面数据与前面有序列的比较其实就是冒泡排序)

以此类推;

2.代码实现

这次的代码实现分为递归实现和非递归实现两种,供大家参考

package Sorts;import java.util.Arrays;
//插入排序
public class InsertSort {public static void main(String[] args) {int [] arr = new int[]{5,9,2,7,3,1,10};Insert2(arr);System.out.println(Arrays.toString(arr));}//递归版的方法public static void Insert1(int[]arr, int low){if (low == arr.length)return;int t = arr[low];int i = low-1;//从右向左找插入位置,如果比待插入元素大,则不断右移,空出插入位置while (i >= 0 && t <arr[i]){arr[i+1] = arr[i];i--;}//找到插入位置if (i+1 != low){arr[i+1] = t;}Insert1(arr,low+1);}public static void Insert2(int[]arr){for (int low = 1; low < arr.length-1 ; low++) {int t = arr[low];int i = low-1;//从右向左找插入位置,如果比待插入元素大,则不断右移,空出插入位置while (i >= 0 && t <arr[i]){arr[i+1] = arr[i];i--;}//找到插入位置if (i+1 != low){arr[i+1] = t;}}}
}

3.总结与思考

插入排序,一听名字应该就能知道它的逻辑是怎么样的。分两个数组,从无序数组中拿数据往有序数组中插入,并且插入到正确位置。难点就在于怎么插入,这个可以看上面代码的演示。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/312216.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue3项目 使用 element-plus 中 el-collapse 折叠面板

最近接触拉了一个项目&#xff0c;使用到 element-plus 中 el-collapse 折叠面板&#xff0c;发现在使用中利用高官网多多少少的会出现问题。 &#xff08;1.直接默认一个展开值&#xff0c;发现时显时不显 2 . 数据渲染问题&#xff0c;接口请求了&#xff0c;页面数据不更新 …

kafka学习笔记03

SpringBoot2.X项目搭建整合Kafka客户端依赖配置 用自己对应的jdk版本。 先加上我们的web依赖。 添加kafka依赖: SpringBoot2.x整合Kafka客户端adminApi单元测试 设置端口号。 新建一个kafka测试类&#xff1a; 创建一个初始化的Kafka服务。 设置kafka的名称。 测试创建kafka。…

goland2024安装包(亲测可用)

目录 一、软件简介 二、软件下载 一、软件简介 Goland 是一款由 JetBrains 公司开发的集成开发环境&#xff08;IDE&#xff09;&#xff0c;专门用于 Go 语言的开发。它提供了丰富的功能和工具&#xff0c;帮助开发者更高效地编写、调试和管理 Go 语言项目。 功能特点&#x…

机器学习——模型评价

概述 在机器学习中&#xff0c;模型评价是评估和比较不同模型性能的关键步骤之一。它是通过对模型的预测结果与真实标签进行比较&#xff0c;从而量化模型的预测能力、泛化能力和稳定性。模型评价旨在选择最佳的模型&#xff0c;理解模型的行为&#xff0c;并为模型的改进提供…

「GO基础」文件名规范、关键字与标识符

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…

Qt 4 QPushButton

Qt 常用控件 QPushButton 实例 Push Button:命令按钮。 入口文件 main.cpp #include "mainwindow.h"#include <QApplication>int main(int argc, char *argv[]) {QApplication a(argc, argv);MainWindow w;w.show();return a.exec(); }头文件 mainwindow.h …

:app debug:armeabi-v7a failed to configure C/C++

报错信息 由于刚换电脑不久&#xff0c;新建native c工程时&#xff0c;出现报错如下&#xff1a; :app debug:armeabi-v7a failed to configure C/C null java.lang.NullPointerExceptionat com.android.build.gradle.tasks.CmakeQueryMetadataGenerator.getProcessBuilder(…

实验六 智能手机互联网程序设计(微信程序方向)实验报告

实验目的和要求 请完成创建图片库应用&#xff0c;显示一系列预设的图片。 提供按钮来切换显示不同类别的图片。 二、实验步骤与结果&#xff08;给出对应的代码或运行结果截图&#xff09; 1.WXML <view> <button bindtap"showAll">所有图片</but…

使用Python进行自动化测试【第163篇—自动化测试】

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 如何使用Python进行自动化测试&#xff1a;测试框架的选择与应用 自动化测试是软件开发过程…

2024五一杯数学建模A题思路分析

文章目录 1 赛题思路2 比赛日期和时间3 组织机构4 建模常见问题类型4.1 分类问题4.2 优化问题4.3 预测问题4.4 评价问题 5 建模资料 1 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 2 比赛日期和时间 报名截止时间&#xff1a;2024…

模板的进阶

目录 非类型模板参数 C11的静态数组容器-array 按需实例化 模板的特化 函数模板特化 类模板特化 全特化与偏特化 模板的分离编译 总结 非类型模板参数 基本概念&#xff1a;模板参数类型分为类类型模板参数和非类类型模板参数 类类型模板参数&#xff1a;跟在class…

Linux硬件管理

文章目录 Linux硬件管理1.查看磁盘空间 df -h2.查看文件的磁盘占用空间 du -ah3.查看系统内存占用情况 htop Linux硬件管理 1.查看磁盘空间 df -h 语法 df [选项][参数]选项 -a或–all&#xff1a;包含全部的文件系统&#xff1b; –block-size<区块大小>&#xff1a;…

项目风采展示【车酷-保时捷第二屏】

桌面功能介绍&#xff1a; 1&#xff1a;支持本地app桌面展示 2&#xff1a;支持本地音乐控制

Spring Boot | Spring Boot 整合 “Servlet三大组件“ ( Servlet / Filter / Listene )

目录: Spring Boot 整合 "Servlet三大组件" &#xff1a;1. 使用 "组件注册" 的方式 "整合Servlet三大组件" ( 实际操作为 : 创建自定义的"三大组件"对象 结合刚创建"的自定义组件对象"来 将 XxxRegistrationBean对象 通过…

Flink CDC 的 debezium-json 格式和 debezium 原生格式是一回事吗?

博主历时三年精心创作的《大数据平台架构与原型实现&#xff1a;数据中台建设实战》一书现已由知名IT图书品牌电子工业出版社博文视点出版发行&#xff0c;点击《重磅推荐&#xff1a;建大数据平台太难了&#xff01;给我发个工程原型吧&#xff01;》了解图书详情&#xff0c;…

计算机网络 Cisco远程Telnet访问交换机和Console终端连接交换机

一、实验要求和内容 1、配置交换机进入特权模式密文密码为“abcd两位班内学号”&#xff0c;远程登陆密码为“123456” 2、验证PC0通过远程登陆到交换机上&#xff0c;看是否可以进去特权模式 二、实验步骤 1、将一台还没配置的新交换机&#xff0c;利用console线连接设备的…

深度解析SPARK的基本概念

关联阅读博客文章&#xff1a; 深入理解MapReduce&#xff1a;从Map到Reduce的工作原理解析 引言&#xff1a; 在当今大数据时代&#xff0c;数据处理和分析成为了企业发展的重要驱动力。Apache Spark作为一个快速、通用的大数据处理引擎&#xff0c;受到了广泛的关注和应用。…

IAR 使用笔记(IAR BIN大小为0异常解决)

烧写 由于芯片的内部SPI FLASH的0级BOOT 程序起到到开启JTAG SW 仿真功能&#xff0c;一旦内部SPI FLASH存储的BL0启动代码被损坏&#xff0c;芯片的JTAG 将不能被连接。所以对BL0的烧写需要谨慎&#xff0c;烧写BL0过程保证芯片不断电。 如果烧写了多备份的启动代码&#xff…

每日两题2

不同路径 class Solution { public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m1, vector<int>(n1,0));//创建dp表dp[0][1] 1;//初始化//填表for(int i 1; i < m; i){for(int j 1; j < n; j){dp[i][j] dp[i-1][j] dp[i][j-1];}}ret…

Linux 内核学习(1) --- 时钟子系统

标题 时钟系统说明时钟树Clock Provider时钟通用数据结构clock_device 的注册clock_provider DTS配置和注册clock consumer时钟系统总结 时钟系统说明 时钟就是 SoC 中的脉搏&#xff0c;由它来控制各个部件按各自的节奏跳动。比如&#xff0c;CPU主频设置&#xff0c;串口的波…