00:00
同学们,那下面呢,我们就来看具体的这些排序算法,我们先看第一个最常见的。排序叫冒泡排序。那么冒泡排序很多同学哈,嗯,都会,有些同学也听过,其实没不会的呢,大致也听过这个冒泡。冒泡排序呢,是我们一个最基本的排序。有些同学虽然会写,但是呢很容易忘,所以说这一次呢,你看老师在讲这个冒泡排序的时候呢,我们一步一步的把它推演过来。大家就印象非常深刻了。我们先来看冒泡排序的一个基本概念,冒泡排序叫BB sorting,它的基本思想是什么呢?我们来搂一圈,它是通过对待对待排序序列从前向后,就是从前面向后面,即从下标较小的元素开始,依次比较相邻的元素值,如果发现逆序则交换。什么叫逆序呢?
01:02
啊,就说比如说吧,你希望是从小到大。你希望是从小到大排,那么你发现你发现前面的大,后面的小,这个就叫逆序,反之亦然。那么就交换过后,就让这个值较大的元素呢,逐渐从前向后移动,就好像水泡一样,逐渐的向上走,对吧,这向上其实就代表我们向后。呃,那么这里面有一个小问题,就是冒泡排序,它设计一个优化,这个优化呢,我们后面再再回头说这个事啊,大家先听一耳朵,因为这个排这个在排序的过程中有一种可能。什么可能呢?就是各个元素不断的接近自己的位置。如果下一趟比较。比较下来一次都没经过交换,说明什么问题,说明我们这个数组已经有序了,这个时候呢,我们就可以设置一个标识位,对它进行优化,这个优化呢,我们在后面专门写一段代码来写啊这段。
02:01
啊,这里这里说的说的优化,优化可以在冒泡写完了以后再来完成冒泡排序,冒泡排序写完后。写好后再进行。OK,好,那么我们再看一个图解。大家看这个图解,这个图解呢,也是演示了一个冒泡排序的过程,比如说同学们看我这里有这么几个数据,35,八十八十六,二七等等,那他一共要经过几次排序呢?大家看我这一共有几个数据?对吧,我这一共有几个数据,看123456789,那么他这个一共九个数据,最终排成的效果是这样子的。对吧,好,那这样子我们我们把这这个呢,因为数据太多了,而且他这个第几趟没有写完,这个图没有写完,所以说我们干脆这样子,我们举一个,呃,一个相对数据比较少的数组,我们给大家图解一下,好吧,我们现在呢,举一个具体的案例来说明,冒泡这里有五个数据是放在一个数组里面的,我们看看。
03:15
我们通过图解的方式来给大家阐述一下冒泡排序算法是什么样子的,来吧,现在呢,我们打开Excel表。Excel表,我在这里写一句话啊,叫什么呢?就是啊,图解一下,图解冒泡冒泡排序算法。的一个过程。就是注意听哈,我们以图解的方式把这个冒泡排序呢,给大家聊一聊,好比如说现在呢,我们有一个数据了,我们看它是怎么来的,首先这有一个数组。这是这是我们的原始数组,看清楚了啊,这是原始有最初的原始数组。
04:02
那么原始数组我们冒泡排序怎么玩呢?大家看,先是第一趟。往这边挪一下啊,第一趟。第一趟排序,那第一趟排序它怎么排呢?同学们看它是这样子的先呢,他认为这里有两个索引指针,就两个两个两个索引。其实就是指向我们这个原始数组的下标对吧?好,他先第一趟排序,他做一件什么事情呢?大家看第一趟排序里面的第一个比较是先让三跟九比较。先让三跟九比较,如果发现3比9大,则交换,大家看3比9大吗三。和九相比,那么三没有大于九,因此呢并不交换,所以说第一趟完了过后。还是一个还是一个数组。那么。第二次比较会怎么办呢?他就在交换过后的数组上,让这两个索引往后移动。
05:07
比较九和负一。比较九和负一,那九和负一谁大谁小呢?显然九大于是发生交换,什么意思?就是说如果相邻的两个元素。啊,逆序它就交换,我们这儿写句话啊,如果相邻的。香林。相邻的元素逆序就交换。那现在同学们可以看到九和负一来说呢,九大因此交换,怎么交换呢?好,它就会这样子来处理。OK,因为时间关系呢,我就把这个复制过来,稍微改一下就行了,让九和负一进行交换,那么负一在前,九在后。理解好,这样做完了以后,这两个索引继续同时往后移动。OK,这时呢,它让九和十比较,同学们九和十谁大谁小,显然九没有十大,因此不发生交换,不发生交换呢,仍然会得到一个新的数组。
06:09
就相当于说这个数组。呃,在上次比较过后呢,仍然是这个样子,于是后面再继续移动,在下一移动过后的速度,再比较十和20谁大谁小,十和20谁大谁小,显然这个地方呢,也并不需要发生交换。因此。再下次得到的结果实际上跟上面一样。是这个意思吧。实际上跟下面这个是一样的,所以说这样子呢,第一第一趟排序过后。这个结果就完了,那紧接着第一趟排序完了以后呢,最大的这个数其实我们就确定下来了。大家看最大这个数是不是就确定下来了。那第二趟排序,注意听第二趟,第二趟排序,第二趟排序呢,其实就是在。
07:01
前面的这四个数组里面,再找到最大的移动过来。好,我们先来看一下第二段排序,它相当于说在上一个数组里面又移动,但是这个时候在排的时候呢,这两个索引就会移动到。数走在最前面,三和负一谁大谁小,显然三大于是发生交换。注意听啊,那这个时候相当于这个数组。会变成什么样子呢?好,这个数组就是三和负一交换,负一在前面,三在后面。然后呢,这两个索引。往后移动。往后移动,三和九谁大谁小,显然3比9小,因此不需要发生交换,于是诶,这个地方为什么啊?这个我们还是要用黑色的来说明。好,这是下一次,下次这个三和九呢并不交换,因此它和前面这个数组保持一致。
08:06
保持一致对吧,所以说这个时候呢,同学们看。这时啊,三和九不发生交换的话,继续往下面走。继续往下走,走过后呢,九和十进行比较,仍然不发生交换。不发生交换,不发生交换呢,仍然是这个数组,好,这时呢,同学们看下一个十。就是十这个数呢,又确定下来了,也就是说十和20这两个数就确定下来了。第二趟,第二趟完了过后,同学们,我们紧接着去看第三趟排序。第三趟,第三趟排序,第三趟排序我们怎么来看呢?同学们看。他呢,又在上一个数组的基础上进行比较。又把这两个索引移动到最前面,移动最前面让负一跟三比较谁大谁小,显然这个时候不需要交换,因为负一。
09:07
B3小,他满足从小到大的这么一个关系,只是我这个案例呢,同学们看我这个案例举的有点不好,就是刚好这个时候他已经,呃,刚好就已经有虚了。对不对,刚好已经有序了,但是实际上呢,呃,在这个过程中,它这个算法的比较他还是要走的,只是这个时候我们可以优化而已,好我们接着往下看啊,那第三道排序又把什么做一下呢?好现在呢,他把这一个。同学们。这个数组进行比较,比较完了,负一和负三,负三不发生交换,于是乎我们不动它。然后在这个基础上又往后面挪一下。是不是又挪一次?好诶,把这个移移移动错了啊,把上面这个指针移动到下面来,让三和九进行比较,三和九进行比较,同学们发现三和九比较呢,也不需要交换,于是它仍然是上次这一个。
10:09
数组的顺序理解吧。啊,上次这个数组的顺序OK,没有问题,但是这次比较比较完了,过这个九。也确定下来了。这个第三一个最大的数也就确定下来了,看清楚没有。OK,好,这次完了过后最后一趟排序了,最后一趟排序第题是呢,第四趟排序。第四趟排序。那第四段排序同学们有助于观察到它呢?仍然是在上一次数组的基础上进行比较,它比较负一和三谁大谁小。当然这个呢,也不需要交换,于是第四趟排序做一次,就把谁确定下来呢?把第四一个最大的数确定下来了。把这个拿下来,拿下来过后,我把这个保留原数据啊,这个三又确定下来了。
11:06
对不对?三确定下来过后,同学们看一下还需不需要第五一次排序。不需要。不需要第五次排序,为什么呢?因为你五个数据有四个数已经确定了,因此呢,没有必要进行D。五次排序,我们来总结一下,小结一下这个冒泡。诶,冒泡排序的一个呃,一个这个呃规则第一趟我们总结这么几个规则,大家看第一次。它的规则是这样子的。一共要进行几趟排序呢?一共要进行你的这个数组,你的数组大小减一次排序对不对,一共。一共进行数组。的大小。大小减一次。
12:02
这个大的大的这个循,大的这个循环。循环。也就是说我们认为第一张排序,第二张排序,第一张代排序,第四张排序,它是一个大的循环。OK,那现在呢,我们把这个总结出来,第二次,第二点我们有没有发现。我们有没有发现他每一趟排序的次数是在逐渐的减少?是不是说每一次,每一趟,每一趟排序的次数在逐渐的?逐渐的减少。减少。OK。OK,好,既然它在逐渐的减少,那么我们在处理的时候,我们在处理的时候呢,就要。有一个变量,再让它不断的减小就就可以了,好,同学们,这个思路,这个冒泡排序的一个思路,我们就分析完毕了。
13:01
那下面呢,有了思路,我们就用代码把这个实现一下,代码实现的时候干脆这样子,我们这个数据呢,设计的有点不好哈,我这样子待会呢,我们设计另外111组数据,呃,也是五个数,我把这个呃怎么整一下啊大。啊,小这是小的小的大的小的大的再来一个这个呢,我们来整一个更小一点的啊,比如说。来一个负。好吧,这样子呢,我们容易把这个过程看的更清楚,把这个过程看得清更清楚一点,好吧,就说呃,就是这样子看,就是小大小大小,对吧,这样子呢,待会我们在演示的过程中,大家可以看到演变的一个过程,而我刚才举的这个例子呢,刚好呃,它排在,其实它排在哪个位置的时候,就已经不需要变化了,其实你看他在这个位置的时候。
14:01
负一。就是第二趟的,第二趟排序里面的第一次,第二趟排序里面的这个第一次比较完毕过后,其实他已经是个从小到大的,后面做的这个工作呢,其实是没有意义的,但是从这个算法来看呢,你还得走一遍,只是我们可以优化,我把这句话也写进去。怎么写呢?就是如果我们发现,我们发现在某注意听啊在。发现在某趟某趟这个排序中没有发生,没有发生一次。这个交换。如果我们发现在某次排序中一次交换都没有,我们可以怎么样呢?可以,可以提前,可以提前结束。提前结束什么呀,结束这个冒泡排序。
15:03
冒泡排序,因为已经是有序的了。因为你在这一趟,其实大家看已经是个有序的了,既然他是一个有序的,那么他其实在后面就一他在他在这个一次大的这个循环里面,可能一次都不会发生变化啊,一次都不会交换,那么这个时候我们可以提前结束跑析,这个就叫优化。啊,这个就是优化,这个就是优化。优化。好,同学们这样子有了这个思路过后呢,我们下面就用代码把这个实现一把,把这个代码实现一表,好我们思路分析先讲到这里。
我来说两句