00:01
同学们,我们来测试一下基数排序,他的排序速度怎么样,还是跟原先一样的规矩,我们来创建8万个数据,然后呢,给予这个测试,好,那现在呢,我们在上一个me。对吧,Merge short这方我们把一些代码拷贝过来。呃,大家可以看到呢,我们这里产生的是呃个十百千万,十万百万八万个数据,800万数数据对不对,好我们来试一下。把这个数据呢,我们先拿过来。放到这里。好非常简单,然后呢,我把上面这个先注销。对吧,上面先注销,然后这边是排序时间,然后呢,我们在排序过后,把排序后的时间也给同学们看一下。对吧,OK,这个呢是排序后的实验,那排序过后呢,为了验证数据的正确性,我们先把这个改成八,这样子呢,我们好验证一把。
01:07
好,在这里呢,我们输出排序后的这个数组长什么样子。A system。走一个,然后呢,我们说叫做叫做什么呢?基数排序后。计数排序后,然后我在这里呢,再把数组的情况打出r.to string,把R放进去。对吧,现在八个数据,我们看一下运行的效果。好,我们可以看到呢,哎呀,这个第几轮咱们就要不就别看了,你因为你要把第几轮也打出来,这个就特别的费时间,先注销它,就看最后一次是不是有血。19223234355560没有问题对吧?好,现在我们把数据呢,给它放大一点。数据放大一点,这个速度应该是非常快的。现在我们把它换成。
02:04
8万个数据。8万个数据,我们先执行一下,看看8万数据它花费多长时间。8万数据花了一秒。花了一秒,我们再来执行一下。啊,一秒都没到,我们把它调成80万个数据。80万个数据。我们再把它运行一下,我们发现呢,80万个数据一秒也没达到,我们来把它调成。800万个数据。800万个数据。找一个800万个数据呢,我们发现耗时一秒钟可以看到它比快速排序。都还要快,第一我们前面讲的这个merge,就是规定还要快,你看再来运行一下,看看是否稳定。是吧,刚才是一秒,诶,现在还是一秒,很快的很快,但是如果我们再来一个8000 8000万个数据,大家觉得会出现什么问题呢?
03:00
大家觉得有什么问题,大家看啊,你这8000万个数据看啊个十百千万十万百万,诶不是个十百千万十万百万千万八千万个数据,8000万个数据,你们知道我们会需要多大的内存吗。大家知不知道,你看啊,你在排序之前,在排序之前其实我们会开十个桶。而每一个桶的大小呢,就跟你的数组的大小一样,那大家先计算一下我们现在需要多大的一个内存。现在呢,我们有。现在我们有8000万个数据,8000个,十百千万,10万,百万、千万。一共有11个这样的数组,一个int,十个字节,这么多个字节,这么多个字节。113这么多个自己的空间,1024过后是K1024过后。是兆在1024过后是G,我们看看内存有多少个G呢?来同学们,我们运行一下。
04:07
这次呢,我们就快速用计算器来计算啊粘贴。要将近3.3个G。各位同学,那你想一想啊。我们。内存够用吗?可能就不够用了,对不对,那我运行可能会报告内存不足。我们看看是不是会有这样一种可能性,对不对,好,你看。你看这这已经不行了,看到没有。他说啊,他说你的Java的内存,Java的help对space空间已经出现了out of memory error,这个error是致命错误,就是内存不足了。它不足以支撑,所以说我们可以通过这个分析看到激素排序呢,它会耗费额外的。这个内存空间。那么我们要。在这个地方要做一些。注意和小心明白我意思吧,好同学们,那现在呢,我们把这个代码呢给呃,把我们这个这个讲解的呃,技术排序给大家总结一下。
05:09
那打开这里,我们刚才给各位同学讲解的内容是基数排序。屡屡思路。那么讲了什么东西呢?我们先来看。我们先来看,首先我们对技术排序做了一个基本的介绍。是这意思吧?我们先给同学们介绍一下技术排序它的一些特点。捋一下这个思路。技术排序的基本介绍那技术排序呢?它又叫统治法。也就是说他是把数据呢放在桶里面。按照个位十位百位排序的,而且呢,大家注意基数排序,它是一个稳定的排序方法,从我们算法可以看到。它总是按照这个顺序往桶里面放的,因此呢,呃,在前面的这个数据呢。
06:04
也一直是在前面对不对,在相同情况下,它总是放在前面的,所以说它是稳定排序法,这是第一点,第二点呢,我们给大家说了一下技术排序的基本思想是什么。也给同学们理到这个位置。它的基本思想就是刚才所说的,把所有数这个元数组里面最大的数找出来,然后第一位开始进行比较,如果较短的数呢,我们不离。就这样一个事思想,那这样思想过后呢,同学们理解起来比较困难,于是我们通过画图给大家讲解了一下它的流程,是不是技术排序的一个图文说明。图文说明我也给同学们整到,那么这个图文说明具体来说呢,我这个幻灯片是有这个图的,但是同时我们在Excel里面是不是也画过这个图啊,那干脆因为我们讲的时候是按这讲的,所以说我仍然把这个图给同学们截取过来好不好?这样呢大家就印象更加深刻。
07:06
这是我们的第一轮。第一轮它的这个结果是他是不是,然后呢,这个第一轮的它的方法呢,我这里总结的是第一步和第二步,先把第一轮放在这。没问题吧,同学们,这是我们的第一轮。OK,第一轮紧接着呢,我们做了第二轮的一个排序分析。是吧,第二轮处理过后呢,它是变成这个样子的。也给同学们挤过来。是这样一个情况,是不是在第一轮的基础上呢,继续我们第二轮的处理。是这样子吧,这第二轮,第二轮完了过后是不是我们还有第三轮。因为我们最这个案例里面最高位。最最大的一个数量一共有三位,因此它要有三轮排序。因为到百位了嘛。是这个道理,好就放过来,那这就是我们的一个图解,那有了图解过后,是不是我们就针对这个题呢,给各位同学用代码进行了实现。
08:10
是这样子的吧,好的,我把这个放到这里来,这是我们的要求,在讲的时候呢,我们先做了思路分析,就是前面的图文,然后呢,我们用代码给同学们实现一下,具体来说代码就是这边。我就把这个代码给各位朋友拷贝过来。放到我们的笔记中,便于大家复习。最后呢,我在这里总结了一下技术排序的特点,技术排序是对传统排序的一个扩展,所以说它的速度呢,的确是很快的。第二个呢,技术排序是经典的空间换时间的方法,占用内存较大,当海量数据排序时,有可能出现out of memory error是什么意思啊?就是内存不足。那么技术排序呢?它是一个稳定。所谓稳定排序,是指假定在待排序的记录列表中存在多个具有相同关键字的记录,也就是说具有相同的那个值。
09:09
那么这些记录的相对秩序不会变化,即如果在语言序列中有一个R和RR节相同,那么I在节前面,那么排序过后呢?仍然会保证R在R节的前面。只是。啊,只是只是只是就说你反正就是你你前面那在相同情况,你前面在前面的还在前面,在后面的还在后面,只是排序功能,它是一个有序的而已,明白所以说针对这种排序算法呢,我们称之为稳定的排序算法,否则就是不稳定的,什么意思呢?假如你原先有个数组。你原先数,比如说有个二有个一,呃,有个有个二这样子啊。比如说这有个数组是二,逗号一。是。一然后呢有个负二,等到这个排序完了过呢,这个一和这个一前后顺序不确定,这个就叫不稳定,如果你这个排序够相同,这个词排序过后,前面的这个还在前面,后面这个还在后面,那么就称之为稳定排序,好的,这是关于我们这一个技术排序的。
10:19
一个在说明,给同学们捋到这里来。截取。一个一个章节,好,那么这一块就是老师给大家讲的关于基数排序的内容,我们就说到这里,大家好好消化一下,最好自己能写一遍。关于基数排序算法,我们还要做一点说明,那么从上面的基数排序算法来看呢?如果我们是有负数的这种数组呢?我们就不要用基数排序来进行排序。为什么呢?大家想一想,如果你这里有一个负数,比如说负的啊118,那么这个时候通过我们上面的这一个算法,它会得到一个什么呢?下边为负数的这么一个桶。
11:11
对不对,那这个时候呢,数组就会越见,因此呢,在我们数组里面有负数的时候呢,咱们就不要用这个基数排序,那如果同学们说我就需要用基数排序,使用复数怎么办呢?那要对这个代码呢,进行进行一个改进,也比较简单,怎么做呢?你对负数的时候呢,需要对它求绝对值。第二个当拿到值取出的时候,要进行一个反转,对吧,所以说如果要支持负数,大家可以参考这样一个,呃,这样一个页面,这个页面呢,它阐述了技术排序复数的处理方案,大家可以去参考一下,但总体的思想呢,并没有什么太大的变化。OK,那关于技术排序这一块呢,的注意事项的补充,我们就先给大家聊到这里。
我来说两句