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

news/2024/4/13 11:57:32/文章来源:https://blog.csdn.net/weixin_39038328/article/details/136549136

一、插入排序

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.luyixian.cn/news_show_997798.aspx

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

相关文章

运维知识点-JBoss

JBoss 介绍介绍 JBoss是一个基于J2EE的开放源代码的应用服务器,也是一个运行EJB(Enterprise JavaBean)的容器和服务器。它支持EJB 1.1、EJB 2.0和EJB3的规范,体现了J2EE规范中最新的技术。JBoss遵循LGPL许可,可以在任何商业应用中免费使用,并且由开源社区开发,这使得JB…

ARM64汇编04 - 条件码

关于分支控制与条件码的作用可以去看 《CSAPP》的第 3.6 节&#xff0c;讲的非常清楚&#xff0c;建议看看&#xff0c;这里就不重复了。 我们直接使用一个例子来简单理解汇编是如何实现分支控制的&#xff1a; #include <stdio.h> #include <stdlib.h> #include…

软件测试相关概念和bug的相关总结

文章目录 什么是测试什么是需求测试用例(CASE)什么是BUG软件的生命周期开发模型瀑布模型螺旋模型增量模型和迭代模型 敏捷测试模型v模型W模型(双V模型) 软件测试的生命周期如何描述一个bugbug的级别bug的生命周期.产生争执怎么办 什么是测试 测试是测试人员用来检验软件的实际运…

面试题之——事务失效的八大情况

事务失效的八大情况 一、非public修饰的方法 Transactional注解只能在在public修饰的方法下使用。 /*** 私有方法上的注解&#xff0c;不生效&#xff08;因私有方法Spring扫描不到该方法&#xff0c;所以无法生成代理&#xff09;*/ Transactional private boolean test() …

python爬虫(2)

继上节 查看数组维数 可以使用数组的ndim属性 代码示例如下&#xff1a; import numpy as np c np.random.randint(1,9,5) print(c.ndim) 结果如下&#xff1a; 当然这些也可以结合前面的各种用法来使用 1、选取数组元素 &#xff08;1&#xff09;一维数组的元素…

ClickHouse SQL Reference (四)数据类型

Tuple(T1, T2, …) 元素元组&#xff0c;每个元素都有一个单独的类型。元组必须至少包含一个元素。 元组用于临时列分组。在查询中使用IN表达式时&#xff0c;以及指定lambda函数的某些形式参数时&#xff0c;可以对列进行分组。有关更多信息&#xff0c;请参阅IN操作符和高阶…

css 用flex做成田字型

哈喽&#xff0c;各位小伙伴&#xff01;今天给大家来css控制div完成田字型样式&#xff0c;来&#xff0c;看看下面的效果图&#xff1a; 一看就知道你们想要代码了&#xff0c;不急。代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head>&…

Spring Boot 生成与解析Jwt

Spring Boot 生成与解析Jwt Maven依赖 <dependency><groupId>io.jsonwebtoken</groupId><artifactId>jjwt</artifactId><version>0.9.1</version> </dependency>生成&解析 package yang;import io.jsonwebtoken.Claims…

黑马java-JavaSE进阶-网络编程

1.网络编程 可以让设备中的程序与网络上其他设备中的程序进行数据交互&#xff08;实现网络通信&#xff09; 2.基本通信架构 基本通信架构有两种形式&#xff1a;CS架构、BS架构 3.基本概念&#xff1a; IP&#xff1a;设备在网络中的地址&#xff0c;是唯一的标识 端口&#…

学c++对Python有帮助吗?

学习C对Python编程确实有帮助&#xff0c;尽管这两种语言在许多方面有很大的不同。以下是学习C可能对Python编程产生帮助的几个方面&#xff1a; 理解底层概念&#xff1a;C是一种更接近硬件的编程语言&#xff0c;它要求程序员更深入地理解内存管理、指针、数据类型等底层概念…

