排序之直接插入排序

前言

本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中都有详细讲解,而我写这些博客只是记录自己学习过程,加入了一些自己的理解,同时也希望给别人提供帮助。

前提故事

  相信大家都玩过扑克,特别是斗地主;从你摸完第一张牌开始,之后的每摸的一张牌都需要与手中已有的牌进行比较,来确定这张牌放的位置,不管你们是否有这个习惯,我是有这个习惯的,就是从左到右,牌是从小到大的;这个摸牌的过程其实就是直接插入排序的一个过程;这时候有人就说了:我摸牌都不看牌的,等摸完了,再去整理牌,其实你这是找抽的节奏呀,别人都叫地主了,你还在整理牌!你说你是不是找抽。

  开个玩笑,闲话不多扯,进入下面的正题。

基本思想

  直接插入排序就是将一个记录插入到已经排好序的有序表中,从而得到一个新的有序表;最初的状态则是将整个序列看成是由第1个元素组成的有序序列 第2个元素至第n个元素的无序序列,这个两个序列组成的,如下图:

重点

  将第2个无序列表中的元素逐个插入到第1个有序序列中,最终使得整个序列有序,如下图:

代码实现

  代码实现语言采用java,没学过java的也没关系,只要有编程语言基础,就不影响阅读

/**
     * 直接插入排序
     * @param arr 目标数组
     */
    public static void strainghtInsertSort(int[] arr){
        int len = arr.length;
        // 将元素arr[i]插入到有序列表中arr[0...j]
        for(int i=1; i<len; i++){                            // 将arr[i]插入到有序列表
            for(int j=i-1; j>=0&&arr[j]>arr[j+1]; j--){        // arr[0...j]是有序列表
                swap(arr,j,j+1);
            }
        }
    }
    
    /**
     * 元素交换
     * @param arr
     * @param pos
     * @param offset
     */
    public static void swap(int[] arr,int pos,int offset){
        int temp = arr[pos];
        arr[pos] = arr[offset];
        arr[offset] = temp;
    }

执行过程模拟

可能基本思想大家懂了,但是不一定能把代码写出来,现在我把代码已经给出来了,可能又不一定能理解代码为什么这么写,那么我们就来模拟一些计算机执行上面程序的过程,这个过程之后大家就理解了。

  1)程序从strainghtInsertSort方法(函数)开始执行,i=1,那么j=0,j满足条件j>=0&&arr[j]>arr[j+1],那么交换arr[j]和arr[j+1],此时,状态如下:

    此时j--后,j=-1,不满足条件j>=0&&arr[j]>arr[j+1],跳出内层循环

  2)那么接着执行外层循环,i++后,i=2,那么j=i-1,则j=1,不满足条件j>=0&&arr[j]>arr[j+1],跳出内层循环,此时状态如下:

  3)与上一步一样,i=3时,则j=2,不满足条件j>=0&&arr[j]>arr[j+1],跳出内层循环,此时状态如下:

  4)重点看这一步,此时i=4,那么j=3,j>=0&&arr[j]>arr[j+1]条件满足,执行循环体,交换arr[3]和arr[4],得到如下状态:

    乍一看,上面的有序序列变成无序了呀!博主,你这有问题呀!别急,毛都没长齐,就想要老婆,那怎么行了!接着往下走,此时执行j--,则j=2,j>=0&&arr[j]>arr[j+1]条件满足,执行循环体,交换arr[2]和arr[3],得到如下状态:

    问题又来了,你这有序的序列不还是无序吗,还是有问题呀;骚年,别急,一口吃不成一个胖子,接着往下看,继续j--,j=1,j>=0&&arr[j]>arr[j+1]条件依然满足,交换arr[1]和arr[2],得到如下状态:

    这次骚年学乖了,不说话了,那么我们接着往下看,依旧j--,j=0,j>=0&&arr[j]>arr[j+1]条件依然满足,交换arr[0]和arr[1],得到如下状态:

    此时骚年惊讶了,哎呀,有序了! 惊讶之后,别忘把程序跑完,j--,j=-1,j>=0&&arr[j]>arr[j+1]条件满足,跳出内层循环

    那么i=4时的最终状态如下:

  同理,当i=5,6,7,8时,过程和上述一样,我这就不复述了,不过,心急的骚年还是要去把5,6,7,8执行完哦!

难以理解之处

基本思想其实好理解,可能内层循环的判断条件 j>=0&&arr[j]>arr[j+1]有点不太好理解,其实你根据上述的模拟过程应该能理解;

   此时骚年说话了,我理解呀,这有什么不能理解的,好吧,博主小瞧骚年了,博主刚接触这个算法的时候,j>=0&&arr[j]>arr[j+1]还真卡了我一会,模拟执行几次之后才理解;骚年果然比博主厉害呀!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数说工作室

统计师的Python日记【第十天:数据聚合】

本文是【统计师的Python日记】第10天的日记 回顾一下: 第1天学习了Python的基本页面、操作,以及几种主要的容器类型。 第2天学习了python的函数...

5298
来自专栏趣学算法

数据结构 第10讲 好玩贪吃蛇——数字矩阵

1073
来自专栏带你撸出一手好代码

JavaScript贪食蛇游戏制作详解

之前闲时开发过一个简单的网页版贪食蛇游戏程序,现在把程序的实现思路写下来,供有兴趣同学参考阅读。 代码的实现比较简单,整个程序由三个类,一组常量和一些游戏逻辑...

4149
来自专栏机器学习算法与Python学习

资料 | Python的14张思维导图(可后台下载)

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 来自:AI科技大本营 下载方式请见文...

3808
来自专栏進无尽的文章

面向对象设计中类的关系

所谓的设计正是采用恰当的方式组织类关。因此谈设计我认为首先要从类之间的关系开始说起.

2875
来自专栏AzMark

Python函数的介绍

1626
来自专栏极客猴

用 Python 学习数据结构, 有它就不用愁

数据结构,我们对它已经是耳熟能详。对于计算机相关专业的大学生来说,它是一门专业必修课。从事软件开发的人员则把它作为谋生必备技能。这充分体现数据结构的重要性。因此...

742
来自专栏颇忒脱的技术博客

Elasticsearch中将Doc根据A字段排序获得第一个Doc的B字段值的方法

最近遇到这样一个需求,要通过Elasticsearch将Doc根据A字段降序,然后获得B字段的值,最终根据B字段的值再去做Pipeline Aggregatio...

1782
来自专栏C语言及其他语言

[每日一题]方程的根

今天的每日一题是大家小学、初中、高中、大学都需要会的一种数学题,但只要我们会了代码,一切都只要输入数据就行,答案秒出,是不是简单了很多呢 题目描述 求方程 的...

2503
来自专栏AI研习社

用在数据科学上的 Python:你可能忘记的 8 个概念

如果你在编程的时候发现自己一遍又一遍的搜索同一个问题、概念或者语法,那么你并不孤单。

961

扫码关注云+社区

领取腾讯云代金券