【排序算法】插入排序与希尔排序,你不想知道为什么希尔比插入更快吗?

这篇具有很好参考价值的文章主要介绍了【排序算法】插入排序与希尔排序,你不想知道为什么希尔比插入更快吗?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【排序算法】插入排序与希尔排序,你不想知道为什么希尔比插入更快吗?,算法与数据结构,排序算法,算法,数据结构

🚀前言

大家好啊!本文阿辉讲介绍插入排序和希尔排序,并将解释为什么希尔排序比插入排序更快。

🚀插入排序(insertsort)

✈️原理

插入排序,实际上是我们平时都使用过的排序,为什么这么说呢😆?想必大家都玩过扑克牌吧,大家是如何整理手中的牌的呢?一定是想下面这样对吧👇
【排序算法】插入排序与希尔排序,你不想知道为什么希尔比插入更快吗?,算法与数据结构,排序算法,算法,数据结构

没错,插入排序也是的么实现的

其实关于插入排序,一句话足以概括:对于要排序的数据,从前往后遍历所有数据,遍历到的数据与之前的数据进行比较,以升序为例,若遍历位置的数据比前一个数据小两者就交换,然后接着与前一个位置比较如果还小就继续交换,直到比前一个数据大就停止交换
给铁子们上动图😘
【排序算法】插入排序与希尔排序,你不想知道为什么希尔比插入更快吗?,算法与数据结构,排序算法,算法,数据结构

✈️代码实现(coding)

对于插入排序,我们需要两个循环来控制,一个循环来遍历所有数据,另  一个循环用来遍历已排好序的部分与要插入数据比较

coding

void insertsort(int arr[],int sz){
    int insert = 0;//遍历要插入的位置
    for(insert = 1;insert < sz;insert++){
        int cur = insert;//记录待排序的位置
        int pre = cur - 1;//记录待排序的前一个位置
        while(arr[cur] < arr[pre] && cur > 0){//没前一个位置大就交换,待排序位置来到0位置就退出循环
            int tmp = arr[cur];
            arr[cur] = arr[pre];
            arr[pre] = tmp;
            --cur,--pre;//待排序位置和前一个位置同时--
        }
    }
}

🚀总结

稳定性的定义

说到稳定性,与之对应就是不稳定性,那么排序算法的稳定性又为何意呢?通俗地讲就是,能保证排序前两个相等的数其在序列的前后位置顺序与排序后它们的前后位置顺序一致。形式化解释如下:一列数中,如果Ai = Aj,Ai位于Aj的前置位,那么经过升降序排序后Ai仍然位于Aj的前置位

阿辉之前介绍的 冒泡和选择排序和今天的插入排序,到现在排序中三个最挫的排序已经介绍完了,这三个的时间复杂度都是O(n2),选择排序是最挫的,冒泡和插入排序都可以做到有稳定性而选择排序做不到

为什么选择排序不行,一个简单的例子就能解释
比如一串数字 83482,一趟选择下来,第一个8与2交换,这样第一个8和第二个8之间的稳定性就被打破了

🚀希尔排序(shellsort)

希尔排序(Shell Sort)是一种基于插入排序的排序算法,也被称为“缩小增量排序”(Diminishing Increment Sort)。它通过将整个列表分割成多个较小的子序列,并对这些子序列进行插入排序,从而逐步减少排序的范围,最终完成整个列表的排序。希尔排序在提供了一种平衡了性能和简单性的排序方法。

好吧上面百度粘的说得不是人话

其实希尔排序就是将数据分组,在每个组内进行插入排序(对就是直接进行插入排序),那么如何分组呢?设置一个增量序列,开始的增量通常是数组长度的一半,然后下一次增量减半,增量设为gap,给铁子们上图
【排序算法】插入排序与希尔排序,你不想知道为什么希尔比插入更快吗?,算法与数据结构,排序算法,算法,数据结构

✈️代码实现(coding)

void shellsort(int arr[],int sz){
    for(int gap = sz/2;gap > 0;gap /= 2){
        for(int i = gap;i < n;++i){//i从每组的第二个数遍历,因为每组的第一个数不用进行插入排序
            int k = arr[i];//记录当前进行插入排序的数据
            for(int j = i;j >= gap && k < arr[j - gap];j -= gap)//如果待插入的数据比前一个数据小就将前一个数移到待排序的位置,接着与下一个位置比较
                arr[j] = arr[j-gap];
            arr[j] = k;//最后将要插入的数据插到合适的位置
        }
    }
}

希尔排序没有稳定性,是阿辉介绍的第一个时间复杂度突破O(n2)的排序,时间复杂度在O(nlogn)~O(n2)之间,有同学可能会问为啥仅仅分了各组就让希尔排序更快了,问的好重点来了