【Proteus仿真】【51单片机】坐姿矫正提醒器设计

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真51单片机控制器&#xff0c;使用LCD1602液晶显示模块、HC-SR04超声波模块、蜂鸣器、按键、人体红外传感器等。 主要功能&#xff1a; 系统运行后&#xff0c;LCD1602显示超声波检…

Android fragment的使用案例

效果图&#xff1a;两个点击事件&#xff0c;显示不同的fragment布局 默认是如下图&#xff0c;点击页面一也如下图 点击页面二如下图&#xff1a; Android Fragment的生命周期是与其所在的Activity紧密相关的。当一个Fragment被添加到Activity中时&#xff0c;它将经历一系列…

Android使用WebView打开网页链接(内嵌H5网页)的两种方式之一

发布Android应用&#xff0c;除了用原生开发外&#xff0c;更多是采用内嵌H5网页的方式来做&#xff0c;便于更新以及多平台使用。 一、第一种方式是直接通过WebView打开外部H5链接。 新建Android工程 直接创建一个工程&#xff0c;点击运行就可以了&#xff0c;打开是个空页…

大路灯护眼灯哪个牌子好?精心挑选五款大路灯,无广分享

当前&#xff0c;大路灯作为一种良好帮助改善光线环境的工具&#xff0c;受到了广泛关注&#xff0c;并以其卓越的光线舒适度功能赢得了许多用户的青睐。然而&#xff0c;其迅速增长的人气也伴随着一些负面反响&#xff0c;其中包括了关于可能对眼睛造成损伤和健康风险的报道。…

代码之旅:我的算法探索之路(二)力扣 最接近的三数之和

目录 LeetCode 第16题 最接近的三数之和 题目 解题思路 代码 结果 LeetCode 第18题 四数之和 题目 解题思路 代码 结果 LeetCode 第16题 最接近的三数之和 题目 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数&#xff0c;使…

TCP传输收发

TCP通信: TCP发端: socket connect send recv close TCP收端: socket bind listen accept send recv close 1.connect int connect(int sockfd, const struct sockaddr *addr, socklen_t ad…

HTML5:七天学会基础动画网页9

在进行接下来的了解之前我们先来看一下3d的xyz轴&#xff0c;下面图中中间的平面就相当于电脑屏幕&#xff0c;z轴上是一个近大远小的效果。 3d转换属性 transform 2D或3D转换 transform-origin 改变旋转点位置 transform-style 嵌套元素在3D空间如何显 …

IM聊天交友APP源码IM带音视频Uniapp即时通讯安卓苹果APP修改二开

前端开发语言&#xff1a;VUE&#xff08; 安卓&#xff0c;IOS,WEB为一套前端代码&#xff09; 服务器端开发语言: PHPWebSocket 数据库&#xff1a;MySql mongodb 前端打包工具&#xff1a;Hbuilder 服务器搭建工具&#xff1a;宝塔 Xshell 短信接口&#xff1a; 支持…

DxO PureRAW:赋予RAW图像生命,打造非凡视觉体验 mac/win版

DxO PureRAW 是一款专为RAW图像处理而设计的软件&#xff0c;旨在帮助摄影师充分利用RAW格式的优势&#xff0c;实现更加纯净、细腻的图像效果。该软件凭借其强大的功能和易于使用的界面&#xff0c;成为了RAW图像处理领域的佼佼者。 DxO PureRAW 软件获取 首先&#xff0c;Dx…

R语言,实现MACD指标计算:股票技术分析的利器系列(1)

R语言&#xff0c;实现MACD指标计算&#xff1a;股票技术分析的利器系列&#xff08;1&#xff09; MACD指标代码完整代码介绍代码EMA函数calculate_DEA 函数calculate_MACD 函数 运行结果 MACD指标 先看看官方介绍&#xff1a; MACD (平滑异同平均线&#xff09; 指标说明 DI…