排序算法:插入排序和希尔排序

一、插入排序

1.基本原理

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

2.动态图

在这里插入图片描述
在这里插入图片描述

3.代码

①:交换方式

public class ThreadNew{public static void main(String[] args) {int[] arr = new int[] {6,5,3 ,1,8,7,2,4};Sort(arr);}public static void Sort(int[] arr) {for (int i = 1; i < arr.length; i++) {//将当前数据插入到已经有序的数字当中(这里需要倒着往前找)for ( int j = i-1; j >= 0; j--) {//前后位置进行交换if (arr[j] > arr[j+1]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}else {break;}}System.out.println(Arrays.toString(arr));}}
}

②:移位方式

public class InsertSort {public static void main(String[] args) {int[] arr = {-1,100,4,23,2,45,67,89,-3,56};System.out.print("排序前:");System.out.println(Arrays.toString(arr));insertSort(arr);}//直接插入排序(移位方式)public static void insertSort(int[] arr){for(int i=1;i<arr.length;i++){int insertVal = arr[i];int insertIndex = i;while (insertIndex>0 && insertVal<arr[insertIndex-1]){arr[insertIndex]=arr[insertIndex-1];insertIndex--;}arr[insertIndex] = insertVal;//输出每趟的结果System.out.print("第" + i + "轮:");System.out.println(Arrays.toString(arr));}//排序完成后输出最终的结果System.out.println("==================================================");System.out.println(Arrays.toString(arr));}
}

二、希尔排序

1.简单插入排序存在的问题

数组arr = {2,3,4,5,6,1}这时要插入的数据1(最小),过程是这样的:
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论:当需要插入得数是较小的数时,后移的次数明显增多,对效率有影响

2.希尔排序介绍

希尔排序也是一种插入排序。它是简单插入排序进过改进之后的一个更高效的版本,也成为了缩小增量排序

3.希尔排序的基本思想

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量主键递减,每组包含的关键词也来越多,当增量减至1时,整个文件恰被分成一组,算法终止。如下图:
在这里插入图片描述
在这里插入图片描述

4.交换式 算法实现

public class ShellSort {public static void main(String[] args) {int arr[] = new int[]{8,9,1,7,2,3,5,4,6,0};shellSort(arr);}// 使用逐步推导的方式来编写希尔排序public static void shellSort(int[] arr){// 第一轮:是将10个数据分成了5组,这里的 i 值得是我们的步长,// 既 我们的 i 指向一组元素当中的 第二个 :注意是第二个for (int i = 5 ;i < arr.length;i++){// 定义 指针 j : 指向数组当中的每一个元素  默认 j 指向的是该组当中的第一个元素// j -= 5 :这里的 5 值得是步长for(int j = i-5; j>=0; j -= 5){// 如果当前元素大于加上步长之后的元素,则交换if(arr[j] > arr[j+5]){int temp = arr[j];arr[j] = arr[j+5];arr[j+5] = temp;}}}// 第二轮:是将10个数据分成了2组,这里的 i 值得是我们的步长,// 既 我们的 i 指向一组元素当中的 第二个 :注意是第二个for (int i = 2 ;i < arr.length;i++){// 定义 指针 j : 指向数组当中的每一个元素  默认 j 指向的是该组当中的第一个元素// j -= 2 :这里的 2 值得是步长for(int j = i-2; j>=0; j -= 2){// 如果当前元素大于加上步长之后的元素,则交换if(arr[j] > arr[j+2]){int temp = arr[j];arr[j] = arr[j+2];arr[j+2] = temp;}}}// 第三轮:是将10个数据分成了1组,这里的 i 值得是我们的步长,// 既 我们的 i 指向一组元素当中的 第二个 :注意是第二个for (int i = 1 ;i < arr.length;i++){// 定义 指针 j : 指向数组当中的每一个元素  默认 j 指向的是该组当中的第一个元素// j -= 2 :这里的 2 值得是步长for(int j = i-1; j>=0; j -= 1){// 如果当前元素大于加上步长之后的元素,则交换if(arr[j] > arr[j+1]){int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}System.out.println(Arrays.toString(arr));}//最后的整合代码for(int gap = arr.length /2;gap > 0;gap /= 2){for (int i = gap ;i < arr.length;i++){// 定义 指针 j : 指向数组当中的每一个元素  默认 j 指向的是该组当中的第一个元素// j -= gap :这里的 gap 值得是步长for(int j = i-gap; j>=0; j -= gap){// 如果当前元素大于加上步长之后的元素,则交换if(arr[j] > arr[j+gap]){int temp = arr[j];arr[j] = arr[j+gap];arr[j+gap] = temp;}}}}}

完成以后我们来进行一下测试,让他和我们的直接插入排序进行对比。

public static void main(String[] args) {int[] arr = new int[80000];for(int i = 0;i< 80000;i++){arr[i] = (int) (Math.random()*80000);}long startTime=System.nanoTime();   //获取开始时间shellSort(arr);long endTime=System.nanoTime(); //获取结束时间System.out.println("希尔排序运行时间: "+(endTime-startTime)+"ns");long startTime1=System.nanoTime();   //获取开始时间insertsort(arr);long endTime1=System.nanoTime(); //获取结束时间System.out.println("直接插入运行时间: "+(endTime1-startTime1)+"ns");
}

在这里插入图片描述
这个时间差距好像不是我们想要看到的结果。
耗时的原因:交换所产生的的耗时
在这里插入图片描述

5.移位式 算法实现

// 这个算法需要仔细去推敲
public static void shellSort2(int[] arr){for(int gap = arr.length /2;gap > 0;gap /= 2){for (int i = gap ;i < arr.length;i++){int j = i;int temp = arr[j];if(arr[j] <arr[j-gap]){while (j - gap >=0 && temp <arr[j-gap]){//移动arr[j] = arr[j-gap];j -= gap;}arr[j] = temp;}}}
}

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

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

相关文章

重读 Java 设计模式: 探索经典之道与 Spring 框架的设计

写在开头 记得大学刚毕业那会儿&#xff0c;想学点东西&#xff0c;于是拿出了《Head First 设计模式》这本书&#xff0c;就开始了阅读&#xff0c;我曾对这些模式感到晦涩难懂。然而&#xff0c;随着工作岁月的增长&#xff0c;我逐渐领悟到设计模式的价值&#xff0c;尤其是…

类和对象(4)

文章目录 1. const成员2.取地址及const取地址操作符重载3. 再谈构造函数3.1构造函数体赋值3.2初始化列表 1. const成员 将const修饰的成员函数称为const成员函数。 const修饰类成员函数&#xff0c;实际修饰该成员函数的隐含地this指针&#xff0c;表明在该成员函数中不能对类…

【echarts】xAxis鼠标事件失效问题

项目中用到echarts柱状图&#xff0c;出现x轴标签文字过长重叠问题&#xff0c;在pass掉标签倾斜、换行方案之后最终决定限制文字长度&#xff0c;超出以…占位&#xff0c;鼠标悬浮时显示完整tooltip。 但编写过程中发现xAxis鼠标事件无法触发&#xff0c;只有bar区域是可触发…

【C++杂货铺】详解string

目录 &#x1f308;前言&#x1f308; &#x1f4c1; 为什么学习string &#x1f4c1; 认识string&#xff08;了解&#xff09; &#x1f4c1; string的常用接口 &#x1f4c2; 构造函数 &#x1f4c2; string类对象的容量操作 &#x1f4c2; string类对象的访问以及遍历操…

【uni-app】condition 启动模式配置,生产环境无效,仅开发期间生效

在小程序开发过程中&#xff0c;每次代码修改后&#xff0c;都会启动到首页&#xff0c;有时非常不方便&#xff0c;为了更高效的开发&#xff0c;有时需要模拟直接跳转到指定的页面&#xff0c; 操作方法如下&#xff1a; 在pages.joson里面配置下列代码&#xff1a; "…

解决 matplotlib 中文显示乱码的问题

matplotlib 库默认只显示中文 例如&#xff1a; import matplotlib.pyplot as pltimg plt.imread(test.jpg)# plt.rcParams[font.sans-serif] [SimHei] # 用来正常显示中文标签 # plt.rcParams[axes.unicode_minus] False # 用来正常显示负号 #有中文出现的情况&#xf…

宏auto关键字(C++基础)

宏 宏可以实现对语句的同义替换&#xff0c;简单来说就是预处理阶段、编译前的替换&#xff08;包括符号&#xff0c;变量等&#xff09;。 #define LOG(x) std::cout << x << std::endl; LOG("hello") 可以正常使用。 下面通过上图中借用不同开发模…

YOLOv8改进 | 独家创新篇 | 利用DCNv3集合DLKA形成全新的注意力机制(全网独家创新)

一、本文介绍 本文给大家带来的机制是由我独家创新结合Deformable Large Kernel Attention (D-LKA) 注意力机制和DCNv3可变形卷积的全新注意力机制模块(算是二次创新),D-LKA的基本原理是结合了大卷积核和可变形卷积的注意力机制,通过采用大卷积核来模拟类似自我关注的感受…

MySQL学习笔记(一)数据库事务隔离级别与多版本并发控制(MVCC)

一、数据库事务隔离级别 数据库事务的隔离级别有4种&#xff0c;由低到高分别为Read uncommitted &#xff08;读未提交&#xff09;、Read committed&#xff08;读提交&#xff09; 、Repeatable read&#xff08;可重复读&#xff09; 、Serializable &#xff08;串行化&a…

OpenAI劲敌吹新风! Claude 3正式发布,Claude3使用指南

Claude 3是什么&#xff1f; 是Anthropic 实验室近期推出的 Claude 3 大规模语言模型&#xff08;Large Language Model&#xff0c;LLM&#xff09;系列&#xff0c;代表了人工智能技术的一个显著飞跃。 该系列包括三个不同定位的子模型&#xff1a;Claude 3 Haiku、Claude 3…

06 - ip route和route -n的区别

1 ip route和route -n的区别 ip route 和 route -n 都是用于查看和管理Linux系统路由表的命令。但下面是它们的区别&#xff1a; ip route&#xff1a;是Linux系统中的现代工具&#xff0c;它属于iproute2套件&#xff1b;它提供了更多的选项&#xff0c;可以更精确地控制路由表…

弱电综合布线:连接现代生活的纽带

在当今信息化快速发展的时代&#xff0c;弱电网络布线作为信息传输的重要基础设施&#xff0c;其作用日益凸显。它不仅保障了数据的高效流通&#xff0c;还确保了通信的稳定性。从商业大厦到教育机构&#xff0c;从政府机关到医院急救中心&#xff0c;再到我们居住的社区&#…

EIP-1559

EIP EIP是以太坊改进提案&#xff08;Ethereum Improvement Proposal&#xff09;的缩写。它是一种标准化的提案制度&#xff0c;用于描述和讨论对以太坊区块链网络的改进和升级。EIP的目的是提供一个开放的、透明的过程&#xff0c;让社区成员、开发者和其他利益相关者能够共同…

短视频矩阵系统----矩阵系统源码搭建(技术门槛?)

短视频矩阵是什么意思&#xff1f;短视频矩阵的含义可以理解为全方位的短视频账号&#xff0c;通过不同的账号实现全方位的品牌展示。实际上是指一个短视频账号&#xff0c;通过不同的链接实现品牌展示&#xff0c;在不同的粉丝流量账号中互相转发同一个品牌&#xff0c;在主账…

pytorch CV入门3-预训练模型与迁移学习.md

专栏链接&#xff1a;https://blog.csdn.net/qq_33345365/category_12578430.html 初次编辑&#xff1a;2024/3/7&#xff1b;最后编辑&#xff1a;2024/3/8 参考网站-微软教程&#xff1a;https://learn.microsoft.com/en-us/training/modules/intro-computer-vision-pytorc…

外包干了8天,技术退步明显。。。。。

先说一下自己的情况&#xff0c;本科生&#xff0c;19年通过校招进入杭州某软件公司&#xff0c;干了接近3年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试…

能源大数据采集,为您提供专业数据采集服务

随着经济的不断发展&#xff0c;能源产业也逐渐成为国民经济的支柱产业之一。而对于能源行业来说&#xff0c;数据采集是一项至关重要的工作。以往&#xff0c;能源企业采集数据主要依靠人工收集、整理&#xff0c;但是这种方式不仅效率低下&#xff0c;而且容易出现数据不准确…

Python测试框架Pytest的基础入门

Pytest简介 Pytest is a mature full-featured Python testing tool that helps you write better programs.The pytest framework makes it easy to write small tests, yet scales to support complex functional testing for applications and libraries. 通过官方网站介绍…

SpringBoot 手写 Starter

1.介绍 SpringBoot中的starter是一种非常重要的机制&#xff0c;能够抛弃以前繁杂的配置&#xff0c;将其统一集成进starter&#xff0c;应用者只需要在maven中引入starter依赖&#xff0c;SpringBoot就能自动扫描到要加载的信息并启动相应的默认配置。starter让我们摆脱了各种…

九型人格测试,8号领袖型人格的职业分析

8号人格&#xff0c;也叫领袖型人格&#xff0c;在九型人格中间&#xff0c;是一种天生领导的存在。他们生性开朗&#xff0c;能够和其他人建立良好的关系&#xff0c;为人不拘小节&#xff0c;遇强则强&#xff0c;坚守心中的理想和正义。不喜欢被人控制&#xff0c;喜欢自己当…