00:00
各位,我们来代码实现一把,然后打开我们这个eclipse,然后在这里呢,我们写上这个,我们创建一个类,对吧,叫做线。So,没问题吧,Share,然后呢,我们勾上这个主方法。再玩一把。好的,嗯,现在呢,我们先把这个数组写出来,我们这个数组呢,是这样子的,对吧,我们刚才写的是这样一个数组。什么呢各位,呃,我就我就用我们刚才分析的这么一个数组,这样呢可以用容易比较对不对?待会呢,我们还是用逐步推导法把这个希尔排序。写出来,那么8917。23546089172354608。九一。723。5460。没问题吧,这是我们的原始数据,跟他一样,我是六零。
01:02
OK,好,那有了这个过后呢,我们就直接来写这个方法,写的时候我们逐步推导哦,我们仍然是使用逐步推导的推啊推导的方式来干什么呢?来编写,编写我们share排序。各位好,我们首先看到这里面有一个说明,怎么看?因为这个C2排序的时候呢,它有它在在对有序序列进行插入时,有两种方式,第一种呢,叫做交换法,这种交换呢,它比较好理解。但是它的速度呢,相对较慢。第二种呢,在对这个需要排序时,我们对有序序列进行插入是采用移动法,这个移动法呢效率较高,但相对不太好理解,所以说我们先把这个交换法写出来,然后再把它优化成移动法,这样子对大家理解希尔排序会非常有帮助,然后呢,我们再分别的对它。
02:03
排序速度进行一个测试,仍然用8万个数据来测试,OK。各位,那现在呢,我们就来先写希尔排序的第一种方式,逐步推导同学们看啊,那现在我们开始写代码。写代码,Public。Static对不对,Void,那share。So,那这个时候呢,你给我把这个数组传过来没问题吧。问题好,同学们可以看到,我们就针对刚才这个图来走,我们就针对他的第一轮。就是它一共其实进进行了几轮,呃,由由这个原始数据到这边来,这是一轮,然后从这个数组到这边来是二轮,最后把这个再进行有序排序是三轮,也就是说实际上我们十个数据,我们一共进行三轮。OK,待会儿我们再找规律,这样呢,学习起来比较清晰,而且呢,印象很深刻。来,同学们,我们先写第一轮。
03:03
跟上我的思路啊。OK,那就第一轮。第一轮这样写啊,希尔,希尔。希尔排序的第一轮。第一轮排序。第一轮排序好,那现在呢,我们就来根据原先这个思路,首首先来说一下这个思路啊,呃,刚才我们讲过,因为第一轮他第一轮排序。第一轮。第一轮排序它是什么呢?是将。是将这个十个数据分成了几组啊,分成了几组啊,分成了五组。是不是同学们,那么这个时候呢,我们就按五组来进行这个处理,那就开始写了for循环。各位同学,你看,In的I等于五。然后呢,I小于R点,为什么要这样走呢?因为你后面郭同学,你后边这一个。
04:08
长度你是要进行这个处理的,是不是,所以你说从我到这个嘛,最后那到这里面过后呢,我们可以接着写下面代码,就是for循环it解等于什么呢?I减五,待会我们写完再看一下啊同学们看解要什么样呢?就要大于等于零。就要大于等于零,然后解减等于五,为什么这样写呢?好的,同学们可以看到。我这里做一个注释。就是我们便利下面这个内循环是在做做这样一个事情,便利各组宗。各祖宗。所有的元素能理解。那么我一共有几组?同学们,我共五组,注意看这个啊,我共共有五组。
05:01
那么每一组有几个元素呢?各位,每一组是,每一组是不是有两个元素各位同学。刚才是不是已经看到每组有两个元素,那既然有两个元素,所以你们有助于观察到我的这个步长是。减五。看到没有,所以说我这个不长。不长是五,那也就是说我们第一组的时候。我们第一组进来的时候,解等于零,因为你刚刚这个I等于五吗?五减五不是零吗?零这个呃,下标为零的跟谁进行比较呢。他他跟谁比硬比较呢,比较的时候其实就是跟他后面第五一个数硬比较,也就是说你看这里。八是第一个是吧,那我数几下呢?12345。这个才是。八和八对应的那一组的数据能理解是说我的步长呢,到时四减五的形式,好同学们,那我开始写了啊,就说如果如果当前这个元素。
06:07
干什么呢,它大于大于加上注意听啊,加上不长后。的那个元素。啊,别写错了啊,那个元素说明什么问题。说明什么?说明需要交换。说明交换,为什么要交换呢?因为你不是要从小到大牌吗?我说了啊,我们这个仍然是按照从小到大牌来讲的,如果从小到从大到小,那这个刚好要反过来。好,那现在就写一段话就可以了,Ifra什么呀,各位同学,它如果大于什么呢?解加五。是不是找到它后面那个数了,如果这个条件成立,那么我们就交换,怎么交换呢?我做一个变量temp。等于R。节。
07:00
没问题吧,好,然后呢,我们R解等于什么呢?R解加五,注意是加五啊,这点同学们要特别的注意和留心,是加五,不是我们以前的那个。啊,加一了,那这个步长呢,它是呃按五来处理了,好这个写进去,然后我们什么节加五等于多少呢?等于temp。那么就喜欢,那么这个temp呢,因为用的比较多,所以说我们可以把这个temp的定义放在外边去,这个没毛病吧,初始化来一个零。然后呢,这边我们就把这个temp写到这来。就可以了。各位同学好,那这个地方我们把它格式化一下,整个格式化好,这样子比较清晰,那也就是说当我进行这样一个for循环以后呢,最后我们这个第一轮的这个处理就完事了,大家有没有发现?你看啊,这里面是不是我一共每一组有每组有两个元素,是不是它的步长数位为五,为为这个为这个五,然后你看啊,第一次I你们可以看I等于五,进来过后解等于零,零呃比较以后,然后再减五,减五是不是到下一这个解解减减一个五过后,我们就到下一个去了,下一个到到哪去了呢?是到下一组进行这个处理。
08:22
所以这么是注意是减五。啊减五不要把它处理错了啊,处理错了好,那这做完了以后呢,我们来看一下我们这个地方处理过后,他的这个结果是什么样子的。啊,什么样子的,我们可以来看一看,我们可以来看一看,好我打赢他一下system。说我就说希尔排序排序一轮后。一轮后这个数组的情况呢?我们将其输出。我们将输出怎么输出呢?Rra用这个工具类arra.to string把这个打开,那如果说没有什么问题,我们这地方是正确的话,我们应该得到的结果应该是哪一个呢?是3516089472。
09:17
OK,那各位同学,我们来测试一下,那各位朋友,我调用我们的希尔。排序。线排序,OK,把放进去,同学们可以来注意观察,我运行一把。那么运行过后呢,我们看这个结果,OK 3516089472。3516。对不对,3516089472完全的。完全的正确。是不是完全正确啊?好,第一轮咱们搞定了,那是不是应该该我们的第二轮了,第二轮如法炮制,各位朋友,你看第二轮我们处理的时候思路就比刚才要清晰很多,那第二轮怎么玩呢?各朋友来吧,第二轮,那第二轮呢?
10:02
第二轮排序你是把它分成了几组,同学们是在这个原先五的基础上再除以二,是不是变成了两组啊,各位朋友,那既然变成两组,那我这个I呢就变成二,因为你在后面进行遍历的时候,这个还是要有的,那这个地方是不是也是减二了?因为你上来过后II等于二,那节应该是从零开始走的,二减二嘛,那同样我们这个步长也会变成二。因为你是再再找下一个,你再找找找下一个的时候,不是节俭,不是节俭了是不是,是不不是节俭一了,而是干什么呢?减二。边也布上,因为我是反过来做的嘛,大家看到没有,我是反过来做的,因为我是,呃,不像原先写的是结小于多少,是结大于多少,所以说我是从后面开始走的。好,那么这个时候呢,这个解和后面这个比较呢,显然也是变二,这个也变成几啊,同学们是不是也变成二啊,这个是不是也是一样变成二,好同学们,我们看第二轮线排序过后,它的结果是什么呢?如果不出问题。
11:07
我们这个代码没有问题,第二轮他得到的结果应该是0214357698,各位朋友运行着。各位朋友,我们运行着,那看看第二轮结果跟我们想的一样吗?哦,OK,完全的一样,对不对,021435。7698。没毛病吧,七六啊,7698完全正确,好,是不是还有最后一轮呢?为什么还有最后一轮呢?因为你二除以二还会有结果,还没到零呢,还可以继续分。好,继续,各位同学,下一轮这一轮我们的处理方案跟刚才完全的一样,到这边变成一,那这时呢,我们第三轮啊,这是第三轮啊,写错了,第三轮进行这个排序呢,各位朋友,十个数据变成了原先的。两组再除以二变成了最后一组,那变成最后一组呢?这个显然就变成一了。
12:01
变成一了,那变成一这边呢,也必然变成一,是不是我们减一了。那减一这边呢,俨然是减一,因为是最后一轮吗?大家有看到啊,最后一轮因为我是使用的交换法。这边我是用的交换啊,后面我们再使用移动啊,那这个时候呢,这个节这个显然它们两个是相邻的,所以说是结前面这个和后面这个是节加一这样进行比较的,然后这边呢,也变成一,这边变成几啊变成一,那这是我们第几轮呢?第三轮,各位朋友,第三轮如果不出问题,我们的结果必然是。这样一个效果,OK,同学们,我们运行一把。我们运行吧。那运过后我们看到的结果啊,空同学们可以看到诶。是不是已经有序了?OK,那也就是说实际上现在我们已经看到规律了,什么规律,我们的这个数据其实它在进行这个呃,排序的次数的时候,实在逐渐的缩小。
13:01
也就是说我们这说的什么呀,缩小的什么东西呢?看这里是不是我们做了个缩小增量排序。那他这个目的是干什么呢?它的目的是尽量让这个小的数,我按照且说按照我们这个顺序的数呢,尽量把它调整到前面去,把小的数,那反过来是尽量把大的数尽量快速的调到前面去,这样呢,我们在后面就避免了,出现什么情况呢?出现这种啊,一个特别小的数还在最后,然后移动很多次这样一个情况,尽量让他避免。OK,好,那有了这样一个东西,我们最后一段代码呢,就是将它整合起来,也就是说你这样写一步步写肯定是不现实的。你这是十个数据,那假设我是100个数据,你得写多少次啊,是不是好,我们把这个规律已然找到,那下面呢,老师把它整理一下。OK,我们根据根据前面的逐步分析。对不对,逐步分析干什么呢?我们得到得到一个循环,我们这个使用使用这个循环处理。
14:07
那大家可以可以看到我们变化的其实就是这个值,那既然如此,老师开始写代码了啊,For循环。怎么写呢?好的,我这地方写个game。啊,就是它的一个不长的意思了,那我们首先呢瑞点N。减去一个二啊,除以一个二除以二,那么只要我们这给。它干什么呢?它大于零是不是我们就做,是不是最后我们退出的情况是只要它大于零,呃,只要它大于零就做,当最后我们二一除以二的时候变成零,那就不能再去进行这个。呃,进行这个这个处理了,试一试吧,那这个地方我们每一次的这个分组是是这样写的,还记得吧,是不是这样写的,除以。哦,这样写。大家能看懂吧,就说你第一次是不是十除以二是分成了啊,分成了五组,那么第二次是五除以二变成了两组,第四第三次是二除以二变成了一组,再是二,再除以22212除以二过后变一,一再除以二变零零,是不是就不再大于零就退出了,是不是一共三次啊各位同学。
15:23
好,标起来过后,下面这段代码是变得异常的easy。我们只需。把这个temp。好,我们只这样子啊,把这个正步提到上面去。因为我要用了,然后把这一段代码,各位朋友请看啊,请看现在呢,我们把这一段代码复制到我们这个循环里面去改哪一个,各位朋友是不是把这个五改成GAP。把这个地方也要改成GAP,因为它在每一次不一样吗?好,这边的GAP这边呢,也变成它。这个是不是也要变,最后这个是不是也要变O了。
16:02
那这个用注释我们做一个变化便利,每一组共多少组呢?好的,这个组就是按照这个来分的。哎,是多少就是多少,每一组有多少个元素呢?OK,每组的元素其实就是按照我们这个分组来统计的。那情况就是实际情况是什么样子就是什么样子的,对吧,那按照实际情况走就可以了,共呃共有多少元素,那么不长是不是就是我们的。是不是好,按照这个实际情况来处理就可以了,那处理完了过后呢,我们可以在这个每一轮过后呢,我们依然打出这个提示信息,我们看看跟刚才的是否一样。来,我们写啊,第多少呃,希尔。呃,这样写啊,希尔排序。啊,这么呃呃这呃D。我们写一下啊,第多少轮呢,DX轮后。
17:02
他的情况是这个样子的,我们依然将其打出凿透。使菌,然后把什么放进去呢?把我们这个放进去,我们可以看到这个效果能不能出来。好,那这个X我们怎么办呢?因为我想处理它,我想把它看一下的话,我这写个计数器零。好的,那每一次进来过后呢,我们要打印出这个次数的话,我们就要这样去写了。把这个X打开,然后这边加加空。加加抗,然后这边我们包一把。诶,这边我们把它包起来就可以了,最后我们把这种代码格式化一下。最后格式化一下,代码就写完了。那有些同学说我们试一下呗,那现在呢,我们把前面这个推导的这段代码,整个这段代码这这几步将其注销。将其注销好,注销完毕过后,我们再一次来进行这个测试,就是用的我们这个循环,大家看这里面的循环是三层。
18:08
是不是好,那现在我运行一把,同学们看效果是否跟我们想的一样呢?运行之各位请看效果。好,我们可以看到效果跟刚才一样的第一次。第二轮。第三轮。完全正确对不对,也就是说我们现在呢,已然把一个吸耳排序的第一种方式什么呢?这个应该叫做。现在呢,我们相当于是讲的是在线排序时,目前用的是插入,在插入时用的是交换法。但是交换法刚才我已经讲了,效率并不是很高,为什么呢?你看你发现一个你就交换。其实这种是。比较笨的。所以它速度呢,应该不会很快。那待会我们可以做测试,然后再优化,那不管怎么样,关于希尔排序的它的一个思路和这个分析的第一步,这个第一个方案呢,我们已然写完了,大家看看能不能理解。
19:02
对不对,其实也并不难。并不难,就是你把你的思想说白了,就是你在这个讲解的过程中,你先有这个思路。这个思路或或这个思路其实就是你自己定的一个算法。啊,就是你要把这个算法理解清楚,然后呢,将其干什么呢,写成我们的代码。是不是这个这样一个过程,首先你得有,你得理解希尔是干什么的,然后才能写代码,缺一不可。好,同学们,那关于希尔排序的这一个原第一个第一个形式的代码实现呢,我们就给大家讲解到这里,大家理解一下。
我来说两句