当前位置: 首页 > news >正文

【数据结构】排序--插入排序(希尔排序)

目录

一 基本思想

二 直接插入排序

三 希尔排序


一 基本思想

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为 止,得到一个新的有序序列 。 实际中我们玩扑克牌时,就用了插入排序的思想

二 直接插入排序

当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移

直接插入排序的特性总结:

1. 元素集合越接近有序,直接插入排序算法的时间效率越高

2. 时间复杂度:O(N ^ 2)

3. 空间复杂度:O(1),它是一种稳定的排序算法

4. 稳定性:稳定

#include<stdio.h>
void InsertSort(int* a, int n)
{int i = 0;for (i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;//因为前面end--了 所以这里是a[end+1]}
}
int main()
{int arr[] = { 1, 3, 2, 5, 4, 7, 9 };InsertSort(arr, sizeof(arr) / sizeof(int));//排升序for (int i = 0; i < sizeof(arr) / sizeof(int); i++){printf("%d ", arr[i]);}
}

 三 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个n 组,所有距离为gap的记录分在同一组内,并对每一组内的记录进行排序。然后,取重复上述分组和排序的工作。当到达gap == 1时,所有记录在统一组内排好序。

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//gap /= 2;gap = gap / 3 + 1;//这样可以更快//直接插入排序思想for (int i = 0; i < n- gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}int main()
{int arr[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5};//InsertSort(arr, sizeof(arr) / sizeof(int));//排升序InsertSort(arr, sizeof(arr) / sizeof(int));//排升序for (int i = 0; i < sizeof(arr) / sizeof(int); i++){printf("%d ", arr[i]);}
}

 

希尔排序的特性总结:

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就 会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的 希尔排序的时间复杂度都不固定 

4. 稳定性:不稳定

本节的重难点是希尔排序, 希尔排序实际上就是直接插入排序的优化, 只要理解了直接插入排序, 希尔排序就不难了.大家可以根据图解和代码进行实操.

继续加油!

相关文章:

【数据结构】排序--插入排序(希尔排序)

目录 一 基本思想 二 直接插入排序 三 希尔排序 一 基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中&#xff0c;直到所有的记录插入完为 止&#xff0c;得到一个新的有序序列 。 实际中我们玩扑克牌时&#xff0c;就用了插入排序的思想 二…...

“探寻服务器的无限潜能:从创意项目到在线社区,你会做什么?”

文章目录 每日一句正能量前言什么是服务器&#xff1f;服务器能做什么&#xff1f;服务器怎么用&#xff1f;部署创意项目&#xff0c;还是在线社区亦或做其他的&#xff1f;后记 每日一句正能量 未知的下一秒&#xff0c;千万不要轻言放弃。 前言 在数字化时代&#xff0c;服…...

5年经验之谈 —— 深入了解性能测试:方法、工具和最佳实践!

性能测试是软件开发生命周期中至关重要的一部分&#xff0c;它有助于确保应用程序在不同负载条件下都能够高效运行。在竞争激烈的市场中&#xff0c;性能问题可能导致用户流失&#xff0c;损害声誉&#xff0c;并损害业务。本文将深入探讨性能测试的方法、工具和最佳实践&#…...

动态加载sprite是multiple模式(即该sprite包含了很多小图)里的小图

在Unity中&#xff0c;Resources.Load()方法可以用来加载资源。如果要加载Sprite下的multiple模式的图片&#xff0c;你需要知道这些图片的路径。 首先&#xff0c;你需要把你想要加载的资源放在一个名为"Resources"的文件夹内。然后&#xff0c;你可以使用以下代码…...

大数据 DataX 详细安装教程

目录 一、环境准备 二、安装部署 2.1 二进制安装 2.2 python 3 支持 三、Data X 初体验 3.1 配置示例 3.1.1. 生成配置模板 3.1.2 创建配置文件 3.1.3 运行 DataX 3.1.4 结果显示 3.2 动态传参 3.2.1. 动态传参的介绍 3.2.2. 动态传参的案例 3.3 迸发设置 …...

微信小程序开发之会议oa(首页搭建)

前言&#xff1a; 上一篇我们掌握了关于小程序的框架&#xff0c;这篇博客带你完成小程序版的会议OA首页。效果如下&#xff1a; 一&#xff0c; 1.1先创建OA首页页面&#xff1a; 首先我们先建一个新项目&#xff0c;在app.json中编写代码 {"pages": ["pages/…...

了解主启动类怎么运行

//SpringBootApplication 标注这个类是spring boot的应用&#xff0c;启动类下的所有资源都会被导入 SpringBootApplication public class SpringbootApplication { public static void main(String[] args) { //以为是启动了一个方法&#xff0c;没想到启动了一个服务 SpringA…...

【LeetCode】31. 下一个排列

1 问题 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如&#xff0c;arr [1,2,3] &#xff0c;以下这些都可以视作 arr 的排列&#xff1a;[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地&a…...

支持语音与视频即时通讯项目杂记(一)

第一部分解释服务端的实现。 &#xff08;服务端结构&#xff09; 下面一个用于实现TCP服务器的代码&#xff0c;包括消息服务器&#xff08;TcpMsgServer&#xff09;和文件中转服务器&#xff08;TcpFileServer&#xff09;。 首先&#xff0c;TcpServer是TcpMsgServer和Tcp…...

文档:htm格式转txt

꧂ 两个地方都保存꧁ import os import codecs from bs4 import BeautifulSoupdef generate_output_filename(file_path, save_path):# 获取文件名&#xff08;不包含扩展名&#xff09;file_name os.path.splitext(os.path.basename(file_path))[0]# 构造保存路径和文件名ou…...

电子邮件地址注册过程详解

许多人可能对如何注册电子邮件地址感到困惑&#xff0c;本文将详细解析电子邮件地址的注册过程&#xff1a;确定邮箱厂商、创建邮箱账户、设置电子邮件地址。 1、确定要注册的邮箱厂商 首先我们需要确定要注册哪种类型的电子邮件服务。目前市场上有许多不同的电子邮件服务提供商…...

深度学习——卷积神经网络(CNN)基础二

深度学习——卷积神经网络&#xff08;CNN&#xff09;基础二 文章目录 前言三、填充和步幅3.1. 填充3.2. 步幅3.3. 小结 四、多输入多输出通道4.1. 多输入通道4.2. 多输出通道4.3. 11卷积层4.4. 小结 总结 前言 上文对卷积有了初步的认识&#xff0c;其实卷积操作就是通过卷积…...

R语言进度条:txtProgressBar功能使用方法

R语言进度条使用攻略 在数据处理、建模或其他计算密集型任务中&#xff0c;我们常常会执行一些可能需要很长时间的操作。 在这些情况下&#xff0c;展示一个进度条可以帮助我们了解当前任务的进度&#xff0c;以及大约还需要多长时间来完成&#xff0c;R语言提供了几种简单且灵…...

Maven实战-声明周期和插件

Maven实战-声明周期和插件 Maven 设计了插件机制&#xff0c;每个构建步骤都可以绑定一个或者多个插件行为&#xff0c;而且 Maven 为大多数构建步骤编写 并绑定了默认插件。例如&#xff0c;针对编译的插件有 maven-compiler-plugin&#xff0c;针对测试的插件有 maven-sure…...

ebpf的快速开发工具--libbpf-bootstrap

基于ubuntu22.04-深入浅出 eBPF 基于ebpf的性能工具-bpftrace 基于ebpf的性能工具-bpftrace脚本语法 基于ebpf的性能工具-bpftrace实战(内存泄漏) 什么是libbpf-bootstrap libbpf-bootstrap是一个开源项目&#xff0c;旨在帮助开发者快速启动和开发使用eBPF(Extended Berk…...

万界星空科技/生产制造执行MES系统/开源MES/免费MES

开源系统概述&#xff1a; 万界星空科技免费MES、开源MES、商业开源MES、市面上最好的开源MES、MES源代码、免费MES、免费智能制造系统、免费排产系统、免费排班系统、免费质检系统、免费生产计划系统、免费数字化大屏。 万界星空开源MES制造执行系统的Java开源版本。开源mes…...

螺纹快速接头在卫浴行业中的应用提高产量降低生产成本

螺纹快速接头在卫浴行业主要用于上下水测试和密封性测试&#xff0c;可以快速密封连接待测产品和水管。取代之前的工人手拧编织管六角螺母的方式&#xff0c;方便快捷&#xff0c;密封性好&#xff0c;产品测试更稳定。 卫浴行业产品必须具备很好的密封性&#xff0c;防止在实际…...

通达OA 2016网络智能办公系统 handle.php SQL注入漏洞

一、漏洞描述 北京通达信科科技有限公司通达OA2016网络智能办公系统 handle.php 存在sql注入漏洞&#xff0c;攻击者可利用此漏洞获取数据库管理员权限&#xff0c;查询数据、获取系统信息&#xff0c;威胁企业单位数据安全。 二、网络空间搜索引擎查询 fofa查询 app"T…...

parameter的各种用法以及localparam的用法

parameter的各种用法以及localparam的用法 一、这种写法放在v文件或者是用来调用其他的ram文件都是正确的。 一、这种写法放在v文件或者是用来调用其他的ram文件都是正确的。 module para_local();parameter a 10; // 第一种用法 parameter a 4d10; // 第二种用法 para…...

网络社区挖掘-图论部分的基本知识笔记

1 网络社区挖掘定义 网络社区挖掘是指利用数据挖掘技术和机器学习算法&#xff0c;分析社交网络、在线社区或互联网上的各种交互数据&#xff0c;以揭示其中隐藏的模式、关系和信息。这些社区可以是社交媒体平台、在线论坛、博客、微博等&#xff0c;人们在这些平台上进行交流…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!

目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...

加密通信 + 行为分析:运营商行业安全防御体系重构

在数字经济蓬勃发展的时代&#xff0c;运营商作为信息通信网络的核心枢纽&#xff0c;承载着海量用户数据与关键业务传输&#xff0c;其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级&#xff0c;传统安全防护体系逐渐暴露出局限性&a…...

数据库正常,但后端收不到数据原因及解决

从代码和日志来看&#xff0c;后端SQL查询确实返回了数据&#xff0c;但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离&#xff0c;并且ai辅助开发的时候&#xff0c;很容易出现前后端变量名不一致情况&#xff0c;还不报错&#xff0c;只是单…...

大数据驱动企业决策智能化的路径与实践

&#x1f4dd;个人主页&#x1f339;&#xff1a;慌ZHANG-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、引言&#xff1a;数据驱动的企业竞争力重构 在这个瞬息万变的商业时代&#xff0c;“快者胜”的竞争逻辑愈发明显。企业如何在复杂环…...