00:00
大家好,我是上硅谷H5学科讲师刘志远。在程序员将到来之际呢,给大家分享一道面试题,面试题的题目呢,叫做冒泡排序。默认排序呢,指的是在我们计算机当中的一种排序方式,那在JS当中呢,我们对数组的操作呢,会进行一些排序,比如说升序或降序的排列。好,那此时呢,我们先创建一个数组啊,VR来个AR。好,为了方便我们能直观的看清呢,在这里边的数呢,我就选择一个五,然后呢,4321啊这么几个数。好,下边我们要做的事情呢,将我们这个数字当中的元素呢,进行一个升序的排列,也就是说最后呢,应该是一个12345。那此时呢?我们应该让他们进行比较和交换位置。那此刻呢?我们利用画图的方式来给大家进行讲解。好,首先上来,我们在这里呢,有五。
01:02
四。三。二。一啊这么几个数。那下边呢,我们要想让他们进行一个比较和升序的排列呢,那第一步呢,我们要拿五跟四进行比较,对吧,好在这。好,那此时呢,五和四比较,如果五等于或小于四的时候呢,那这个时候呢是不动的,那只有当五大于四的时候呢,那这个时候呢,才需要交换,因为我们要比出一个最大值。最后要是一个升序排列,所以五和四进行交换。然后呢,五再和三进行比较,当五大于三的时候呢,五再和三进行交换。然后五呢,再和二比较,五大于二,哎,再和二交换。
02:01
好,最后呢,五是不是在跟一进行比较,此时呢,如果它比一大,诶再和一进行交换。所以我们刚才的比较完之后呢,我们可以认为啊,在这次比较当中,或者我们认为这一轮比较当中,我们已经找出了该数组当中的一个最大值。那我们发现一轮是不够的,因为4321它们之间还没有进行比较,还没有进行重新排列。啊,所以在这里呢,我们需要比较几轮。在这我先写上一个,这叫轮数。哎,这是轮数。好,那我们可以认为刚才我仅仅只聊了一轮。我在这儿写一个这事。Deal。好,第一轮。
03:03
好,那我们来看一看啊,刚才这一轮当中呢,我们一共比较了几次呢。是不是先是五跟四进行比较一次,然后呢四跟三。啊,然后五再跟三两次,五再跟二三次,五再跟一四次。那也就是说这一轮当中,我们比较了次数呢,是四次,所以在这呢,我们也记录一下。次数啊,刚才这是四次。好,那我们开始比较第二轮,那第二轮是不是和刚才差不太多呀啊。D。第二轮。好,第二轮比较的时候呢,是不是四先跟三比较呀啊4:3打交换,然后呢,这是四,然后四代跟二比较,比二大,跟二交换四,然后四再跟一比较,比一大,然后再交换四。
04:01
啊,那我们看当时啊,当前这个四还有没有必要再跟五比较了,没有了,因为他们第一轮的时候已经比较了一会了啊,所以在第二轮比较的时候呢,我们就不用跟五进行比较了,我们也可以认为在第二轮比较当中呢,我们已经找出了该数字当中的第二大值。对吧,第二大值,那刚才我们再回忆一下,我们比较了几次呢?在这里是不是就是三次了。比较了三次。好,那咱们再继续啊。呃,第二轮呢,比较完了还不够,我们今天找出了第一大跟第二大,还有321没有进行比较啊和进行排列的。好,第三轮开始。好,我这有一个D啊第三轮。第三轮那三跟二比较,比二大进行交换,二然后呢,这是三,三再跟一比较,比一大,然后进行交换,这是三。
05:01
好,此时呢,三没必要再跟四和五比较了,所以四和五呢,我们直接写下来。哎,那在这只表当中呢,我们比较了几次呢?是不是两次啊,三跟二,然后呢三再跟一,所以此时呢,我们第三轮的次数呢,是。两次。好,是两次。那在这次比赛当中呢,我们又找出了第三大值了。哎,那此刻呢,我们还剩二跟一,他们两个之间没有进行比较呢。所以呢,我们还需要再比较一轮啊,再比较一轮。那我这就写一个第四啊,第四轮第四轮那是不是就仅仅二跟一比较,哎,交换就完了,所以在最后一次角当中呢,我们已经把整个数字当中的。元素进行一个升序排列的完成。啊,所以我们把后边的都给它照抄三。
06:00
四。那我们可以认为在第四轮表当中呢,比较了几次呢,是不是一次。好,那通过啊,刚才我们的,呃,这个图形的讲解啊,那我们其实可以找到一些规律,首先啊,我们先看一看我们的元素一共有几个。元素元素的个数。元素的个数是不是我们说是五个呀。好,那这五个我们可不可以认为就是a.Les通过它可以知道元素的一个个数,对不对啊,元素的长度嘛。好,那还有一个就是轮数,我们看到一共比较几轮呢,四轮。那我们看是五个数,比较了四轮。那从这里呢,我们也可以得出一个规律或者一个公式,那比较的轮数呢,就是我们当前数组的长度呢,减一。
07:01
所以在这我再写一个。ar.les。减一啊,这是我们比较的人数。那在每一轮当中呢,我们比较次数呢,也都是不同的,那我们来看一下啊,这个次数,首先第一轮比较的是四次。那我们还可以跟谁挂钩呢?还可以跟我们元素的个数挂钩。那这个次数是不是就是a.Les。还是减一对吧,啊,这是四次那好啊。那在这儿我这么写行不行,我再减个零。哎,其实数字是没有变化的,或者说结果是没有变化的。我就先这么写啊,放在这儿,那我们再看第二轮啊,第二轮。是不是还是一个a.Les然后减一。好,这个时候呢,那我们是三四,那这应该减几了,是不是再减一个一啊。哎,没问题是吧,好,这是第二轮,然后呢,我们再看第三轮。
08:01
好,第三轮呢,那以此类推。比较了两次,那应该是a.Les。减一,减二。对不对,哎,四减二得二,那好还剩最后一个了,那最后一个呢,那我们不用说了,是不是a r.N4。减一,减三。好。那这个时候呢,那我们把它们之间的这一个关系,我们已经罗列清楚了,下边我们就可以开始来写了,好,那通过这个图形,或者通过我们刚才这个画图的方式呢,我们应该知道在。这里边儿啊,我们写的时候呢,肯定要需要一个嵌套循环。那也就是说呢,我们需要一个外循环来控制轮数,因为在每轮循环的里边呢,我们需要把每一个元素呢,进行一个多次的比较。哎,那所以呢,我们会有一个内循环来做比较的事情。
09:03
啊,外循环是来做每轮的事情。好,那下边我们就开始来写了。好,那我们刚才说了啊,那外循环是一个轮数。我只来写个for。VI等于零。然后呢,I小于小于什么ar.les减一对吧?哎,我们说这是元素的长度减一,这是我们比较的轮数,然后呢,I每次进行一个递增。好在这里边儿呢,我们再写一个什么呀,次数就是每一轮里边应该比较几次。啊,还是for where。好,我们别使I了,这应该是个这是吧?好,这等于什么?这还是开始,我们先给一个零。好,然后呢,这小于什么呀。我们看看啊,我们应该怎么写。
10:00
那我们刚才说了啊。这个次数啊,我们发现每一轮比较的次数呢,也是有规律的,都是长度啊,先是减零,然后减一,然后减二,然后减三,所以我们认为啊。J0123这三个数啊,这四个数。它们是一个可变的数。那我们通过谁能充当这个可变数呢?那我们看啊,那第一轮的时候,我们的Y循环是不是就是零呀,那个I是不是就是零呀,然后第二轮是不是就是一呀,第三轮是不是就二,第四轮是不是三呀。所以啊,我们可不可以认为啊,这个比较的次数呢,就是a.N减一减。好,那在这里边呢。我们这应该写一个G等于A点。减一减。好,然后呢。这我们再来个加价。
11:03
那好,那关于我们轮数跟次数这个倾倒循环就已经写好了。啊,那现在下边我们要做的事情,那是什么呢。在次数我们说这里边,那次数这个循环呢,我们是做一个比较,那应该是我们比如说第一个数跟第二数进行比较,只有第一个数比第二位数大的时候啊,才进行一个交换。然后呢,在依次的第二个数跟第三个数进行比较,是不是,哎,那大的情况下呢,再进行交换,那以此类推,所以在这里呢。那我们怎么来写呢?那肯定得用到一个判断是不是。好,我们这儿判断什么判断。判断前一个数,然后大于后一个。后一个数。十。
12:01
做什么进行?交换啊,进行值的一个交换,那我们就该这么写了,If括号好,A。中国号。这是不是,那我们元素的索引下标呢,是不是就从零开始啊。所以在这啊,是不是就是拿到这,然后这跟谁比啊,这和这加一比,是不是就是零加一是一方一加一是二,所以在这呢,我们应该这么写啊,当。I中括号J大于中括号G加一的时候,那此时呢?是不是才认为我们前一个数大于后一个数呢?那此时应该进行交换了吧?那我们交换两个变量的值又回到我们最基础的。是不是应该借助底层变量啊,所以在这儿我们写一个。啊,借助啊第三方啊变量。交换。
13:02
交换两个变量的值是不是,哎,那我们是不是定一个VRT是不是。好,Time等于什么,是不是就是哎,A,我们这写一个中括号J。对不对,然后呢,下边A中括号。J。等于什么?等于A中国号J加一。对不对,那此时最后呢,再把我们AR中括号J加一。再把temp复制给他,这时候就是不是实现我们的。交化了。那此时交换完以后啊,那我们把我们的数组呢,再重新打印一下,看此时是否进行一个顺序排列了。最后呢,Cancel dialog借助控制台日志来打印AR。
14:02
好保存呢,我们来运行一下啊走。F12。诶,此时呢,我们再刷一遍,我们发现是不是就是12345了,哎,那这次呢啊,我们就已经实现了,我们一个数组的以冒泡排序的方式,一个升序排列的,那此时呢,你可以把这边数呢,随便换一换啊,比如说我们来一个啊,比如说三啊三。32啊,这是这是。14这是比如说67啊,然后再来一个八八十二啊。这是21。好,再来一个11好不多写了,那只要能成功,那多少数都能成功啊,我们再刷一遍。哎,41 21 32,六十七八十二。诶,那以上呢,就是我们对冒泡排序的一个讲解啊。好,那我们的面试题讲到这儿。
我来说两句