排序之插入排序----直接插入排序和希尔排序(1)

 个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

排序之插入排序----直接插入排序和希尔排序(1)

收录于专栏【数据结构初阶
本专栏旨在分享学习数据结构学习的一点学习笔记,欢迎大家在评论区交流讨论💌

目录

1.排序的概念及其运用

1.1排序的概念

1.2排序运用 

1.2.1 购物和电商

1.2.2 图书馆和书店

1.2.3 教育

1.2.4 交通和物流

1.2.5 餐饮业

1.3 常见的排序算法 

2.插入排序

2.1基本思想

2.2直接插入排序

2.2.1直接插入排序的概念:

2.2.2直接插入排序示例:

2.2.3动图演示:

 2.2.4代码实现:

2.2.5测试代码:

2.2.6时间复杂度分析

2.3希尔排序 ( 缩小增量排序 )

2.3.1希尔排序的概念

2.3.2希尔排序图解分析:

2.3.3代码展示:

 2.3.4测试代码:

2.3.5希尔排序时间复杂分析:

2.3.6 希尔排序的特性总结:

2.4希尔排序与直接插入排序的关系和比较 

3总结 


1.排序的概念及其运用

1.1排序的概念

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次 序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排 序算法是稳定的;否则称为不稳定的。

内部排序:数据元素全部放在内存中的排序。

外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不断地在内外存之间移动数据的排序。

1.2排序运用 

排序算法在生活中有着广泛的应用,无论是日常活动还是专业领域,都能看到排序算法的身影。以下是一些具体的例子:

1.2.1 购物和电商

  • 产品排列:在线购物平台会根据价格、销量、评价等对商品进行排序,方便用户查找和比较。
  • 推荐系统:根据用户的浏览和购买历史,推荐系统会对可能感兴趣的商品进行排序。

1.2.2 图书馆和书店

  • 分类与索引:图书按字母顺序、类别、作者或者出版日期排序,方便读者查找。
  • 借阅记录:按时间顺序记录借还书信息,便于管理和统计。

1.2.3 教育

  • 成绩排名:考试成绩会按照分数排序,以便评估学生的表现。
  • 学籍管理:按学号或姓名排序学生信息,便于查询和管理。

1.2.4 交通和物流

  • 航班和列车时刻表:按出发时间、目的地等排序,方便乘客查询和安排行程。
  • 快递分拣:按目的地、优先级等对包裹进行排序,提高运送效率。

1.2.5 餐饮业

  • 菜单排序:餐厅菜单按菜品类型、受欢迎程度等排序,方便顾客选择。
  • 订单处理:按下单时间、优先级等排序订单,确保及时准确地完成服务。

这些例子展示了排序算法在各种场景中的重要性和广泛应用,从而提高了效率和用户体验。无论是简单的字母排序还是复杂的多条件排序,排序算法在现代生活中都是不可或缺的工具。

1.3 常见的排序算法 

大家可以去下面链接查看各个排序算法的动态演示效果

--Comparison Sorting Visualization (usfca.edu) 

2.插入排序

2.1基本思想

直接插入排序是一种简单的插入排序法,其基本思想是: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。

实际中我们玩扑克牌时,就用了插入排序的思想

2.2直接插入排序

2.2.1直接插入排序的概念:

直接插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是逐步构建有序序列。具体操作如下:

  1. 初始状态:将序列分为两部分,一部分是有序序列,初始时只包含第一个元素;另一部分是无序序列,包含剩余的元素。

  2. 排序过程

    • 从第二个元素开始,依次将该元素插入到前面已经排好序的序列中的合适位置。
    • 假设当前要插入的元素为 current_value,将 current_value 与已排序序列中的元素从后向前逐个比较。
    • 如果发现已排序元素比 current_value 大,则将该元素后移一位,直到找到比 current_value 小的位置,或者到达序列的开头。
    • 将 current_value 插入到找到的位置后,此时已排序序列长度增加一。
  3. 重复:重复以上步骤,直到所有元素都插入到有序序列中。

  4. 结束:当所有元素都插入到有序序列后,排序完成。

2.2.2直接插入排序示例:

