00:00
同学们,我们继续来看排序法。那么刚才我们讲到。插入排序。那插入排序有没有什么问题呢?我们来思考一下。同学们可以看到这有一个幻灯片,这是一个简单插入排序存在的一个问题分析。同学们看。在这里呢,我这里有一个数组是234561,同学们看啊,如果此时此刻我们存在这样一个情况,要把后面这个一。就这个一。进行插入排序的话,那么它的过程就是这样子的,第一步可以看到。他先把这个六往后移,因为这个一是最小的嘛,所以说他会先把这个六移动到这个位置,第一步第二步。下面这个五呢,也不是所有五会继续移,那么四会后移对不对,三会后移,二会后移,同学们可以可以看到我们这个流程,当我们在进行操作排序的时候,如果我们假定这个顺序是从小到大进行排序的话,那么当有一个比较小的数。
01:13
当有一个比较小数在最后的时候,我们这个移动的次数很多。那么这样子的话呢,后移的次数明显,那么对效率就会有影响,是不是这样子的,所以说我们在考虑一个算法的时候呢。排序算法的时候呢,我们必须要去考虑存在的一种最差的一种情况,好鉴于这样一个情况呢,我们提出这样一个方案,就是希尔排序,那么希排序呢,他是希尔这个人,他在1951959年的时候提出的一种排序算法,那么希尔排序也是一种插入排序。也就是说它是一种。对排序操作排序进行优化的一种排序方式,它是怎么做呢?在简单操作排序的版本上经过改进,经过改进形成的一个更高版本的,更高效的版本,也称。
02:07
缩小增量排序,我们先来看一下希尔排序的一个基本思想,先看这样一段话啊,同学们可以看到。那希尔排序是干什么呢?它是把记录按下标。按下边的一定增量进行分组,也就是说分组,比如说我这里前面有一有有这么几个数九八是不是7654321,那么它先分组,它怎么分组呢?它让这个数组的大小,那个数组的长度除以二,先分成这样一组。然后在这个组的基础上,下面再分组,再进行这个插入排序,也就是说对每一组使用直接插入排序算法进行这个处理,随着增量的逐渐缩小呢,每组包含的关键词就会越来越多,当增量缩减到一的时候,整个这个文件呢,再进行最后一次插入排序就完事了。
03:03
大家明白这意思吧,也就是说,也就是说随着它的这个呃,增量的缩小呢,我们这一个数组就越来越接近一个有序的数列,而且后面进行一次排序的时候呢,这个数这个数的就是这个移动的次数就会越来越少,那么这样子看一个图吧,同学们看我这里有个案例。同学们看最初实的情况下呢,我们有。八有这么几个数?89172354660,一共几个数啊?同学们看是不是一共有十个数?是不是一共有数,它是没有没有顺序的,而且大家有没有发现这个零我们故意放在最后的。是不是有点像前面那个情况。那么现在呢,我们来看如何进行这个优化呢?首先我们先用这一个嫩识,这个嫩代表是数组的大小,除以二,那十除以二当等于五了,意味着我们第一次先把整个组分分成五组,那么五组它是怎么分的呢?各位同学一起看啊,它并不是像我们顺序来分,也也就是说不是891组,717 717组,这个没有意义。
04:15
他会怎么做呢?他会这样做。他利用一个不长。他让这个八和三为一组,注意看蓝黑色的一组,那九这个九和五是一组。那么以此类推,就是不同的颜色代表一组,那对这一组的就是对这个五组数据进行这个操作排序。那对这一组进行一个操作排序过后呢,我们得到的一个数组就变成这样,你看八和三交换。八和三交换,是不是这个是三在前面的了八,呃,这个三原先的位置变成八了。是不是这样子的同学们,那么九和五进行这个操作排序,那这个时候呢,诶,你看五在前面,九在后面。
05:04
同样,一和四。那一和四,因为它本身就满足小的在前面,大的在后面,因此一和四呢,并不发生交换。或者说不进行这个移动,那么七和六交换,你看这个七这边七变成六了。而原先这个六变成七了,是不是这样道理,最后一个二和零,你看同学们看二和零,零是小的,所以说一下就把这个二噌的一下就调到前面来了。对不对,那这样子我们就可以尽快的让比较小的数放在前面来,那么在这个基础上呢,原先是原先已经是呃五组,五组再除以二再分组。那这个五除以二等于几呢?等于2.5,那么这个时候取整就变成二了。那这个时候变成二,它又怎么分组呢?看黑色的又是一组3109756842是不是,那这个时候我们再进行对每组进行什么呢?进行这个直接插入。
06:05
那直接操作法呢,大家看对这一组的一个调整过后,黑色的这个部分和这个蓝色的部分调整以后变成什么样的,我们看啊310971组。56841组调整以后还按刚才那个方案,就变成了这样一组,变成什么?02143576。酒吧,各位同学请看,此时此刻,你们有没有发现这。这,这一次。这一次,这一组,你们有没有发现呢?此时此刻啊,此时此刻,他已经非常的接近一个有序的了。是不是非常接近一个有序的了。最后。这个二再除以个二等于一,那这个时候呢,我们发现原先是五组,现在第二次是二组,第最后一次是一组,再对这个数组,就是最后这个数组,因为我现在只能分成一组了,因为按照这个步长来说的话,它就逐渐的减少,那对这个数组呢,再进行最后一次。
07:07
插序,比如说我们原先的那个简单插入排序,那这个时候调整的次数就很很少,很快我们就拿到了个这样的一个。数据看0123456789,拿到了好同学们,那呢,这个就是我们对这个希尔排序的一个原理分析。和图解。那下面呢,我们就准备用代码将线排序进行实现,那么待会写代码的同学同时候呢,请同学们注意好实现我们放在下一个视频讲。
我来说两句