00:00
好,各位同学呢,我们来看一下这个希尔排序的第二一种方式叫做采用移动法。移动法,我们来看看移动法它又是怎么写的,那首先呢,我们在写移动法之前,我们先来测试一下当前这个希尔排序,它的这个速度有没有明显的提升,来吧,同学们还是老规矩,我们现在呢整8万个数据。好的,我把这段代码拿过来。这个是不是用来测试我们这个。速度的呀。好,我把这个呢拿到进来。格式化一下,现在呢,我要做8万个数据随机的啊,同学们看。8万个。八个。那么8万个数据呢?嗯,我们先把它写成8万。哦,这8000,这8万。个十百千万八万个数据,那8万个数据在排序之前,我们把时间是不是打出来了,我们再来。
01:00
把排序过后的时间也给他打印出来,这是我们排序后的时间。是不是这样子的,但是这个时候呢,同学们看啊,我们我们我们可以先测试一下目前这个这个随机生成的数组,它到底有没有,呃,有没有真正的实验排序,我们把这个写成八行吧,因为8万个我们如果打印的话就太恐怖了,对不对,好,我们来先运行一下,先测试一下代码的正确性。OK,我们可以看到,我们可以看到,那么我们随机生成的八个数据呢,它在进行线,现有的线排序构仍然是有效的。说明代码没有问题对不对,那没有问题的话呢,现在我要把它改成8万。8万。没没毛病吧,但是8万我们再去打印这个显然不可能的,8万个数据,你这么一打印时间时间太长了。我们测试的是排序的时间,不是测试打印的时间,对不对,因此我要把这个打印呢注销。因为我们刚才已经确定确实没问题,把这个是不是也要注销。
02:04
好,各位朋友,现在呢?现在我们就可以来玩一把了,现在我们来测一下8万个数据,我们一共花了多少时间来运行着。运起来。好,现在是。九分42米。稍微的等一下。你看。还没还没拍完。还没拍完。OK。怎么还没拍完呢,有点慢,是不是等待一下?我们可以看到他花了将近多少时间呢?同学们看是不是将他已经用了17秒,那么有没有发现这个17秒,原先我们操作排序就是简单的操作排序,其实也大部大致也就这个时间了。是吧,你看原先我们这个操作排序,呃,这个是17秒,我们原先这个insert。我们Excel排序,假如我们也是8万个数据。我们来比对一下它有没有提升呢?好,现在这个我不要打印它啊。
03:03
这打印这个就就出大问题了。好,我们来测试一下原先这个insert的排序,它花费的时间是多少。好,我这写写上这个啊,叫做插入排序,这样大家可以比对插入排序来,各位朋友,我运行时。我运行制好运行起来。现在我们用的是操作排序,刚才我们改进过的,你看你这整完了过后。你居然变得更慢了。哦,这个这个就没有意义啊,你整个需二排序过后,你不但没有变快,反而变慢了,你看我们用简单的操作排序法是花了四秒钟,而我们用现有的希尔排序法,我们花了。哎,刚才那个是17秒啊,显然这个方案就虽然你这个希尔排序的思想很好,但是呢,肯定是存在问题的。什么问题呢?各位朋友,现在我要进行改进,也就是说我们的问题一定是在交换,出了问题,大家看我们来分析这个这个地方啊,你看你你现在写写的希尔排序是当我们发现有一个有有两个数据,呃,这个大小啊逆序的时候,我们就是不是就交换了。
04:16
数据交换,那这样子实际上代代价是很高的。代价很高的,其实并没有真正的利用到我们以前那个操作排序,因为操作排序我们以前是一位法。是不是当我们发现有一个大的时候,我们并没有马上马上交换,你现在是发现一个交交换一个,发现一个交换一个,你很笨的。是不是你相当于说是在交换了,而我们原先这个插入排序它的思路是什么样的呢?我我在为这一个无序序列找一个出手,我先找到位置,然后一次性插入。是不是,所以说我们现在还要对他进行一个改进,各没有改进呢,直接写代码。来吧,我们现在写一个对。对,这个交换式的。交换式的希尔排序进行一个优化。
05:04
把它改成什么呢?我们改成这个移动法,或者叫移位法。一位法。一位。移位法,那这个移位法怎么写呢?那么我们直接去写代码了啊。Public大体思想一样,就是就是在交换的时候,不要发现一个就交换一个,其实就这么一点优化那么线。SHORT2,我们写的第二个方法,OK,那同样你把这个数组是不是要传给我呀,传给我OK,这个跟原先是一样,然后呢,我们就开始把前面这个代码打过来,他整体思路还是大体相同的。所以说这段代码呢,我们。是需要的。对不对,这段代码还是需要的,因为我们仍然是使用了增量。的干。干什么呢?我们并逐步逐步的缩小。
06:03
缩小什么样缩小我们这个增量,是不是你第一次是呃我第二次呃变二,第三次变一,第四次变零就退出了,这个没有问题,那下面的代码呢,我们仍仍然继续写啊来从什么呢?从D。不够。哎,大家看这有有有变化了,盖B个元素,盖B个元素开始。开始逐个。足够。对什么呢?对其所在的。所在的这个主进行直接插入。OK,直接插入排序法。那现在我就直接写代码,大家看能不能看懂for循环。N ti等于GA。然后呢,I小于R点的值,有没有发现现在是不是。诶,这个。
07:01
GAP。好把这个地方别写错了啊,那别写错了,然后呢点认识了,现在我们用的就不是交换法了,是不是就是我们以前传统的这个操作排序了,因为我从这GAP开始找位置了。是不是,然后现在呢,我们仍然找,先把这个待插入的位置先这个纸先保存,这个下标先保存起来,然后呢,下一步我们用一个临时变量来记录要插入的这个数是不是跟前面那个插入方法一样的,就说这个数是要带插入的I带插入的,那我们先把它放到这个temp里面去给他找位置就可以了,那怎么找位置呢?各位朋友非常的简单。如果我们这个解怎么样小于零。减减去一个干这个地方跟原先是有区别的,因为你现在在进行这个比较的时候,并不是一个加加减减的问题。
08:03
它是有一个不长的。是不是,所以说你不能按以前那个方方法做了,那下面呢,有个Y循环,这个Y循环跟原先大体相同,那么我让这个。解,减去一概,如果它还大于等于零,说明我们还可以继续找位置。当然找位置的时候呢,同时还要满足temp,你要小于RC压仍然是解减去GAP。什么意思,是不是跟我们以前那个操作方法是,呃,大致是同样一个含义啊,是不是同样一个含义,就是说你。我把这个格式化一下,就说你只要Y要循环说明什么,说明你还没有找到位置。就外循环还没推出,说明你还没有给这个temp找到适当的位置,我们在前面讲操作排序也是这样讲的吗?好,现在呢,我们就开始移动。哎,而不是我们原先的交换了移动,是不是让我们这个当前这个R位。
09:01
往后移啊,就是你找到的这个,谁把这个截盖。这个地方大家要理解哦,这是谁谁移到哪去,是节俭概补这个下边对应的元素移动到节这个位置去。理解。是不是好,紧接着呢,我们要把这个结。按照我们这个步长在。后再往前面移动。是不是,呃,比较一个再再往前移嘛,是不是跟我们操作方法一样,就是说如果没发现我们那个原先是index减减,对不对,这个是节减。GAP,但是不是减一了,原先我们是不这样写的。减一,现在因为你你你的这个步长是GAP了,所以说要减GAP,然后再去找,等到它退出这个循环以后,说明什么问题,找到位置了。当。当退出我们这个while循环后,循环后就给什么呢?就给这个temp找到了。
10:01
找到了插入的位置。是不是这个意思啊?是的,那这样子呢,我们就直接放进去就可以了,哎,谁呀,官方要解它等于什么呢?等于我们这个temp,这个temp就有点有点类似于我们以前写的那个insert value。明白好,这样子显然就用的是我们移位法,而不是交换法。你。好,那么这个代码我们就写完了。那写完过呢,同学们,我们来玩一把呗,看看这个效率到底有没有真实的提升。显然肯定是会提升的啊,肯定是会提升的,朋友们,我们来运行值,嗯,这段代码呢,首先我们先来验证一下,我们写完这个,呃,移位法过后,这个代码的正确性,先验证一下,是不是需要验证一下,那同学们我们打开这里,我们先把这个随机数呢改成八位。为什么改成八公呢?我想我想打印出来看看它到底有没有效,然后。这个是交交换式的。
11:01
交换式的,那下面呢,这个SHELL2就是刚才我们写的SHELL2。这个呢,就是我们的一位式,是不是这意思,这是一位。移位的移位,这个移啊移动。移位,移位的一种方式,那现在我们用第二种来玩一把,好,现在我可以把这个数字先打开一下,为什么可以打开?因为我现在只有八个,我们先验证一下移位法的正确性,运行之,各位朋友请看代码。我们首先看,当我们处理完了过后,哎,小的对不对,是不是要逐渐变大呀。没问题,你你如果说不相信的话呢,你也可以把我们最先前这个打开给同学们看一下也是可以的,就说我们现在呢,把这个最先前这个打开,你们看一下最先前排序前我们是这样一个顺序,是不是,排序后我们看是不是。有序的。怪朋友是不是有虚的?显然是有序,说明我们这个移位法代码肯定是没有毛病的,那既然如此,现在呢,我们就可以大胆的测试我们8万个数据到底OK还是不OK,来去掉,现在我把八改成8万。
12:13
A写错了啊个十百千万没问题,紧接着我们把这个也改成8万,那改成8万以后呢,这个地方我们就不能再打印了,因为八个数据太大了,对吧,你要这这一打印就就瞎了啊就瞎了好现在我们看移位阀,8万个数据,8万个数据的数组,然后呢,运用我们一位法,那么时间到底有没有变化呢。运行一把走起来。OK,可以看到,一秒钟搞定。你是零八,我零九,至少原先你的这个操作排序大概是三秒左右,是不是我的一秒搞定,至少提升了,我们再运行一下,看看是否真的是这样子的。你看是不是一秒。对不对,很稳定的嘛,很稳定的。
13:02
对不对,这个甚至你一秒都不到,一秒都不到,好了同学们,那关于我们这一个呃,操作排序的,呃不希尔排序的第二种方式移位法呢,就给同学们介绍这里。大家要深刻的去理解啊。我我说了这个移位法并并不神奇,它就是我们以前这个,就是相当于把我们这个缩小增量的这种方式,结合我们以前这个。那个操作法也一味去找位置的这种方式结合起来,而不是发现一个就交换一个,仅此而已。那么我现在把代码呢,给各位朋友板书到我们这边来,大家理解哈。板书到这里来就OK了。那现在呢,我们将其本书。来,我们刚才讲的是什么内容呢?刚才我们讲的什么内容呢?我们讲的内容是呃,这样子的,首先我们提出希尔排序的一个必要性。啊,也就是说我们分析了简单的排序,它存在的问题,它存在什么问题呢,同学们。
14:05
简单的排序,它存在的问题是,当我们有一个数最小的时候,我们这个步骤就是把一个最小的数往按照我们从小到大的顺序来排,它移动次数太多了,所以我们这得出一个结论。对不对?我们的结论是,当需要插入数是最小数时,我们后移的次数明显增多,那么对我们效率有影响。因此呢,我们就提出一种新的这个排序算法,什么呢?序二排序,那希尔排序基本介绍呢,我们拿过来。对不对,它的基本介绍是这样子的,首先我们说了希尔排序呢,它也是一种插入排序。这个大的。大的方向没有变化,只是呢,他对简单的操作排序进行了一个改进的更高效的一个版本。而且我们把它称之为缩小增量排序,就说如果你听到有人说叫缩小增量排序。
15:04
给能力什缩小谁的增量呢?缩小我们原先那个分组的这个增量,原先最早十个数据,你分成五组,随着不停的缩小,是不是最后变成一组了呀。试一试吧,同学们啊,希尔排序的它的一个思想大致是这样子的,后面呢,我们这有个图解。啊,注意啊,当增量缩减到一的时候,我们就退出。那这有一个关于希尔排序的图解,我们也给各位朋友拿过来。那我们针对这个图解,就是针对这个图解呢,我们。呃,做了一个说明,同时呢,也实现了我们代码。是吧,这是他的一个示意图,这是第一张图。这是第一张图,紧接着下面还有最后一次呢,这个图我也给同学们拿过来,这第二次就第二次啊,最后一次啊,这最后一次,最后一次呢,就是在上一次的基础上进行的。呃,一个一一个处理,那这个处理完了过后呢,同学看我们就把代码给各位朋友拿过来测试了一下,是不是这样子的,那写代码的时候呢,写这个希尔希尔排序法的实现的时候,我们说了在希尔排序呢,有两种思路,有两种思路,第一种思路呢,就是我发现。
16:18
我发现你这两个数啊,有逆序的情况下,我就直接交换。是这样子的吧。而第二种呢,我不是这样做的,我是按照以前我们那个插入的那种移动位置的方式来处理什么呢,就说我不马上交换。我先后移,如果你不是我的位置,我就把你这个数往后面移一下,然后直到我找到我这个temp该去的位置。过后我一次性的。把它放过去就完了,所以这个速度呢,明显提升。对不对,好,最后这个代码呢,我该写到这儿,代码实现,代码实现呢,我直接将代码给各位朋友板书到我们的笔记中。就可以了,来,各位同学插入到这里来。
17:02
好同学们,那关于这块呢,就是我们讲解的这个视频阶段,就是我们讲的希尔排序的一个优化。
我来说两句