00:00
同学们,我们继续来学习排数排序算法的下一种叫基数排序。那么基数排序是什么呢?大家可以看到。基数排序是统排序的一个扩展。它什么意思呢?我们看基基数排序叫rid thought,它是属于分配式排序。Distribution,那么又称统治法,就是bucket sort那。到底它是个什么东西呢?我们看,顾名思义,它是通过键值的各个位上的值,就是它是以各个位上的值将要排序的元素分配到一些桶里面,那么这个桶在哪里呢?其实就是数组。从而达到排序的作用,第二种呢,第二点我们要知道激素排序它是属于一种稳定性的排序,何为稳定性?何为稳定性?何为稳定性?你可以这样理解啊,后面我还会想说,比如说我这里有个数组是三。
01:03
一。43。一好,那么大家看到这有一个一,这也有一个一,对不对,那么稳定性指的是当我们对上面这个数组。排序结束以后。那么它会得到一个一,一个一,一个三,一个43,是不是这就是从小到大,那么所谓稳定性指的是你原先的这个一,各位同学我换一个画笔。就是你原先的在前面,这个一仍然在前面。你后面这个一呢会在会在前面这个一的后边,也就是说这个一呢会在这个位置,这个就是属于稳定性排序简单先说到这里好吧。那么技术排序呢?我们是统排序的扩展,如果有同学学过这个统排序,那么你再来学这个技术排序其实更轻松。
02:00
我们或者这样讲,基数排序呢,它是一种扩展的统排序,也就是说你学完基数排序再看统排序也是非常简单的。那么这个基数排序是1887年,是赫尔曼这个人他发明的,他是这样实现的,他将整数按照位数切割整不同数字,然后按照每个位数分别比较。那这个说的有点抽象。那么这样子啊,我们待会儿呢,举个例子,大家就很清晰的知道了。那么基数排序它的基本思想是这样子的,我们先来看一下,将所有带比较的数字统一为同一同样的数,呃,这个数位长度,然后呢,数位长度前面补零,比如说你你这有个四啊。那么如果说我要把它补成百位,前面我认为有两个零,明白这意思吧。啊,就这个意思,然后呢,从低位开始依次进行排序,这样从最低位排序一直到最高位完成,那么就变成一个有序序列了。
03:00
好了,同学们看,我这有个图文解释,那么待会儿大家一看图文解释呢,就比较清晰,同学们看,现在呢,我这里用基数排序的图文方式给大家讲解一下,比如说我们这里有一个数组是一个无序的,现在呢,我们要求把这个数序用什么呢?用基数排序实现升序排列,也就是说从小到大来我们先画个图。这个图呢,有助于我们理解技术排序的它的一个思想。好,我先把这个呢稍微放大一点,各位同学。好了,同学们看到啊,我们这个数组最初始的状态是这个样儿的。是不是这样子的?好,我们先在这里写上。一个内容说数组的。对宿主的初始状态。初始状态。那么它的初始状态是这样子,对不对,是这样子,好,我在这里给它设置一个背景,这样。
04:03
大家看起来比较轻松一点。啊,比较轻松一点好,现在怎么办呢,他是这样子的,他事先呢,认为我这他事先先有先有十个桶。比如这是一个桶,一个桶就是一个数组。两个三个四个五个六个,七个,八个,九个,十个。好,它一共有十个桶,怎么怎么排呢?这十个桶其实就是一个二维数组,好,我先这里给大家排好啊,大家看到,待会儿这个其实很神奇的,很有意思。好,我在这呢,再排一个对不对,这在前面排两吧。好,现在同学们可以看到我有几个,我有几个这个桶呢?这个桶就是数组啊,这个你可以认为这是一个数组,这是一个数组,这是一个数组,一共几个呢?一二三四五六七八九十。对吧,那么每一个桶,我们把这个标号为零。
05:01
这是第零个桶。好,这是第零个桶,那么这个是第几个桶呢?这个是第一个桶。下标为一的,其他以此类推,我就不写那么多了。好吧,不写那么多了,这后面是23456789对吧,一这是一,这是二。3456789。九个筒,那么九个筒他第一轮怎么做呢?大家看到啊,他第一轮是这样玩的,我在这里写一个他的他的第一轮的这个做法。好,我在这里呢,用一个颜色把这个它的算法给大家描述一下。好,来看第一轮。第一轮这个排序他是怎么做呢,他先。把每个数的个位取出来。啊,第一步注意听这句话啊,将。将每个元素OK,每个元素的个位。
06:05
个位数取出。取出。将个位数取出,然后呢,然后然后。看看这个数,这个数应该放在放在哪个对应的桶。对应。对应的这个统,再再说这个统的意思啊,这个统就是一个一位数组。统就是什么呢?统就是一个一维。一为数组完事。那大致就这个意思好,那么它这个怎么放呢?你看啊,53它的个位是三,就放在D3下边为三的这个桶,因为你现在下标为三的实际上是这个桶吗。是不是,是不是这个桶啊,这下边为三的桶,于是乎,他先把53放在这个地方来写上。
07:02
53就到这个桶了,当然三呢,诶,山也是在这个桶,于是他把山呢放在它的下边,注意听按这个顺序来放的啊,这是宿组的上上端,这是数组下面,也就说呃,这个数组这个桶的第一个元素方的是53,第二个元素方的是三,那么52下边为二,呃,这个个位为二,放在哪里呢?放在这个桶里面,那这就是542。听清楚了52,那这个地方我们我们也可以知道这一个是下标为二的这个数,这个桶,也就是说下标为二的这个数组。52完了过后呢,我们看748 748这个八应该是在哪个桶呢?是在这,是第四个五个六个,七个八个就在这。好,也就是说这个748在这个地方明白好,十四十四个位,14就放在下标为四的这个桶,那这边就是14。
08:01
好,这个呢,就是我们下标为四的这个图了。好的,各位同学看,放这那放到这里面过后呢,我们看再看214 214也是各位为是,于是乎这边就变成了214各位。好,同学们看第一轮我们这个排序呢,就把这个这个嗯,就把我们这个什么呀,呃,数按照个位放在对应的统了,那么第二步做什么事情呢?各位同学对听啊第二步。然后干什么呢?按照按照这个统的顺序,顺序其实就是我们这个一位数组的下标是吧,就是我们这个数这个一尾数组的这个下标。啊,下标下标依次依次取出,取出什么呢?取出数据,取出数据放回到从放入到哪里呢?放入到元素组。原来的数组,你原来数组是是,比如说原来这个数组是啊,OK,那么这样子它就放进去,怎么放呢?来各位朋友大家看啊,那第一轮完了过后,它放成什么样子,我们看一看。
09:15
好,就放成这个样子了,你看啊,同学们,第一轮数组的第一轮。的第的第第一轮第一轮这个排序就变成这样子了,同学们看。你原先。你原先是这个五三十二,那就从这取,第一个是542,先把542取出来。这个取出是53。按顺序来的啊,三下一个是14,再下一个是214 OK,最后一个是七百四百四十八。完事了,第一轮。搞定。那么第二个呢,按照刚才这个操作好,我把这个选择一把啊各位同学。
10:03
选择一把,然后呢,我复制一下,放在我们的下一轮,也就说第一轮完了过后呢,还有下一轮。OK,那下一轮他怎么处理呢?各位朋友,下一轮是在这个排序的基础上,再按照刚才这个流程来走,只是这一次呢,同学们注意听。这是我们的第二轮。各位第二轮排序呢,它是将每个元素的百十位。十位注意题,十位的位数取出,然后看这个数应该放在哪个对应的桶。还是放在我们这个对应的数据啊,好,那么我们来看看542它的十位是不是四啊,于是会把这个542放在第四个桶,放在哪里呢?放在这个位置。也就是说它原先的位置会被覆盖明白,比如说542会被覆盖。52分覆盖,那么这个地方这个值呢,其实还留在这,但是为了讲课方便呢,我先暂时把这些数据先清掉,我再说一遍啊,其实这些数都还在,但是为了讲课方便呢,我把这些数清掉。
11:11
诶,我把这个数清掉。啊不不是不是把这个桶删掉啊,把这个数清掉,这样呢,我好好讲课,但实际上我说了啊,这个数其实还在这个桶里边,只是呢,我两个都在写,我容易让大家听不太明白。好,现在我们再接着看啊,52放这了,那么53这个桶是五下边为五的,下边为五应该放到第五这个下边为五的桶,那就说这是53放这明白有这个这个桶的下标呢,就是我们的下标为五的这个桶啊,现在有数据了,对吧。好,我把这个标一下。没问题吧,非常的简单。那么53完了过后,下面是三三,诶十位是什么呢?没有没有没有就是零。没有就是零,所以刚才不是讲过这话吗?同学们看是不是按照这个。
12:01
较短的数前面怎么样不灵明白,那也就是说三呢,就会放在哪个位置,放在这个里面。然后呢,1414这个是十位是一,所以说放在这个位置,明白好,214是不是也是十位,就是214放这儿了,那么7484诶放在哪里呢?放在这个位置。OK啊,OK。好,我把这个先停一下78,那么78就放在哪里呢?放在这个位置了748。好,同样的道理,再把这个桶按照刚才这个所一,按照这个0123这样取,取的时候从从上面开始取,再形成我们一个新的数组,又重新回到二位。好注意听,那现在呢,我们又得到一个对不对,好得到一个,得到一个呢,这是我们第二轮排序的结果,相当于说刚才呢,我们是把这个结果。
13:01
诶,我这里画这么一个小的镜头,像,原先是这样子的啊,把这个桶整个拿到这面来,现在呢,又要把现在的这一个部分。各位同学要把这里面所有的数据放到又放回这个速度,那么第一个是52,好,这个我先去掉。去掉啊。现在从这个顺序选第一个是不是三,第二个是14,第三个是214,第四一个是542。再下个748,再下一个什么呀,53。是不是搞定了?搞定了,那现在呢,紧接着我们第三轮完了,下面又开始第三轮了啊,因为在这上面基础上我们就进入到第三轮了,第三轮是在哪个基础上处理呢?就在上面这个组的基础上处理好,我仍然哈,仍然把这个拿过来。各位同学,我复制一份。好的,放在这里,放在这里,放在这里,我们接着看,现在呢,呃,还是一样的道理,这个其实数据里面,这个桶里面都有数据,但是呢,呃,为了好看,我先把它清掉。
14:11
我把你清掉啊。我把这个清掉,这样我好讲课好怎么办呢?看三又开始找百位了啊,现在是百位。原先是十位吗?每个元素的百位。取出来,然后放百位的话,这个零前300位还是零,是不是三。十四百位是几呀?百位是零放这儿了。然后呢,二幺四百为422就应该放到这个地方明白,然后呢。542应该放在哪里呢?下边为这个桶,542没问题吧,然后呢,748,它的百位是七,就应该放在下边为七的这个桶,这是六,这是七,说这边呢是748。明白好,然后这边53 53的下标的那个百位为零,所以说放在这。
15:02
同学们有没有看到此时时刻再把这个桶里面的数依照原先这个顺序再次取出,就得到我们第三轮的这个结果?各位同学请看那第三轮的结果呢,是相当于就是我们这个上边。往里面放,那怎么取呢?大家看啊,我们再取一次。三下面是14,再下面是53,再下面是214,再下面是542,再下面是78各位。有没有发现已然是?二已然是一个有序的了。对不对。有没有好,所以说这个刚才整个这个流程呢,就是给大家讲的我们这个基数排序的一个,呃,操作原理,那么从这里可以看到,其实他没有递归的过程。他并没有递归过程,那么它只是在不停的把按照这个规则干什么呢?把按照这个百个位百位,呃个位十位百位往里面放,放完了取,放完了取,就这样,那到底他一共要放多少次呢?
16:11
要去做这个几轮,这个多少轮,这个怎么决定呢?取决于你这里面的最大数的位数。比如说你这里面最大的位,最大数的位数是三位,那么就一共要三轮,如果你的最大数是四位,那就要一共要进行四四轮的这样的操作。大致明白这意思了吧,好,这个就是我们所谓的什么呀,统排序的啊,对所谓的基数排序的一个编程思想。编程,我相信大部分同学应该听懂了。那如果你听懂了话呢?下面我们就准备使用代码将其实现。来先把这段视频给大家揭晓。
我来说两句