插入排序与希尔排序

个人主页:Lei宝啊

愿所有美好如期而遇


前言:

这两个排序在思路上有些相似,所以有人觉得插入排序和希尔排序差别不大,事实上,他们之间的差别不小,插入排序只是希尔排序的最后一步。


目录

前言:

插入排序:

思路:

图解:

代码:

希尔排序:

思路:

图解:

代码:


插入排序:

思路:

当我们有了一个有序的数组arr,假设为升序,现在向里面插入一个新数据。

我们假设这个数组有n个元素,最后一个元素的下标我们记作end,那么要插入的这个数下标为end+1,并用tmp记下这个数的大小。

接下来,如果tmp小于arr[end],那么arr[end+1] = arr[end];  end--,

              如果tmp大于等于arr[end],那么break;   arr[end+1] = tmp;  

重复上述操作,直到end < 0或者break跳出


那么面对一个无序的数组,我们可以将第一个元素当做有序,第二个元素为新插入元素,依次类推排序

图解:

代码:

void InsertSort(int* arr, int n)
{//i == n - 2时,temp = arr[n - 1];for (int i = 0; i < n - 1; i++){int end = i;int temp = arr[end + 1];//此处画个图,end小于0跳出循环while (end >= 0){if (temp < arr[end]){//插入的值比end小,end值向后移动一位arr[end + 1] = arr[end];end--;}else{break;}}//写在循环外的原因是如果while循环不是break出来的//会导致第一个元素值重复,插入的值最后未插入进去arr[end + 1] = temp;}}

希尔排序:

思路:

希尔排序比插入排序多的就是预排序,而预排序的目的就是让大的数据/小的数据更快的被排到后面去,因为越接近有序的数据,使用插入排序时时间复杂度越接近O(N),而我们的希尔排序最后一步等同于插入排序

图解:

以代码一为例:

代码:

两个代码没有什么差别,只是一个是一组一组排,一个是并排。

代码一:
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){//多组预排序,最后接近有序时插入排序gap /= 2;//完成一趟预排序for (int j = 0; j < gap; j++){//完成一组预排序for (int i = j; i < n - gap; i += gap){//走一组中的一个位置的预排序int end = i;int temp = arr[end + gap];while (end >= 0){if (temp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = temp;}}}}
代码二:
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){//多组预排序,最后接近有序时插入排序gap /= 2;//等同于上面的希尔排序,不是分组排了,而是并排for (int i = 0; i < n - gap; i++){//走一组中的一个位置的预排序int end = i;int temp = arr[end + gap];while (end >= 0){if (temp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = temp;}	}
}

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

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

相关文章

华为数通方向HCIP-DataCom H12-831题库(单选题:161-180)

第161题 某台路由器Router LSA如图所示,下列说法中错误的是? A、本路由器已建立邻接关系 B、本路由器为DR C、本路由支持外部路由引入 D、本路由器的Router ID为10.0.12.1 答案: B 解析: 一类LSA的在transnet网络中link id值为DR的route id ,但Link id的地址不是10.0.12.…

对pyside6中的textedit进行自定义,实现按回车可以触发事件。

以下方法不算最优解。因为这个ui文件很容易重新编译&#xff0c;使写在ui.py里面的代码被删掉。 所以更好的方法应该是在主代码当中单独定义控件。并且使用布局添加控件到界面中。 以下内容纯为旧版实现&#xff0c;仅供参考&#xff1a; 我的实现方法是&#xff0c;先用qt de…

学信息系统项目管理师第4版系列15_资源管理基础

1. 项目资源 1.1. 实物资源 1.1.1. 着眼于以有效和高效的方式&#xff0c;分配和使用完成项目所需的实物资源 1.1.2. 包括设备、材料、设施和基础设施 1.2. 团队资源 1.2.1. 人力资源 1.2.2. 包含了技能和能力要求 2. 人力资源管理 2.1. 不仅是组织中最重要的资源之一&…

设计模式之抽象工厂模式--创建一系列相关对象的艺术(简单工厂、工厂方法、到抽象工厂的进化过程,类图NS图)

目录 概述概念适用场景结构类图 衍化过程业务需求基本的数据访问程序工厂方法实现数据访问程序抽象工厂实现数据访问程序简单工厂改进抽象工厂使用反射抽象工厂反射配置文件衍化过程总结 常见问题总结 概述 概念 抽象工厂模式是一种创建型设计模式&#xff0c;它提供了一种将相…

【开发篇】十、Spring缓存:手机验证码的生成与校验

文章目录 1、缓存2、用HashMap模拟自定义缓存3、SpringBoot提供缓存的使用4、手机验证码案例完善 1、缓存 缓存是一种介于数据永久存储介质与数据应用之间的数据临时存储介质使用缓存可以有效的减少低速数据读取过程的次数&#xff08;例如磁盘IO&#xff09;&#xff0c;提高…

Shapiro-Francia正态检验

Shapiro-Francia检验是一种用于检验数据是否来自正态分布的统计方法。它是Shapiro-Wilk检验的一个变种&#xff0c;通常适用于小到中等样本大小的数据集。Shapiro-Francia检验的核心思想是通过计算统计量来评估数据的正态性。 Shapiro-Francia检验的零假设是数据来自正态分布&…

26 docker前后端部署

