00:00
来,我们用代码给大家实现一把这个技术排序。品类。RA。少。好,同学们,现在呢,我们老规矩哈,首先呢,我们仍然先做一个数组出来。那为了跟刚才我们讲的这个数组匹配呢,我们使用的数组就用刚才我们讲这个原理的这个数组,好吧。就用这几个数,这样呢,待会我们可以对比来进行讲解,对不对。来吧,放进去。好,格式化一下。然后呢,我们这就写一个技术排序。基数排序方法。Public static VO,然后我们取个名字叫做rid,什么呢?Sort,你给我传一个数组过来就可以,我完成一个排序任务。没吧?
01:01
OK,那我应该怎么做呢?来,我们先搞定第一轮,就是我们先把第一个这个事情做完,就是第一轮往里面放。然后取出来这个流程。然后再找规律,这样呢,大家听起来会比较轻松,而且记忆会比较清晰,那我们先把第一轮搞定。打开这里。好,第一轮,第一轮排序。所谓第一轮排序就是指的针对什么呢?啊,针对每个每个元素的什么呀,各位。进行排序处理,是这意思吧?那大家想一想,刚才我在讲过,我们是不是需要十个桶啊,那十个十个桶我们应该怎么做呢?是不是我们先要定义一个二维数组表示十个桶,这个没问题吧,是定义一个二维数组。表示什么呢?表示十个桶。
02:02
大家注意啊,每每一个桶呢,就代表一个一位数组,就每个每个桶其实就是一个一位数组,对不对,每个每个桶就是一个一为。宿主。一为数组没问题吧,那现在我们开始做了,那首先呢,我写一个。这样的二维数组bucket b统的意思。6IN首先十问题来了,每一个桶有多大呢?各位同学能想到吗?就说我们现在不是有十个桶吗?但是是不是每一个桶,比如说这个零,标号为零的这个一位数,它到底有多大呢?你们觉得有多大?不好说,你看我们这里面用到最大的就俩,那你按理说定定两个就可以了,但是问题来了,假如我们举个最极端的例子,假如我们这几个数,它的个位全部都为一,或者全部都为零,那怎么办?
03:00
因此你没有办法这个时候,这个时候呢,你只能把这个定大一点。对不对,所以说我在这里面说第一第一件事情呢,说明一把说明一把,OK,第一点就是呃这个,呃,这个二维数组呢,它是包含了十个一位数组,这个刚才说了啊,二维数组包含包含十个。一维数组,每个一维数组就是一个桶,这个不说了,第二点。那么为了防止溢出,注意听啊,为了。为为了防止在放树的时候放入树。的时候,什么样数据溢出,数据溢出溢出我们只能这样做,我们干什么呢?我们认为每个一位数组的大小为二点。则只能这样做啊,则每个一为数组。
04:01
即桶,就每个桶它的大小是多少呢?大小我们只能定为R点,没有办法。所以说大家有没有发现我们这个统排序是很明显的用空间来换时间的一种算法。所以说他对额外的空间需求是比较大的,那没办法呀,对不对,所以这个地方是很很明显很明显很明很明确,就是什么呢?激素排序。基数排序是什么呢?是使用空间换时间的经典算法。换空间换时间的经典算法。好经典算法。对不对,好,那我没办法了,我只能用点认识,原因就是这么来的。对不对?好,那么第二个问题来了,同学们有没有发现在我们整个这个操作的过程中,我们会取这个数据,大家没看到这条线。你们有没有注意到,刚才我在这个位置说我从什么什么地方把它取出来,这个是我们。
05:07
人的眼睛用肉眼来观察每个桶有多少个数据,但实际上各位同学,实际上我们应该想象到是不是我们每一个桶。我们每一个桶。都应该有一个有一个下标在不停的取。就这个桶有一个是不是。那这个桶也有,这个桶呢也有。是这样子吧,每个桶都有一个表示,每个桶都应该有一个值来表示这个桶实际当前放入了几个数据,能理解吗?这个有点有力,因为因为你想嘛,我我从这个第四号中,我怎么知道取四取两个数,而不是而不是取三个数呢。我怎么知道呢,因为下一次你看啊,你看这个第一轮,第一轮是编号为五的这个桶一个都没有,但是到了第二轮这个编号为五的这个桶是不是就有一个数据了。
06:05
是不是每个桶每次取的时候,就是每次这次取,这次取他也他不确定这个桶里面有多少数,因此你每次都要去重新更新每个桶。就是你每放一次都要去有一个有一个方法来记录每一个桶到底有几个有效数据的这么一个变量啊。是不是好,所以说我现在呢,打开这里,我就说一下啊。我就说一下。什么呢?为了记录,为了记录,为了记录每个桶,每个桶。记,记录每个桶中实际实际对实际实际存放了。存放了多少个数据?多少个数据,注意每次不一样啊,每次放的时候都不一定一样。啊,愿意你有一次放的多,有一次放的少都有可能,那么怎么办呢?我们这样子啊,我们定义。
07:04
啊,我们定义一个,我们定义。一个一维数组。一为数组干什么呢?来记录各个统。的有效的,呃,各个桶每次每次放入的这个数据个数。你你只有知道放入的数据有多少个,你将来才知道怎么去,是不是道理,好同学,那我写一个东西啊。怎么写呢?非常简单,我就用bucket。Bet element element元素的什么呀?然后呢,这个一位速度等于什么呢?六一个INT10。因为我我每每一个桶都要去记一下,所以说我需要这个一位数组呢,嗯,是十个的。
08:00
大家明白吧,就说感,嗯,说的再再直接一点,你可以这样理解,可以可以怎样理解,可以这样理解。这样理解怎么理解呢?我们。Element,零。这个记录的就是什么呢?记录的注意听啊记录的。就是。就是什么呢?就是这个这个啊,注意听。呃,就是零。就是第零个组这个。你八级的零,这个是个是一个桶,对不对,这个是一个桶,这个你能理解吗?就是这就是这个桶的。桶的什么呢?桶的这个这个放入的,每次放入的这个数据的个数。其他以此类推。哦,其他意思类,比如说这个唯一,那就是放的是八一的这个桶里面的数据。我不说那么多了,好,有了这两个数据过后呢,同学们,我们继续往下写。
09:03
我们继续往下写,那现在你有这个桶啊,也有每记录每个桶的数量,好,下面呢,我们就用for循环把它放进去,来吧,开始写段代码,大家先看我的代码怎么写啊,Int j等于零,J小于R点。对不对,结加加。节加加。因为现在我们做的是第一轮。啊,现在其实开始开始处理第一轮的啊,我写进去第一轮,那么第一轮呢,我便利这个数组的每一个数,把它的这个个位取出来,是不是好取出。取出每个每个元素,注意听啊,元素的个位,说,老师,你怎么知道元素个位怎么取呢?非常的简单,你看我这样写,是不是就轻松的拿到了digit数字of element。
10:00
对不对,然后我怎么取出它的个位呢。这个值磨上十。能理解,就说digit of element就是这个元素,呃,这,这就是每就是当前这个元素。而未解这个元素,因为你变历嘛,你假设有六个,那每一个呢,我模时是不是就得出它每个元素的这个,呃,每个元素的个位。个位啊,个位的这个值。个位的值能理解吧,那我如果找到它个位的值,是不是我现在就可以把它放进去了呀?是不是就可以放入了,好,放入到放入到对应的。对应的这个桶中。那怎么办呢?同学们刚才不是讲过了吗?那叫beauty but。第几个桶啊,显然就是你刚刚算出来的这个桶。那么这个桶放到。哪个地方去呢?
11:00
放到哪个地方去呢?OK,它是放在这里面的,大家看没有element。对不对,然后怎么样,第几次。这个有点不好理解是不是,大家看看能理解吗R。Orange。什么意思?就是把你当前这个数放在对应的桶中,第几孔这个桶?这个桶里面的哪一个,因为这个桶的元素它就会,呃,它就会变化吗?你第一次放的,你看啊,第一次进来是不是放在放在这个桶里面的下边为零的这个位置,如果再是,再如果再发现有一个,是不是我们要变到第一第一个位置啊。是不是,但是这个前面这个桶也有可能在变化,桶的数量有变化,然后不要忘了一些事情,还得把这个值进行一个加加。为什么要加加?因为你如果在这个桶,比如说这个你你算出来这个低级的open是零,那么就代代表在下边为零,这个桶放了一个数进去,因为你初始化这个为零嘛,然后加加的话,就代表如果下次就又计算出来有个数要放在第零个桶,是不是它就放到这个第零个桶对应的一位数组的下一个,呃,这个元素空间里面去了。
12:17
明白我的意思吧。这个也不是很难啊,啊,也不是很难,别别认为这个很难,其实并不是很难,好,当我们这样第一轮做完了过后,同学们知道我们此时此刻每一个桶放的数据就已然是哪个了呢?也是这样一个情况。就是第一次已经已经把已经做成这个样子了,而且呢,我我这个这个数组,就是你们看到的这个bucket element count里面已经记录了。每一个桶对应的有几个数量,因为我这儿不停加加。是不是好,那么这个时候我们紧接着要做一件什么事情呢?要做把这里面所取出来,重新放回到这个位置,是不是,也就是现在要做的是干什么呢?OK。
13:05
发什么呢?注意听。按照这个统的顺序,一位数下边一术放入原来数组,这个好不好写呢?非常的简单,来整一个index,我们先定一个下标。下标index等于几呢?等于等于零。等于零。好,等于零,那等于零我怎么做呢?肯定我要负循环。对不对,现在这样子啊,现在我或循环每一个桶,现在便利每一个桶。遍历每一个桶,并将并将桶中注意听桶诶,这个写写错了啊,桶中的数据数据放入到元素组。是不是好?现在呢,我们就来玩一把for循环。我们第一个变量叫K等于零,K小于什么呢?桶的数量。
14:02
你现在有多少个桶啊,你现在有多少桶?好,我们来看看你现在有的桶的。呃,这个数量其实是十个桶,那么显然我就要便利。多少次呢?呃,并且实次其实也可以按这个来算,因为我记录多少个也行啊,上面也行,下面这个也行,下面算是记录每个桶的数量,我就用它也是可以的,对不对,K加加。K加加。那么现在,嗯,说白了这个值是多少嘛,说白了就是十嘛,对不对,只是我为了将来处理方便呢,我没有写固定的值。是不是十,那么如果说老师我用这个BK的点ne可不可以一样的,因为它也是十嘛。没问题吧,好,那现在呢。拿到这个过后,是不是每个桶里面都有数据呢?好,如果注意听,如果桶。桶中有数据。有数据我们才才放入到哪里呢?放入到元素组,如果这个元元元素组啊元素组。
15:12
你打个比方,你打个比方,比如说我们在便利的时候,我们发现编辑到第一个桶,这个桶一个都没有,第一轮,那你还去往里面放什么呢,是不是?那么所以说我们要做一个判断,怎么判断呢?就是这样的片段,如果de a buck element。这个桶因为K刚好是等于零。第四是零,第二是一,就是说这个对应的桶干什么呢?它不等于零。说明他有数据,没有说明对应这个桶是这个K,这个对应的K这个桶里面是是有数据的,那有数据我们就循环。该桶。该桶是哪个桶?DK个桶及DK个桶。DK个桶DK个桶其实就是DK个一位数组。
16:03
即。第K个。一为数组对不对?变离数组,将数据放入,放入数据即可,放入好负循环,负循环RTL,我们换一个变量,0L小于什么呢?L小于我们。这个。Buckets。这个K。因为你有多少个嘛,对不对,L加加。是不是?是不是L加加,然后取出,取出元素放入到哪里去,放入到我们这个R中。你原先这个OA是不是就这样做的,现在放进去是不是就是我们刚才说的,呃,这这这这个动作,那这个动作怎么写呢?非常简单,前面是不是有个index就有用了,那么。Index。等于什么呢?等于就是你现在取出来的对应的这个桶现在是第几个孔,K这个桶第几个元素呢?K这个桶里面的DL元素。
17:12
因为你的便利嘛,是不是就放进去了,大家看现在是DK个桶里面的这个元DL个元素L是从零便利到我们该桶的,呃,这个该桶现在存放数量的一个最大值。整个这个for循环结束以后,各位朋友。各位朋友,那现在是不是这个事情就。搞定了。搞定,但是搞定了过后呢,呃,这个相当于说这个for循环结束以后,这个for循环结束以后,这这这个获循环结束以后呢,我们这个事情就。完事了。是不是就完事了。但是你要记住有一件事情。有件什么事情呢?如果我们下次还要取的话,呃,下次还要取的话,是不是我们第二轮还要重新来做的话,还得把这个重新置零了,对不对,因为你这次做完了,那下次还有可能要做,所以说还得把这个自零,只是你现在可以先暂时不置零,对吧?我们先写到这吧。
18:14
先写到这,好,我们先看一下此时此刻第一轮是不是已经搞定了。第一轮是不是已经搞定了,那我们打印出这个结果。来朋友们,第一轮第一轮。对什么对个位的排序处理。过后我们这个数值等于什么呢?各位朋友请看效果。哦,这样打不出来阿瑞。用这个数组工具,点to string,然后把外放进去,这是不是第一轮?好,我们来调用试一下吧,同学们,Rid。把我们的放进去。各位,如果第一轮不出什么问题,我们第一轮打印出来的这个数组长的样子呢,就跟刚才老师说的这个一样,也就是52,五十三三幺四二幺四七十八是不是这样子呢?不知道运行一下。
19:09
验证一下我们思路是否正确。呃,我把这个粘过来看一下啊,同学们,因为这个我来回切也很累。呃呃,7484,诶这个有问题啊,大家看现在是748542。呃,这个有问题三。这个跟我们想的有有不一样的地方,对不对,有不一样的地方,那这个问题是在什么地方呢?我们先来看。跟我们想的是有出入的。7483。我们看看问题是在哪里哦,我们的代码是不是在哪个地方写的呢?有不明确的地方我们看一下。For循环。For循环这边也是做处理了的,对不对啊,这边也是做处理的,那哪一块有问题呢?我们来稍微的调整一下,调整一下。
20:04
看看问题是出在什么地方。大家来跟着老师调一调这个思路。呃,我们看嗯,取往里面放应该没有问题,估计是取的问题,我们看这里便利啊,L0加。取出来过后index,哦,大家看我们这个index有问题,我们这个index呢,你你取出来给放一次过后,你这个index应该增加一下,你不能说我取第一个数放在呃INDEX0,我再取个数还放在INDEX0,这个不行啊,对不对,所以说应该是。加加,因为原先是零嘛,你加加完了价值一好,我们再来运行一把,请看效果,这次应该是没毛病的,大家看现在是5425431,各位朋友我们把这个呢给大家再写到这,看对不对,五四二五四三三幺四二幺四七七十八完全正确,好,既然第一轮做完了,那下面同学们老师思路就清晰了吧。
21:04
怎么做?同学们,你第一轮完成了,那第二轮是不是照猫画虎就可以了?来,把这个第二轮给同学们拿过来,注意听啊,这是第二轮的处理。我为什么要这样去写呢?就是为了让大家能够听得明白,不然你听不清楚啊,你听不清楚,听不明白老师在说什么,好讲这个算法其实是有难度的,就是有时候我老师知道,但是讲不清楚,或者说你听不明白,好这个流程不需要变化,这是我们第二轮仍然是对所有数组进行这个处理,对不对,是在上面这个数组进行处理吗?你看。你现在已经是这个德行了,然后我对我对这个已经处理过第一轮的这个数,第一轮处理过后的数组,再次处理这面代码不需要变化,但是有一个问题,此时此刻你再磨石就不对了。因为你现在是对十位进行处理,那我怎么才能拿到十位呢?各位同学,你现在是不是应该这么干,是不是在这个基础上除以一个十,再去磨十,这样就得到十位的数了?
22:09
能理解吗?打个比方,比如说现在我有一个数是748,我先除一个十,是不是就得到了74?然后再磨上一个十,是不是又就得到了它的个位十?呃,十位是四对不对,没毛病吧,同学们好,下面代码是不是不需要做任何变化,你该怎么做还怎么放。还怎么放INDEX0还是INDEX0,但是你不需要反复定义了。对下面这个代码呢,K0还是这样去处理,但是我们这边有个细节,有个问题,大家知道问题在什么地方吗?你们有没有发现,我们在上一季这个处理过后,我们并没有把这个桶里面的数量清为零?为什么?因为你你第一次排序完了过后,每个桶里面其实都已记录的有呃,第一轮往里面放的呃数量,但是你第二轮往里面放的这个数量呢,是要重新进行累积的。
23:14
是不是,你看你每次做了个是不是再重新进行累积啊,那你不能说我在第一轮上面再进行累计,而应该是清零了过后再累积,因此我们这方有一个动作非常的重要,这里。就是第一轮注意听第一轮第一轮。第一轮。第一轮这个处理后,处理后需要将每个。每个什么呢?K是零。这个能理解吧,要把它治零,否则会出问题。否则会出现这个很重要,这一点呢,很多同学在写这个基数排序的时候,往往这方忘了,所以代码就是错的,来各位同学,我把这个呢给大家写一把。
24:04
Bucket element,然后呢,K,我们这里代码写完,那么写完过我们这个地方再处理一下,你会发现呢,诶。OK了。这个地方OK了,再我们看第二轮结果跟我们想的是否一样啊,第二轮理论上说如果没有什么出问题的话,他就应该是。这个结果明白来运行之。运行时做代码,第二轮是这样一个结果,我看对不对呢,不知道试一下吧。第二轮跟我想的一样吗?314214542748543完全的OK。好,第二轮搞定,第二轮我们就搞定了,那第二轮搞定是不是该我们第三轮呢?朋友们,第三轮是不是老师不用这么说你就能写出来了吧?第三轮应该怎么办?各位同学来吧,第三轮,第三轮就是我们的最后一轮,为什么是最后一轮?因为我们最大的位数是不是就是百位啊,各位朋友。
25:02
因为我们一共有最最大的位三位数吗。好,现在我们来处理一下,这时这个不变,这个时候怎么办要诶刚才我们是。再往上写了,得到十位。十位的数这边呢,也是吨位对针对十位进行排序了,所以说这是出了一个十,是不是这个道理,那现在我们第三轮应该是对百位进行处理,那就我们写成百位。那么这边也要把它改成百位。那同学们,百位,你怎么得到每一个数的百位的值呢?显然这个地方应该怎么办?除以100。明白,那为什么除以100呢?你看啊,你这个740 778,如果我除以100。除以100除以除以100的话。它是多少呢?除100除以100,其实这个地方就已经是。
26:03
四了,因为我商我上一个七,呃,78除以100上一个七嘛。对不对,七点多少,七就7.48,那取个数就已经是七了。对不对,所以说这个模取不取,其实呃,也无所谓了,对不对,因为你除以100就可以拿到我们这个百位数整数,但是你七再磨一个十呢,它它还是七。是不是它还是七啊啊,你这在一个七的基础上再磨一个十,其实它还是七,这样我就给它统一起来了。没问题吧,好没问题,那这个做完了以后呢,同学们,我们接着往下看了,这个不需要变,这个呢,OK kk,但是我们发现没有我们上面第二轮,第二轮是不是也要跟刚才一样,也得要把这个。清一个零啊,不然的话你会影响第三轮,是不是好像说第二轮处理过后呢,要把这个指控好,这个时候第二轮处理完了,第三轮我们把它打出来。
27:01
第三轮看有没有问题啊,呃,我觉得应该没有什么大的问题,但第三轮过后呢,其实你就可以布置空了,反正也没有了,说说白了就第三轮你写不写这句话无所谓,写上了也不错啊,第三轮处理完了过后呢,我们也把它吃空吧。小心有第四轮对不对,好第三轮好,我们第三轮处理完了过后呢,就应该是我们的一个有序了,我就直接运行至。那同学们可以看到现在是不是有序呢?三幺四五十三过来了,214啊542748完全都OK,好同学们,那现在三轮处理完毕过后,是不是我们发现规律了,什么规律?
我来说两句