假设要对数组 [5, 2, 4, 6, 1, 3] 进行直接插入排序:

  1. 初始时,有序序列为 [5],无序序列为 [2, 4, 6, 1, 3]
  2. 将 2 插入到 [5] 中,得到 [2, 5],无序序列变为 [4, 6, 1, 3]
  3. 将 4 插入到 [2, 5] 中,得到 [2, 4, 5],无序序列变为 [6, 1, 3]
  4. 依此类推,直到所有元素都插入到有序序列中,最终得到排序后的数组 [1, 2, 3, 4, 5, 6]

直接插入排序虽然简单,但在某些特定情况下仍然可以提供不错的性能,特别是在处理部分有序的数据或者数据量较小时。

2.2.3动图演示:

 2.2.4代码实现:

void InsertSort(int* a, int n)
{//  [0, n-1]for (int i = 0; i < n - 1; i++){// [0, n-2]是最后一组// [0,end]有序 end+1位置的值插入[0,end],保持有序int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}

分析:

  1. 外层循环(i 循环)

    • for (int i = 0; i < n - 1; i++) 循环遍历数组,从第一个元素到倒数第二个元素。每次迭代开始时,数组从 a[0] 到 a[i] 是已经排好序的部分。
  2. 内层循环(end 循环)

    • int end = i; 将当前元素 a[i+1] 视为待插入的元素。
    • int tmp = a[end + 1]; 记录待插入元素的值。
  3. 插入过程

    • while (end >= 0) 内层循环用于找到待插入元素 tmp 的正确位置。
    • if (tmp < a[end]) 如果待插入元素比当前位置 a[end] 的元素小,则将 a[end] 向后移动一位,即 a[end + 1] = a[end];,同时 end-- 继续向前比较。
    • 当找到合适的位置(即 tmp >= a[end]),退出内层循环。
  4. 插入操作

    • a[end + 1] = tmp; 将 tmp 插入到找到的合适位置 end + 1 处,此时数组从 a[0] 到 a[i+1] 又变成有序状态。

 注意:我们的外层循环for (int i = 0; i < n - 1; i++) 是遍历的是我们已经排好序的数组,我们需要排的数为a[end+1],也就是a[i+1],所以这里i<n-1,不能等于n-1

2.2.5测试代码:

测试链接:912. 排序数组 - 力扣(LeetCode)

题目描述:

给你一个整数数组 nums,请你将该数组升序排列。

示例 1:

输入:nums = [5,2,3,1]
输出:[1,2,3,5]

示例 2:

输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

提示:

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

代码展示:

void InsertSort(int* a, int n)
{for(int 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;}
}int* sortArray(int* nums, int numsSize, int* returnSize) {(*returnSize) = numsSize;int* array = (int*)malloc(sizeof(int)*(*returnSize));for(int i = 0; i < numsSize; i++){array[i] = nums[i];}InsertSort(array, numsSize);return array;
}

2.2.6时间复杂度分析

 插入排序可以说是排序的最底层,它最好的情况是有序,时间复杂度为O(n),很显然这种情况很少见,最坏的情况是逆序,时间复杂度为O(n^2).在平均情况下,直接插入排序的时间复杂度也是 O(n^2)。虽然有时候可能会比较少于最坏情况下的比较次数,但是对于大规模的随机数组,其平均时间复杂度仍然是二次阶的。

在力扣这道题目中只通过了12个例子就超时了.....

 

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

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

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

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

4. 稳定性:稳定

2.3希尔排序 ( 缩小增量排序 )

2.3.1希尔排序的概念

希尔排序(Shell Sort)是一种改进的插入排序算法,也称作缩小增量排序。希尔排序通过将原始序列分割成若干个子序列来改善插入排序的性能,每个子序列分别进行插入排序,最后再对整体进行一次插入排序。其基本思想可以描述如下:

  1. 步骤

    • 选择一个增量序列,通常是使用 Knuth 序列(例如 ( n / 2, n / 4, ..., 1 ))或者 Hibbard 序列(( 2^k - 1 ))来作为增量。
    • 根据选定的增量序列,将待排序的序列分割成若干个子序列。
    • 对每个子序列分别进行插入排序。
    • 逐渐缩小增量,重复以上步骤,直到增量为 1。
  2. 排序过程

    • 假设待排序数组为 [5, 2, 4, 6, 1, 3]
    • 如果选取增量序列为 ( n / 2, n / 4, ..., 1 ),则初始增量 ( n / 2 = 3 )。
    • 分别对 [5, 6][2, 1][4, 3] 这三个子序列进行插入排序。
    • 第一次插入排序后,可能得到 [1, 2, 3, 5, 4, 6]
    • 接下来使用更小的增量进行插入排序,直到最终使用增量为 1 的插入排序完成整体排序。

2.3.2希尔排序图解分析:

 

2.3.3代码展示:

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){// +1保证最后一个gap一定是1// gap > 1时是预排序// gap == 1时是插入排序gap = gap / 3 + 1;for (size_t i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

代码逻辑:

  1. 初始设置 gap

    • 初始时,将 gap 设置为数组长度 n。在每一轮迭代中,通过 gap = gap / 3 + 1 逐渐减小 gap 的值,直到最后一次迭代时 gap 等于 1,变成普通的插入排序。
  2. 主循环(while 循环):

    • 当 gap 大于 1 时,进行希尔排序的预处理阶段,即根据当前的 gap 进行分组预排序。
    • 当 gap 等于 1 时,执行最后一轮,此时相当于执行普通的插入排序。
  3. 预排序阶段

    • 对于每个 gap 值,通过一个 for 循环遍历数组,对每个分组进行插入排序。这里的 for (size_t i = 0; i < n - gap; ++i) 控制每个分组的起始位置。
  4. 插入排序

    • 对于当前的分组起始位置 i,使用插入排序的方式将该分组内的元素排序。
    • 内部的 while 循环用于找到合适的插入位置,确保当前位置的元素插入到正确的位置。
  5. 交换和移动

    • 如果当前位置的元素比 tmp(待插入元素)大,则将当前位置的元素向后移动 gap 个位置,直到找到合适的插入位置。
    • 插入位置确定后,将 tmp 插入到该位置。
  6. 最终结果

    • 经过多次循环和逐步缩小的 gap 值处理后,数组 a 将被排序完成。

 2.3.4测试代码:

 测试链接:912. 排序数组 - 力扣(LeetCode)

代码展示:

void ShellSort(int* a, int n)
{int gap = n;while(gap > 1){gap = gap/3 + 1;for(int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while(end >= 0){if(tmp < a[end]){a[end + gap] = a[end];end-=gap;}else{break;}}a[end + gap] = tmp;}}
}int* sortArray(int* nums, int numsSize, int* returnSize) {(*returnSize) = numsSize;int* array = (int*)malloc(sizeof(int)*(*returnSize));for(int i = 0; i < numsSize; i++){array[i] = nums[i];}ShellSort(array, numsSize);return array;
}

结果展示:

居然过了!!!!!!!!!!

 

希尔排序虽然有点难理解,看起来很复杂,但是它的效率真的很高.

2.3.5希尔排序时间复杂分析:

 有关希尔排序的时间复杂度至今都没有定论.

《数据结构(C语言版)》--- 严蔚敏

《数据结构-用面相对象方法与C++描述》--- 殷人昆 

因为我的gap是按照Knuth提出的方式取值的,而且Knuth进行了大量的试验统计,我们暂时就按照:O(n^1.3)来算

那为什么希尔排序的时间复杂难算呢?

第一次预排序 gap = n/3(这里我们将-1省略方便计算),一组有3个数据(n=10),最坏的情况需要排3次,也就是3*3/n=n,也就是说,希尔第一次预排序接近于O(n)

最后一次排序:数组接近有序,可以看成O(n)

第二次预排序:gap=n/9,每组九个数据,最坏的情况(1+2.....+8)*n/9=4n

注意:这里我们第二次预排序取得是最坏的情况,而经过我们第一次得预排序,我们第二次往往不会是最坏的情况,希尔排序难就难在除第一次和最后一次,其他情况是变化的

2.3.6 希尔排序的特性总结:

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

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

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

2.4希尔排序与直接插入排序的关系和比较 

关系与比较:

  1. 基础原理: 希尔排序可以看作是对直接插入排序的改进,通过预处理数据,使其更接近最终排序后的位置,从而减少了直接插入排序中的元素比较和移动次数。

  2. 性能比较: 在数据量较小时,直接插入排序可能会比希尔排序更快,因为希尔排序的预处理阶段可能带来一定的额外开销。但是在大规模数据和随机数据排序时,希尔排序通常能够明显优于直接插入排序。

  3. 稳定性: 直接插入排序是稳定的,而希尔排序一般来说是不稳定的,这是因为希尔排序涉及多个子序列的插入排序,子序列之间的相对顺序可能发生变化。

综上所述,希尔排序和直接插入排序虽然在实现上有所区别,但它们的基本思想都是通过逐步将元素移动到正确位置来完成排序,希尔排序通过增量序列的方式优化了插入排序的性能,特别是在处理大规模数据时表现更为优越。

3总结 

直接插入排序和希尔排序虽然在我们排序中使用较少,但它们具有可使用性,尤其是希尔排序(从它AC力扣的数组排序就可以看出)

我马上会更选择排序--(选择排序和推排序)

宝子们记得点赞关注支持一下

我将会在数据结构初阶这个专栏持续更新

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

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

相关文章

算法训练营day20--235. 二叉搜索树的最近公共祖先+701.二叉搜索树中的插入操作 +450.删除二叉搜索树中的节点

一、235. 二叉搜索树的最近公共祖先 题目链接&#xff1a;https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/ 文章讲解&#xff1a;https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91…

天马学航——智慧教务系统(移动端)开发日志三

天马学航——智慧教务系统(移动端)开发日志三 日志摘要&#xff1a;更新了学生选课模块、我的课程模块以及退课的功能&#xff0c;优化了后端数据库的缓存 1、学生选课模块 学生选课模块主要实现&#xff0c;学生根据需求进行选课操作&#xff0c;通过后端查询到所有教师的课…

一份简单的海外问卷,改变经济现状

在许多人看来&#xff0c;赚钱似乎总是与资金和技术密切相关。然而&#xff0c;即使没有丰富的资金和高超的技术&#xff0c;仍然有机会赚取可观的收入。 首先&#xff0c;需要明确的是&#xff0c;赚钱并非完全依赖于物质资本和技术能力。在这个充满机遇的时代&#xff0c;选…

深入源码设计!Vue3.js核心API——Computed实现原理

如果您觉得这篇文章有帮助的话&#xff01;给个点赞和评论支持下吧&#xff0c;感谢~ 作者&#xff1a;前端小王hs 阿里云社区博客专家/清华大学出版社签约作者/csdn百万访问前端博主/B站千粉前端up主 此篇文章是博主于2022年学习《Vue.js设计与实现》时的笔记整理而来 书籍&a…

谷歌云(GCP)4门1453元最热门证书限时免费考

谷歌云(GCP)最新活动&#xff0c;完成免费官方课程&#xff0c;送4门最热门考试免费考试券1张(每张价值200刀/1453元)&#xff0c;这4门也包括最近大热的AI/ML考试&#xff0c;非常值得学习和参加&#xff0c;活动7/17截止 谷歌云是全球最火的三大云计算厂商(前两名AWS, Azure…

投票多功能小程序(ThinkPHP+Uniapp+FastAdmin)

&#x1f389;你的决策小助手&#xff01; 支持图文投票、自定义选手报名内容、自定义主题色、礼物功能(高级授权)、弹幕功能(高级授权)、会员发布、支持数据库私有化部署&#xff0c;Uniapp提供全部无加密源码。​ 一、引言&#xff1a;为什么我们需要多功能投票小程序&#…

NSSCTF中的[WUSTCTF 2020]朴实无华、[FSCTF 2023]源码!启动! 、[LitCTF 2023]Flag点击就送! 以及相关知识点

目录 [WUSTCTF 2020]朴实无华 [FSCTF 2023]源码&#xff01;启动! [LitCTF 2023]Flag点击就送&#xff01; 相关知识点 1.intval 绕过 绕过的方式&#xff1a; 2.session伪造攻击 [WUSTCTF 2020]朴实无华 1.进入页面几乎没什么可用的信息&#xff0c;所以想到使用dis…

【c语言】二级指针

1&#xff0c;定义 本质还是从指针的角度去理解&#xff0c;只不过存的指针的值 2&#xff0c;使用方法

Android使用DevRing框架搭建数据库实体类以及使用

一、引用DevRing依赖 //导入DevRing依赖implementation com.ljy.ring:devring:1.1.8创建数据库表的依赖implementation org.greenrobot:greendao:3.2.2 // add libraryimplementation org.greenrobot:greendao-generator:3.0.0 二、修改工程目录下的.idea->gradle.xml文件&…

Golang笔记:使用serial包进行串口通讯

文章目录 目的使用入门总结 目的 串口是非常常用的一种电脑与设备交互的接口。这篇文章将介绍golang中相关功能的使用。 本文使用的包为 &#xff1a;go.bug.st/serial https://pkg.go.dev/go.bug.st/serial https://github.com/bugst/go-serial 另外还有一些常见的包如&…

Springboot民宿信息管理系统-计算机毕业设计源码08818

摘 要 信息化社会内需要与之针对性的信息获取途径&#xff0c;但是途径的扩展基本上为人们所努力的方向&#xff0c;由于站在的角度存在偏差&#xff0c;人们经常能够获得不同类型信息&#xff0c;这也是技术最为难以攻克的课题。针对民宿信息管理系统等问题&#xff0c;对民宿…

大模型应用研发基础环境配置(Miniconda、Python、Jupyter Lab、Ollama等)

老牛同学之前使用的MacBook Pro电脑配置有点旧&#xff08;2015 年生产&#xff09;&#xff0c;跑大模型感觉有点吃力&#xff0c;操作起来有点卡顿&#xff0c;因此不得已捡起了尘封了快两年的MateBook Pro电脑&#xff08;老牛同学其实不太喜欢用 Windows 电脑做研发工作&am…

Ant Design Vue Cascader 级联选择 错位问题

当Cascader 多个的时候 对应的下列会错位 如果滚动 他不会跟着元素 而是会跟着屏幕滚动&#xff0c;如下效果 解决方法 在Cascader 标题添加 getPopupContainer 属性监听对应的位置&#xff0c;返回对应的元素 <a-cascader class"smart-width-100 " v-model:…

Sam Altman:从少儿奇才到OpenAI掌舵人

自2022年底发布了ChatGPT以来&#xff0c;OpenAI及其首席执行官Sam Altman迅速成为科技界的焦点人物。Altman的崛起并非偶然&#xff0c;而是长期以来不断追求权力和创新的结果。本文将回顾Altman的成长历程&#xff0c;探索他如何一步步走向OpenAI的顶峰。 童年与教育背景 S…

亚马逊云科技官方活动:一个月拿下助理架构师SAA+云从业者考试认证(送半价折扣券)

为了帮助大家考取AWS SAA和AWS云从业者认证&#xff0c;小李哥争取到了大量考试半价50%折扣券&#xff0c;使用折扣券考试最多可省75刀(545元人民币)。 领取折扣券需要加入云师兄必过班群&#xff0c;在群中免费领取。目前必过班群招募到了超过200名小伙伴&#xff0c;名额有限…

YOLOv8关键点pose训练自己的数据集

这里写自定义目录标题 YOLOv8关键点pose训练自己的数据集一、项目代码下载二、制作自己的关键点pose数据集2.1 标注(非常重要)2.1.1 标注软件2.1.2 标注注意事项a.多类别检测框b.单类别检测框2.2 格式转换(非常重要)2.3 数据集划分三、YOLOv8-pose训练关键点数据集3.1 训练…

任务3.8.4 利用RDD实现分组排行榜

文章目录 1. 任务说明2. 解决思路3. 准备成绩文件4. 采用交互式实现5. 采用Spark项目实战概述&#xff1a;使用Spark RDD实现分组排行榜任务背景任务目标技术选型实现步骤1. 准备数据2. 数据上传至HDFS3. 启动Spark Shell4. 读取数据生成RDD5. 数据处理6. 计算TopN7. 输出结果8…

Instagram 算法更新?想要吸引更多新用户请打开这些设置!

为什么你发的IG就没人看&#xff1f;没流量&#xff1f;注意了&#xff01;IG算法已更新&#xff0c;了解最新算法、学会这些设置&#xff0c;你的IG自然能吸引到越来越多用户关注&#xff01; Instagram 算法更新 1️⃣ 根据Instagram官方的表述&#xff0c;他们对算法进行了调…

分享一个好用的图幅号计算器

如果在你的工作中会分幅处理地图数据&#xff0c;也许这个好用的图幅号计算器能对你有所帮助。 你只需要在该工具中输入经纬度坐标&#xff0c;就可以为你计算出各个比例尺下的图幅号&#xff0c;你可以在文末查看该工具的领取方法。 一个好用的图幅号计算器 该图幅计算器工…

Redis的持久化方式和注意点

redis持久篇 两种持久化技术&#xff1a; AOF日志和RDB快照 Redis默认会开启RBD快照 AOF:持久化只会记录写操作命令。 是一种日志&#xff0c;写入到文件&#xff0c;有相应的格式文本 就是 Redis 里的AOF(Append Only File)持久化功能&#xff0c;注意只会记录写操作命令…