[参考博客]((257条消息) DockerNginx部署前后端分离项目(SpringBootVue)的详细教程_在docker中安装nginx实现前后端分离_这里是杨杨吖的博客-CSDN博客) (DockerNginx部署前后端分离项目(SpringBootVue)) 安装docker # 1、yum 包更新到最新 yum update # 2、安装需要的软件包…

JavaSE | 初识Java(七) | 数组 (下)

Java 中提供了 java.util.Arrays 包 , 其中包含了一些操作数组的常用方法 代码实例&#xff1a; import java.util.Arrays int[] arr {1,2,3,4,5,6}; String newArr Arrays.toString(arr); System.out.println(newArr); // 执行结果 [1, 2, 3, 4, 5, 6] 数组拷贝 代码实例…

cf 解题报告 01

E. Power of Points Problem - 1857E - Codeforces 题意&#xff1a; 给你 n n n 个点&#xff0c;其整数坐标为 x 1 , … x n x_1,\dots x_n x1​,…xn​&#xff0c;它们位于一条数线上。 对于某个整数 s s s&#xff0c;我们构建线段[ s , x 1 s,x_1 s,x1​], [ s , x…

C语言结构体指针学习

结构体变量存放内存中&#xff0c;也有起始地址&#xff0c;定义一个变量来存放这个地址&#xff0c;那这个变量就是结构体指针&#xff1b; typedef struct mydata{int a1;int a2;int a3; }mydata;void CJgtzzView::OnDraw(CDC* pDC) {CJgtzzDoc* pDoc GetDocument();ASSERT…

npm ,yarn 更换使用国内镜像源,淘宝源

背景 文章首发地址 在平时开发当中&#xff0c;我们经常会使用 Npm&#xff0c;yarn 来构建 web 项目。但是npm默认的源的服务器是在国外的&#xff0c;如果没有梯子的话。下载速度会特别慢。那有没有方法解决呢&#xff1f; 其实是有的&#xff0c;设置国内镜像即可&#x…

基于web的医院预约挂号系统/医院管理系统

摘 要 随着信息技术和网络技术的飞速发展&#xff0c;人类已进入全新信息化时代&#xff0c;传统管理技术已无法高效&#xff0c;便捷地管理信息。为了迎合时代需求&#xff0c;优化管理效率&#xff0c;各种各样的管理系统应运而生&#xff0c;各行各业相继进入信息管理时代&a…

如何解决版本不兼容Jar包冲突问题

如何解决版本不兼容Jar包冲突问题 引言 “老婆”和“妈妈”同时掉进水里&#xff0c;先救谁&#xff1f; 常言道&#xff1a;编码五分钟&#xff0c;解冲突两小时。作为Java开发来说&#xff0c;第一眼见到ClassNotFoundException、 NoSuchMethodException这些异常来说&…

八大排序(三)堆排序,计数排序,归并排序

一、堆排序 什么是堆排序&#xff1a;堆排序&#xff08;Heap Sort&#xff09;就是对直接选择排序的一种改进。此话怎讲呢&#xff1f;直接选择排序在待排序的n个数中进行n-1次比较选出最大或者最小的&#xff0c;但是在选出最大或者最小的数后&#xff0c;并没有对原来的序列…

k8s--storageClass自动创建PV

文章目录 一、storageClass自动创建PV1.1 安装NFS1.2 创建nfs storageClass1.3 测试自动创建pv 一、storageClass自动创建PV 这里使用NFS实现 1.1 安装NFS 安装nfs-server&#xff1a; sh nfs_install.sh /mnt/data03 10.60.41.0/24nfs_install.sh #!/bin/bash### How to i…

springboot 简单配置mongodb多数据源

准备工作&#xff1a; 本地mongodb一个创建两个数据库 student 和 student-two 所需jar包&#xff1a; # springboot基于的版本 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId>&l…

SSM - Springboot - MyBatis-Plus 全栈体系(十六)

第三章 MyBatis 三、MyBatis 多表映射 2. 对一映射 2.1 需求说明 根据 ID 查询订单&#xff0c;以及订单关联的用户的信息&#xff01; 2.2 OrderMapper 接口 public interface OrderMapper {Order selectOrderWithCustomer(Integer orderId); }2.3 OrderMapper.xml 配置…

一文拿捏基于redis的分布式锁、lua、分布式性能提升

1.分布式锁 jdk的锁&#xff1a; 1、显示锁&#xff1a;Lock 2、隐式锁&#xff1a;synchronized 使用jdk锁保证线程的安全性要求&#xff1a;要求多个线程必须运行在同一个jvm中 但现在的系统基本都是分布式部署的&#xff0c;一个应用会被部署到多台服务器上&#xff0c;s…

【系统架构】软件架构的演化和维护

导读&#xff1a;本文整理关于软件架构的演化和维护知识体系。完整和扎实的系统架构知识体系是作为架构设计的理论支撑&#xff0c;基于大量项目实践经验基础上&#xff0c;不断加深理论体系的理解&#xff0c;从而能够创造新解决系统相关问题。 目录 1、软件架构演化和定义 …

关掉在vscode使用copilot时的提示音

1. 按照图示的操作File --> Preferences --> Settings 2. 搜索框输入关键字Sound&#xff0c;因为是要关掉声音&#xff0c;所以找有关声音的设置 3. 找到如下图所示的选项 Audio Cues:Line Has Inline Suggetion,将其设置为Off 这样&#xff0c;就可以关掉suggest code时…
推荐文章