00:00
同学们,我们下面给大家介绍第三一种排序算法,叫插入排序。就是我们先看一下操作排序的,它的一个基本介绍啊,它的一个基本介绍。那么这个插入排序,它是属于一个内部排序法,是对预排序的元素以插入的方式去去找他该元素适当的位置,以达到排序的目的,就这个意思,呃,那么这个呃。操作排序。操作排序,它的一个排序算法的思想是什么呢?我们来看一下。它的基本实际上是这样子的,将把N个待排序的元素看成是一个有序表和一个无序表。那怎么怎么来看呢?开始的时候这个有序表中只有一个元素,也就是我们的第一个元素,那么无序表中有几个呢?有N减一个元素。
01:04
排序的过程中,每次从无序表中取出第一个元素。就是相相当于是,呃,那个第这无序表就是这个N减一个嘛,那第一个有序表就是第一个元素,那么把它的排序码依次和有序元素的排序码进行比较,也就是跟。这个有序表的元素直径比较,将它插入到有序表中的适当位置,使之成为新的有序表。那这个排序是想在这说的呢,比较的抽象,我们来看一个图解,大家一下就明白了,大家看这个图是不是就非常的形象。这个这个这个插入排序思路还是很很简单的啊,它比冒泡排序从思想上来说还是很好理解的,大家看说这里有一个数组,有六个元素,分别是17,三,25 14和,还有20和九,那么大家有看到,对于这一个初始状态,我们认为第一个元素17它就是一个有序表,因为一个元素不管是从大到小,还是从小到大,是不是都是有序的。
02:19
再把后面的五个元素看成是一个无序表。然后呢,怎么办呢。从这个无序表里面的第一个元素就是三。把这个三插入到这一个有序表的里面去给他找位置,怎么找呢。注意听这这个地方啊,它先让这个三跟17比较。追星,他让这个山跟湿气比较。如果发现山。比17小。就让这个17往后面挪一位。让17往后面挪一位,然后让这个山呢再往前面比较,如果发现山。
03:00
前面已经没有数了,那就直接把这个三放在这个位置,所以说你看第一次插入过后呢,这个就变成一个有序表。而下一次就是第二次插入的时候呢,又把后面的这四个数当做一个无序表,把前面三和17看成是个有序表,再为这个25找一个适当的位置。同样还是刚才这个逻辑,让这个25呢,跟这个有序表的最后一个元素先比较。他发现25比17大,说明这个25呢,直接插在这个这个位置就可以了。明白这个意思吧,啊,当然我这是按照从小到大来讲解的,如果是从大到小的话呢,那就是找一个,呃,给这个25找找到最前面去了,是这意思吧,那同样第三次插入的时候呢,又给这个14。给这个无序表里面的14找一个适当位置插入到这了,第四次插入呢,是是给这个在20,给这个20找一个适当位置插入到有序表。
04:06
第五次插入就是把这个九找到适当位置插入。那么大家有没有发现它这个规则已经出来了,什么规则呢?我一共有六个数据。那其实我一共要去这个添加或者插入几次呢,就是五次。是不是五次,因为呃,第一个元素它不存在找位置,因为第一个元素我们就认为它是有序的,所以说实际上是为后面的五个数。找适当位置并插入就完事了。好,同学们,关于插入排序的这个思路,咱们就聊到这儿。那么后面呢,我们就来看它具体的代码实现,就根据刚才老师讲的第一次怎么办,第二怎么办,第三次怎么办,这样一讲大家就明白了,好吧,呃,那关于操作排序的思路,我们就先分析到这儿,下面呢,我们用代码给大家实现一把。
我来说两句