✈️为啥希尔排序能比插入排序更快

其实一个列子就能让你明白,比如下列这个数组:
【排序算法】插入排序与希尔排序,你不想知道为什么希尔比插入更快吗?,算法与数据结构,排序算法,算法,数据结构

对于最后的1插入排序需要交换5次才能来到正确的位置
而如果使用希尔排序,对于第一个增量31将与8一组,一次交换就让1跨过了3和4下标的位置,从而少了2次交换,所以希尔排序比插入排序更快,它降低了交换的次数


其实,阿辉介绍的这些比较挫的排序,之所以挫就是因为它们大量浪费了交换,后续阿辉介绍的时间复杂度在O(nlogn)的排序都减少了交换的次数
【排序算法】插入排序与希尔排序,你不想知道为什么希尔比插入更快吗?,算法与数据结构,排序算法,算法,数据结构文章来源地址https://www.toymoban.com/news/detail-787666.html

到了这里,关于【排序算法】插入排序与希尔排序,你不想知道为什么希尔比插入更快吗?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 八大排序算法之插入排序+希尔排序

    目录 一.前言(总体简介) 关于插入排序  关于希尔排序: 二.插入排序 函数首部: 算法思路: 算法分析 插入排序代码实现: 插入排序算法的优化前奏:  三.希尔排序(缩小增量排序) 1.算法思想:  2.算法拆分解析  序列分组 分组预排序: 分组预排序的另一种实现方式: 希尔排序的实现

    2023年04月09日
    浏览(45)
  • 数据结与算法之排序-插入排序(直接插入/折半插入/希尔)

    文章目录 目录 前言 一、什么是插入排序 1.直接插入排序 2.折半插入排序          3.希尔排序 总结 理解三种排序,并将三种排序用C++实现,借鉴了王卓老师和没有难学的知识的图例 提示:以下是本篇文章正文内容,下面案例可供参考         插入排序是简单直观的排序方

    2024年02月04日
    浏览(42)
  • 十大排序算法之插入排序、希尔排序、选择排序

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【数据结构初阶(C实现)】 本篇主要讲解八大排序算法中的三种排序,分别是: 插入排序、希尔排序、选择排序 。 在我们的日常生活最常见的一个场景就是斗地主,

    2023年04月16日
    浏览(37)
  • 【数据结构】常见排序算法——常见排序介绍、插入排序、直接插入排序、希尔排序

      在计算机科学中,排序是将一组数据按照指定的顺序排列的过程。排序算法由于执行效率的不同可以分为多种不同的算法。   通常情况下,排序算法可以分为两类,即 内部排序和外部排序 。内部排序是指数据全部加载到内存中进行排序,适用于数据量较小的情况,而

    2024年02月08日
    浏览(63)
  • 数据结构与算法:插入排序&希尔排序

    假设现在你有一个有序的数组,你要把一个数据插入到数组中,保证插入后依然有序,要怎么做? 对于人来说,这个问题就像是在整理扑克牌,瞄一眼就知道应该插入什么位置。但是对于程序来说,就需要一一对比,直到找到一个位置 左边比它大,右边比它小 ,就算找到了

    2024年01月17日
    浏览(58)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(86)
  • 【数据结构与算法】:插入排序与希尔排序

    🔥 个人主页 : Quitecoder 🔥 专栏 : 数据结构与算法 欢迎大家来到初阶数据结构的最后一小节:排序 排序是一种将一组对象按照某种特定顺序重新排列的过程。在计算机科学中,排序是数据处理中非常基本且重要的操作,它可以帮助人们更有效地理解和分析数据。排序的顺序

    2024年03月18日
    浏览(39)
  • 【数据结构与算法】插入排序和希尔排序

      目录 一.插入排序  InsertSort 基本思想 动图演示  特性总结 二.希尔排序  ShellSort 基本思想 图例 特性总结 基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。 当插入第i(i=1)个元素

    2023年04月18日
    浏览(89)
  • 【数据结构与算法】直接插入排序和希尔排序

    进入了初阶数据结构的一个新的主题——排序。所谓排序,就是一串记录, 按照其中的某几个或某些的大小(一定的规则) , 递增或递减排列起来的操作 。 排序的 稳定性 :在一定的规则下,两个值相等的元素,在排序算法处理前后的相对位置是否发生变化,如果相

    2024年04月13日
    浏览(44)
  • 十大排序算法(上)直接插入排序、希尔排序、直接选择排序、堆排序

    排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假设在待排序的序列中,存在多个具有相同内容的元素,如果经过排序,这些元素的相对位置并不发生改变,则称这种排序算法是稳定的。 稳定的排序可以变成不稳定的

    2024年02月05日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包