00:00
下面呢,我们来学一下C语言的排序,还有这个查找,那排序呢,我们重点讲一个冒泡排序,查找呢,我们讲两个,一个是顺序查找,一个是二分查找。我们先来看什么叫做排序,排序呢?也叫排序算法。也叫排序算法。排序指的是将一组数据第一指定的顺序进行排列的过程,就把它排列好。那么排序呢,分成两大类,一类呢叫内部排序,一类叫外部排序。所谓内部排序就是指将需要处理的所有数据加载到内部存储器,这个内部存储器就是我们所说的内存。哎,同学们看到这个内部存储器就是指的内存,就一次性的加载到内存。进行排序,还有一个呢,就是所谓的外部排序,外部排序呢,就是有时候我们这个数据量太大了,就非常非常大。
01:00
无法全部加载的内存中,需要借助外部存储进行排序的,我们把它称之为外部排序,对,那现在呢,我们来看第一种哈,我们就给他讲讲一种,重点讲一种就行了。冒泡排序,冒泡排序呢,它非常形象,它是通过对带比较的排序序从前到后,也就是说从下包下标较小的开始依次比较,然后呢,如果发现有逆序的交换,就像这个水泡一样,为什么管它叫冒泡呢?就好像水泡一样。把那个大的呃,往上或者是大的往下啊,这个这个根据你的实际情况,比如说水泡呢,就是这个大的水泡往上飘,小的水泡呢往下沉,对不对,就像冒泡一样,因为排序的过程中,各元素在不断的接近自己的位置,如果一趟比较下来没有交换呢,可以说明已经有序了。如果在这种情况下,我们可以来减少这个排序,好这下面这句话大家不太理解,我们待会再说,好吧,我们现在直接上案例。
02:05
给大家举一个案例,来说一下冒泡排序法的一个写法。那么假设现在我们有五个无序的数。有五个无序的数,分别是三,九,负一,十,负二,然后呢,要求用一个冒泡排序法将其排列成从小就写错了从小。诶,从小到大的一个有序序列,那现在呢,老师给大家分析一下这个冒泡的过程,好,我们以这个数字为例。现在呢,老师给大家分析一下这个顺序是什么样子的,来吧,这是我们一个原始的数组。原始数组。原始数组它长的是这样子的,好的,现在呢,我们看看冒泡排序排序。的一个过程。
03:02
第一步它要分成几轮排序啊,各位同学,它要分成几轮排序第一轮。第一轮。第一轮排序呢,它是这个样子的,听我说第一轮里面呢,先分第一个步骤,它首先呢,让。我我们假定这有这有两个指针,或者有两个箭头哈,两个箭头大家听我说。然后呢,我用不同的颜色来标识啊,这个颜色太太粗了。换这个颜色。他先让什么呢?他先让三和三和九进行比较。假,我们现在还得假定一个东西,就是假定我们是从从小到大。从小到大排序好吧,那三和九先比较,三和九比较呢,发现9比3大,因此呢不变化,所以第一轮这两个比较完了过后呢,并不交换,它仍然是三。
04:05
九。负一。十。负二没问题吧,那这个时候让这两个指标。让这两个箭头往后面移动,然后呢,再比较九和负一,看谁大,九比负一大,于是他们就交换,交换完了后呢,变成这个样子了。变成三。然后这边呢,负一,因为要交换嘛,九往后面挪十负二。OK,第这是第一轮里面的第二次排序啊,这个比较,然后呢,这个两个指针再往后面移动,让九和十进行比较,各位九和十比较谁大谁小啊,是不是十比较大,十比较大呢?OK,那这个时候不交换,于是第第第一轮里面的第三次比较完了过后呢,仍然是原来的这个顺序。对,然后这两个箭头继续往后面移动,让十和负二比较,显然十比负二大,于是呢,进行交换就变成什么呢?变成了三。
05:08
负一九,负20。大家看可以看到这时候大家有没有发现,当第一轮进行四次比较以后,进行四次比较以后,各位同学,我们的第一个最大的数就已经移动到最后移动到这儿了,就是说这个最大的数。就第一最就是说最大的数。就第一大的数啊,第一大的数就移动到,移动到哪里呢?移动到最后了。那紧接着呢,进行第二轮的排序,OK,那就第二轮呢,第二轮这个颜色我们还是用黑色的好吧,第二轮排序。那么第二轮排序咱们怎么处理呢?它是在这个基础上,就在第一轮,第一轮的最后这个数字上进行排序,那首先把这两个指针又移动到最前面。
06:08
看清楚这个库存,三和负一比较哪个大一点,三比较大,于是第二轮里面的第一次呢,三和负一比较。这是负一,这是三。然后呢,九负二,OK,十十这个地方不要动它了啊,十不能动了,然后呢,这个三就到这好,紧接着呢,把这个数,把这两个箭头往后面移动。三和九比较,三和九比较呢,三和9比3大,因此呢,不交换,于是还是负一。三。九。负20,那也就是说第二轮的第二次,第二轮的第二次比较呢,这个九移动到这个位置了,当然也就是说是你这个三和九不是原先就是这个位置吗?因为你比较过后,你才知道9比3大嘛,对不对,好紧接着让这两个箭头继续往后往后移动。
07:02
往后移动呢,九和负二进行比较,各位九和负二并行比较过后呢,九比负二要大,因此呢,移动三不动哈,然后是负二,九往后面移动一下,十动好,此时此刻大家看到我们第二个数,第二大的数又定位在。定位好了,也就是说第二轮呢,经过了三次比较,我们就把第二大的数。第二,大的数移动到这个适当的位置。是不是移动到适当的位置了,那么我们还要进行第三轮的比较来,也就说这个九已经定位了,不要再动了,后面再比较的时候呢,就比较前面三个数就行了,来继续往这边移动。又把它打到最前面去了,然后呢,进行第三轮的第就写了啊第三轮。第三轮排序,那么第三轮排序里面的第一次怎么办呢?仍然让负一跟三比较,谁大呢?显然三大,于是第三轮第一次完了过后呢,仍然是负一三。
08:07
二。OK 90。好,然后这两个呢,往后面移动,让三跟负二进行比较,让三和负二进行比较的话呢,同学们可以看到这是三比负二大因式,负一负二,三。90结束了,因为这个时候大家可以看到第三大的数我们也定位了,因为你后面没有必要再比较了,因为九和十已经在适当的位置,所以说经过第三轮的处理过后呢,我们第几啊,第三大的数也移动到了适当位置,没完,为什么没有完呢?因为你一共有五个数,你还得进行一轮比较,所以说第四轮呢。第四轮排序,第四轮排序呢,它仍然又把这两个箭头移动到最初始的位置,让负一跟负二比较,谁大呢?显然负一大,于是这边就进行一次比较,负二移动到前面负一。
09:07
对,然后呢,394,这时我们负一也就移动到适当的位置了,也就是说此时此刻我们第四大的数移动到了适当的位置。对第四大的数移动到适当的位置,那同学们问大家一个问题,还有必要进行第五轮的比较吗?没必要了,为什么呢?因为你一共有五个数。你有五个数,四个数已经找到适当的位置,那么最后剩下的这个数呢?自然就已经在他适当的位置了,因此排序结束。排序结束。好,各位同学,这个就是老师跟大家讲的冒泡排序的一个完整的过程,那现在呢,我们就需要把这个排序过程用什么呀,我们已经分析了过程。
10:02
分析了它的一个过程。这个过程其实就是我们的思路,那现在呢,我们要将这个思路干什么呢?写成代码。是不是我们写代码,我们做程序开发永远在做一件事情,分析过程,或者叫分析思路,然后形成代码,我们一直都是在做这个事情,没问题吧,同学们,好的,那既然如此,现在老师就把这一个分析过程用代码来呈现给大家,来打开我们的这个。这一个VS2010,我们来给大家跑一下。现在呢,老师写一段代码来走着,我们叫做bubble BU bbl bubble bubble,就是那个冒泡,So,对不对?八瘦,那现在呢,老跟跟上老师思路,我们来一起写一写。看怎么来实现这个功能呢,Include。然后呢,Std。
11:02
然后VO的我们的主函数。我们的主函数,然后呢,我把数组先拿过来,同学们,数组在哪里呢?各位朋友,诶,数组其实就是这一个,我们就以这个为例好不好?那数组我们写一个呗,叫int array。等于这个是不是可以用这种方式来初始化呀。好,现在跟上老师思路喽,跟上老师的思路,我们来完成第一轮。第一轮,诶这个是第一轮。的排序。各位同学,我们看第一轮排序的过程呢,其实一共有四次,而且呢,它每次都在不停的移动,所以说我先来写这么一个东西看看,看看老师能不能跟上老师思路啊,我先定一个解。第一个节。跟着老师思路哈,For循环。大家看你第一轮是不是一共整了四次啊,是不是一共四次,所以说我这边就可以写R减等于零,解小于四,结加加。
12:11
是不是吃?那么试测完了过后,是不是他每次都是在比较前面的,就是他每次他从第它它实际上是从这个和这两个数开始比较。如果他们呃,顺序呃,不是从小到大就交换。嗯,然后这个做完了之后,是不是再比较后面这两个,然后再比较这两个,再比较后面两个是不是这样子的,所以说老师就开始这样写了啊来我们呢,用一个临时变量来走一下。我要做一个临时变量T。这是一个临时。变量。临时变量,那老师怎么怎么写呢,大家看如果。就说我要写,如果前面的数,前面的数大于后面的数,就怎么样交换。
13:07
那写了if。怎么是前面数呢?显然就是结,结如果大于了结加一,结加一是不是代表后面这个数啊?如果这个条件成立,怎么样交换?哎,同学们,交换这两个数,这两个元素的值是不是很简单呀?怎么写啊?TRJ先保存到这里,RJ。等于二节加一能理解二瑞杰加一等于T是不是交换了?哎,这三句话是不是在交换呢?能看懂吗?好,那也就是说经过这一这一个的处理,第一轮我们就排序完毕了,能看懂吗?我们可以输出一下。输出。看看第。第一轮的这个排序后的情况,来吧,我们看看第一轮处理完了过后是个什么样子的,来整一个哈,咱们解等于零,解小于多少呢?一共有五个元素对不对?结加加。
14:13
一共有五个,就说你一共是有五个元素嘛,那么现在我们打出来看一下per f走起来我就直接输了哈,就是百分号D打个空格,然后呢,二位解能看懂不?应该能看懂哈,那为了好看呢,大给他掐一下没毛病,来,朋友们,我们先运我们先生成一下解决方案,看看OK否?看看是否OK,如果有问题,我们再调一调先。他现在正在生成解决方案。OK,没有问题,我运行一下。那运行这个结果我们发现,诶有没有发现跟我们想的是一样的呀,十是不是在后面了,也就是说它最后是三负一九负20,跟我这分析的完全一样,三负一九负20正确吧,第一轮就结束了,就第一轮咱们做的事情就已经搞定。
15:06
那么你这个第一轮做完了过后,你是不是还有第二轮呢?第二轮是不是咱们也要来完成一下,诶第二轮,第二轮大家想跟前面是不是非常像啊,诶非常像,所以说你其实是可以把这句话粘贴复制过来的,能理解吗?OK,但是有一个地方不一样,这是三你原先是进行了。进行了这么多次的比较。是不是你一共比较了几次,你第一轮是比较了四次,现在我们是第二轮是不是比较三,第二轮比较三次就可以了呀,因为这个十已经到位了嘛,所以说各位朋友,你这地方应该改成三。能理解不?诶诶,不对,是三号,原先是四,现在是三变成三,是不是再把这个代码走一圈就完事了呀,一模一样。对不对,好,所以说第,我们说第第二轮排序过后呢,它的情况我们也可以看到。
16:03
是不是,那为了好看呢,咱们是不是给他来一个换行啊F。来一个斜杠,我们说一下,这是第二轮的运行项。跑起来,诶,这个地方有问题,我们没有关闭。别关闭,是出问题了。好,这边他会,诶你看现在就正确了,你看第第一轮是不是把十放在最后了,第二轮是把九放在最后了呀,呃,放在第二适当的位置了吧,那以此类推,是不是还有我们的第三轮呢?各位朋友是不第三轮来写一个吧,第三轮是不是把这个地方换成二就可以了,各位朋友。是不是就完事了,这是第三轮结果,我们看第三轮对不对,跑起来。把这个关闭一下啊,第三轮走起来,看第三轮是不是把第三个最大的数放在了适当的位置呢?我们来拭目以待,诶,我们发现又OK,看三是不是在适当的位置了,来我们还要来进行最后一次第四轮。
17:07
第四轮走起来,第四轮。那第四轮的话呢,这个地方是不是写成一就可以了,其他不用变化来跑一下走各位跑起来就OK,那这时候呢,我们可以看到第四轮排序过后,这个结果呢,就已经到位了。各位还需要再来一次吗?不需要了,也就是说经过四轮过后,我们速度变成负二,负一,三九十。写完了,但是有一个问题,同学们,你现在只有只有五个数,那问题来了,假设将来我们这有很多要排序的呢?对不对,34,比如34 567或90等等,那各位同学,难道咱们就这么一轮一轮的写啊,肯定不现实啊,那大家看我们这是不是有规律啊,各位同学。
18:00
你想一想。你想想,假设我们还回到这个地方啊,同学们,你想你是不是这一段代码,这个排序的这个过程。和下面这个过程是不是几乎一样,只是这个在变化呀。那你为什么?不把它包起来呢?对,因为你第一轮的排序和第二轮排序,第三轮排序,第四轮排序其实大同小异,仅仅是这个量的一个变化是不是,所以各位同学。现在呢,我们找出规律了来,各位同学。因为每次每轮排序几乎几乎一样,因此我们可以使用for循环套用。或循环处理,怎么处理呢?大家看,假设这是这是第一轮的啊,各位同学我把这个复制过来。这是不是第一轮?哎,往下面拉过来,其实这个第一,这是我们的第一轮,但实际上这个动作呢,在下边就这个for循环,只要进行四次就可以了,所以说我何不这样写呢,我再定义一个I。
19:12
看清楚了I,然后呢,我写个I等于零,I小于几呢?是不是一共四次,所以说再写个四就可以了。因为你大的轮只有四次嘛,然后是I加加。是不是从这把整个这个for循环包起来。看懂了没有?对,但是这里面呢,大家有没有发现这个事呢,是在逐渐的减少。是不是第一轮咱们内存循环是四次,第二轮内存循环就变成三次了,第三第三轮内存循环变两次,第四轮内存循环变一次,说这个地方写是不合理了,怎么写呢?是不是四减I就可以了。为什么四减I可以,你看你第一次这个I进来是零,四减零还是四,第二轮进来这个ii变成一了。
20:04
那么四减一等于三,诶,以此类推完刚好合适,所以说其实我们下面的代码就可以完全的注销了。各位朋友你看。是不是非常简洁啊,你看。是不是我们这儿到此为止,这个就完全可以拿掉了?而只需要保留一个。双层循环就可以了,那这个循环对不对呢?对不对呢,我们可以把这个结果输出来给他看一下不就可以了吗?来,我们看一下最后的这个结果就行了啊,其他结果我不看了,看一下。这个循环结果以后,同学们看到。是不是最后来运行一下。是不是这这样一套用就简单很多了。那我们可以看到此时此刻这个结果呢,跟我们想的应该也是一样的,看负二负一三九十,我没有一次一次的打了啊,我是一次性的把,就是把这个循环处理完了过后,我再一次性的输出,这个相当于是排序后的。
21:05
排序后的结果。对不对,但是这么还有问题,大家有没有发现我们这个是呢,写的是死的。其实这个是是不是刚好等于数组的大小。它减去一个一呀,你五个元素减一嘛,因此咱们还有一个办法更简单,我们把数组的大小认识算出来,它就等于什么呢?Size of讲过吧,Size of,然后呢,Array包起来除以size of什么呢?可以了。是不是这个就是数组大小,哎,各位同学,这个大小是等于几啊,是不是等于五啊,那现在可不可以这样处理,同学们,我们。这换成一完事了,然后这边这个四应该换成什么呢。这个是应该换成什么?是换是不是换成are?减一再减I就可以了。
22:00
这样多方便呢,那这个时候我们验证一下代码对不对呢,跑起来。好,我们先看看一下用了这种比较灵活的方式处理是不是对的,来看一个。运起来看结果完全正确,那有些同学老师这有什么好处呢?大家看我现在再来整几个负11这么多,然后123。349,好,再来一个吧,9000再来一个负。这么多,哎,同学们看我这个数变多了,下面代码需要变化吗?不需要,因为我这个长度是灵活变化的,是是这个通过计算得到。对不对,通过那这样子就很方便了,那同学们看,这时我们一步到位。是不是非常的简单了,各位同学,你看现在这个结果应该跟我们想象的完全一样,我们看对诶不好意思啊。这个地方为什么报错了呢?哦,我没保存,好像刚才再看一下。
23:00
排序后。哦,我知道为什么了,是不是因为我输出的时候,这边固定只输出一个五肯定不对了,因为你现在呢,大小其实是这么大个这么多元素对不对,你那你输出的时候呢,也要相应的跟他变化一下对不对。所以这个时候再看这个结果就应该正确。你有多少个元素就显示多少个元素,看结果。看对不对哈,最小。完全是按照从小到大的顺序来排列的,那我问大家,如果要从从大到小应该怎么改?如果要从大到小,是不是把这个大于改成小于就可以了,也就是说如果前面的数小于,后面数才交换。这样子是不是那个小的就往后面沉了,你看我把这一改,同学们看,现在就变成了从小到大,而啊,原先是从小到大,现在是从大到小了。大的在最前面。是不是没问题吧,同学们,很简单,好,我还改回去,还改回,那最后呢,还有一个工作我们要做一下什么呢?你看啊,这个地方我们每次写一遍太麻烦了,是不是可以把它封装成一个函数呀?诶我们把它封装成函数好不好,这段代码我们就把它封装成函数来走起来把它卡了。
24:18
卡了卡了过后呢,我写一个函数写一个呃,冒泡。冒泡排序的函数。那老师这样写了啊VO。BUBU。Bub BU BB Le bubble sort,然后呢,你给我传一个数组过来。OK,然后我把代码呢扔进去就完事了。诶各位同学这样是不是更方便啊,以后你要排序把它传进去可以了,那么我们调用怎么调用呢?是不是这填一个8b BB le8什么呢?LG传句大家还记不记得我们宿主默认是什么传递地址传递。
25:01
或者传的指针是吧,是指针,那这样子的话,你这传的这个其实呢,在这里面会被修改,也就是说这边处理数组呢,其实就是处理的外面这个数组就完事了,好这少了一个十少代码就写完了,那么这个长度同学们长度呢,我们。对,在这个长度呢,我们在里面统计,外面还得要一个,不然的话不好处理,或者这样也行,我们在排序的时候呢,把这个数,把这个长度传进去也是可以的,这样子写我稍微改一下好不好,那这个我就把它拿出来,注意听。看到啊,这我接收一个数组的长度,然后在这边呢,我先统计这个长度,然后把这个长度呢,传给我们的这个BB shot,这样就更好了。是不是两边都可以用到,现在用的是函数来处理的啊来我们现在写一个叫函数。那调用排序使用的是函数。函数处理。
26:01
那我们看看这个结果是不是跟原先的一样呢,我这为了好看,我把这个再换一下。因为这样我能看到数据有变化吗?好运行,如果这个结果正确,说明我们前面写的都是正确的,否则我们就是错误,我们就要改了。这是。有问题对吧,我们看哪里问题在哪个地方,我们调一调就行了。我们来调试一下。哪里有问题呢?他说,杰没有声明过。哦,明白了,因为你现在你现在整个这个节是在这里边,所以说这如果要再用结的话呢,我们还得写一个,因为那是那变成局部变量了。是不是写成这样一个就可以了。再来。好,没有问题啊,咱们改一下就完了,这也不是什么大事,只要你的整个逻辑是正确的,代码就不会有问题。看排序后,现在我们用的是函数机制,负11,负二,负1394正确。那各位同学,关于我们这一个冒泡排序的一个过程,包括它代码的实现呢,老师就给大家讲完了,看看能否理解,尤其这边最重要的呢,就是要把这个过程搞清楚,你只要把过程搞清楚了,其他都不是事,代码呢,老师在写的时候有一个演变的过程,我先说的是第一轮怎么处理。
27:20
第二轮又怎么处理,第三轮又怎么处理,依次推推,最后呢,我们把这几几轮的这个东西呢,咱们想了一个办法,用一个双层for循环处理,这样呢就更加的灵活,对更加灵活好的,那同学们关于这一块我们就说到这里,关于冒泡内容我们就给大家讲解到这里,好吧,那现在呢,我们把讲的内容做一个简单的梳理,我们看一下冒泡我们是怎么讲的。这块我们讲什么,这块呢,我们讲的是排序和查找,是不是梳理一下各位同学,那我们做一个新的章节。放这里。排序和查找我们先给同学们说的是关于一个排序算法的介绍。
28:04
哎,就是做了一个介绍,什么叫做排序。那何为排序呢?A排序是这样一些内容。排序是这样说的,对吧。排序的一个分类,那排序说完了过后,是不是老师就直接给大家讲了一下冒泡排序。它的一个概念,冒泡排序。那什么是猫包排序呢?就这样子。冒泡排序。放这儿了哈。基本介绍。他这还有一个配了一个图片,这个图片我就不要了,然后呢,我们是不是对冒泡排序做了一个应用实例,并且呢,分析了它的过程,并用代码将其实现。来吧,这边是我们的冒泡排序的应用实例。应用实例,应用实例呢,然后这边有一个分析冒泡的过程,我把这个分析过程给他拿过来,分析过程就在这。
29:00
是不是这么几轮啊,我给他截一个图,因为这里面有不同的颜色。好,我把这个放过来哈,分成了几轮来处理的呢?这是我们的第一轮。第二问。第三轮。第四问,这是它的一个完整的分析过程。对,那分析过程完了过后呢,我们这边还有代码。是不是有了过程有代码呀,把代码呢,也给各位朋友放到这个位置板书过来,这是我们的冒泡排序代码实现。来,放一个小小的表格。各位关于冒泡排序呢,就给大家讲解到这里,大家好好的去消化一下。
我来说两句