00:00
各位,我们下面呢,来给大家介绍一下堆排序的它的一个思想和它的步骤。那堆排序它是怎么来玩的呢?可以看到。堆排序的基本思想是这样子的,将待排序的序列先构建成一个大顶堆。注意这个大理论在构建的时候呢,是构建成了一个数组啊,大家知道这个地方啊,也就是说我们在进行这个堆排序的时候呢,你会发现我根本就没有创建数。那不要说,哎韩老师你不说那个刚才那个用堆排序,怎么没有看到你创建创建一棵二叉树呢,没有,因为我们现在是用这这个把这个数注意听,把这个数呢,是以数组的形式来存放的,因为我们前面讲过。就是什么呀,我们讲过顺序存储二叉树,明白我意思吧,也就是说在整个过程中,我们其实都是对在对数组进行操作,但这个数组操作的时候呢,是以这种大顶堆和小顶堆这种规则来进行操作的,就好像前面我们顺序存储二叉树,我们其实是。
01:07
把数据放在数组里边的,但是我们在遍历的时候呢,我们是按照数的形式,而二叉树的某种遍历方式来遍历的,是不是这样子的,所以大家不要说诶后面我们怎么没有看到数,因为我讲了数和数组它本身就可以相互转换是样子的吧。所以说待会儿呢,我们先将待排序的序列构建成一个大底堆,这是第一步,此时这整个我我这个换一个颜色。此时整个序列的最大值呢,就是堆顶的根节点。也就是说,我们会把这个根最大值放在堆零。将其与末尾元素进行交换,此时末尾就是最大值,那么末尾这个最大值呢,相当于说我这有个数组。我这有个数组,我先把最大值放在末尾,那这个数组呢,就抛出去了,然后呢再对。
02:04
前面三个数继继续进行我们这样一个操作,明白吧,你看这写的,然后将剩余的N减一个元素重新构建成一个。这个堆当然也是大整堆了啊呃,这样呢就会得到N减N减一个元素的次小值,如果反复的执行,那么我们就能得到一个有序有序序列了,就说我每排一次就把这个最大的值堆到这个堆到这个堆顶,然后呢,把它放在我们数组的最后啊,以此类推,最后呢,我们就看到可以看到在构建大顶堆的过程中,元素的个数逐渐减少,最后就得到一个有序序列了。大家明白这意思吧,我相信我这样讲的过大家一脸茫然,不知道老师在说什么,因为确实太抽象了。我说了1234,说实话你不知道我在说什么,这样子为了让大家理解堆排序的思想呢?我们看一个图解,而且举一个实际的例子,大家就会更形象的来理解堆排序的步骤好不好?我们看一个图吧。
03:06
比如说现在我有个数组,四六、八、五、九,一共有几个数,五个数,现在我们要求用堆排序将数组进行升序排列,所以升序就是从小到大。那同学们现在呢,我们打开这个堆排序的。图解步骤的图解,打开它,我们来一起看一看。嗯,同学们看啊,呃,我们我们这个数组刚才老师已经讲了,它原始的数组是。我在写一下。它原始的数组,注意听。哎。原始的。原始的这个数组它是这样子的,是不是是是。六。八。五九明白意思吧,46859。那么这个456859,如果这个形式对应我们一个数来讲的话,假设我们这个是一个数组,如果对应一个数来讲,是不是按这样存放的,46859,这个没问题吧。
04:14
好,那也就是说现在呢,我们这棵树对应的数组就是46859好。第一个我们应该很好理解,那下面呢,此时我们从最后一个非叶子节点开始。各位同学,哪一个,哪一个是最后一个非叶子节点?而且他要求是从左至右,从上至下进行调整,我问大家哪一个是最后一个非液体点,如果从左边开始来计算的话,是个六。是不是六就是我们最后一个非叶子节点?那它怎么算到这个值的呢?是r.N除以二再减一个一,就是我们最后这个非叶子节点。
05:00
那么最后这个非S点四六的话,他怎么做呢?大家看它是这样做的。他怎样做呢,大家看。从左从左至右,从上至下进行调整,大家他他发现什么呢?诶,他发现这个六它的左右注意看啊,他的他发现它像它会让这个六这个节点跟它的左指节点和右指节点进行比较。他发现什么呢?他发现右子节点,注意听这句话啊,每句话待会我们都有代码对应的,他发现右子节点。他发现右子节点是大于它的左子节点的,于是呢,他就让右子节点的这个节点的值跟它的这个。这个非叶子节点,也也就是他的负节点进行交换,就变成了这样一个东西。就变成这样一个数组,那这个这个数对应这个数呢,它对应的数组也就发生了变化,变成了四看49856,是不是这个数变呢,那你这个数组呢,也相对的相应的变化。
06:03
其实你整个操作的过程是整个操作的过程中,其实一直是在操作这个数,呃,操作这个数组。但是呢,我们为了理解这个最大顶堆和小顶堆呢,给它画了一个这个数组对应的那个图,明白我的意思吧,对应的那个数好第一步就做完了,那紧接着看再找到第二一个非叶子节点,各位同学,第二个非叶子节点是哪一个,是不是就是四啊?因为非X节点,你刚才这个六已经处理过了,那下一个非节点就是四,那又怎么办呢?大家看这个时候由于498中的九是最大的,所以说四和九就直接交换。那一交换过后,又造成一个新的问题。什么问题呢?就是你交换完了后,就意味着你这个地方还要进行一个调整,为什么呢?因为你交换完完了过后导致它的左指数。左指数就是456结构混乱了,因为这个时候它不再是一个。
07:04
大顶堆了是不是这样子的,那怎么办呢?让456中的六。跟这个交换又变成什么呢?就在这就在上面这个基础上啊,就变这个图,这个图就变成了让六和四交换。发到这个。好,到这一步的时候呢,我们就得到了一个大顶椎,为什么这个八不用调整呢?八它不是一个非叶子节点。是不是它不是一个非E节点,好,咱们这就不用去调整它。好,这就拿到一个大顶堆,原大顶堆,当然你在你刚才在进行这个把这个酒拎上去的时候,再调整这个酒的时候,其实你你是做了一个比较的,你是你发现这个这个九是比八大的,所以说你没没有交换,只是我这个图没有体现出来啊,说老师为什么九和八不比较,因为他在把这个把这个九拎上去的时候再调整。这个这个。呃,就是调整第二一个非节点的时候,他其实已经也像刚才那样做了一个比较发现呢。
08:06
这个八并不大于九,所以它不会交换,明白吧。好,呃,那么第二步干什么呢?刚才前面讲的其实就是一个。其实就是一个调整的过程,就把它调成一个大顶堆,第二步呢,将堆顶元素注意听,将堆顶这个元素和末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换得到第二大元素,然后反复的进行交换,重建交换。那么我们举个例子,比如说刚才这个九,刚才你已经得到一个大顶堆了,这个大顶堆它会让这个酒。和他最后这个四进交换得到了一个什么呢?得到了这样一个数,就是它是96854,这是大顶堆,大顶堆交换完了过后是拧到上面去了,九拿到下面,那拎到上面去过后,它对应的这个数组呢,这个九也就是最大的了,此时此刻大家有没有看到这个图呢?把这个九画成了虚线,就离开了我们这个数组,也就是说下一次我们在工作呢,只是针对。
09:13
这四个数。进行刚才的一个重复交换的一个过程。也就是说重新调整结构,使其继续定义啊,定义满足一个对,也就这个时候调整呢,只是只会去调整。4685。4685好,那你看调整的时候,你看这调整的时候,它这个酒就就不会再去动它了,不去动它,不去动它的话呢,其实就是对哪一部分呢。对,这几个数。进行调整。调整仍然是按照刚才那个流程来走好,还是按照刚才那个流程来走好,最后呃,调整完了过后就变成什么样子,看啊,他这说了,再将堆顶的八与末尾五进行交换,得到第二大版元素,你看这最后把八也放到这个位置了。
10:00
这个时候八和九其实已经是呃已已经是按照他的要求来存放了,好,最后依次不停的反复交换,最后就变成了一个呃,一个一个,就是按照从小到大心序排列的一个数组。看到没有,它就是这样子的一个过程,那么这里我再简单的总结一下堆排序的基本思路啊,大家不要着急,你现在听到这呢,肯定只是听到一个概念,待会我们走代码。把每一个代码给他写一遍,抄一遍,大家就更深刻的理解了,我我再简单的总结一下堆排序的思路,其实他的思路呢,大体来说就是三步,第一步将无序序列先构建成第一个堆,就是第一步先把它构建成一个堆。就是构建成一个什么呢?大顶堆或者是小顶堆,当然你构建成大顶堆还是小顶堆,要根据你是升序还是降序的需求来确定,比如说你是希望把这个数组做成一个升序的,那么就应该构建大顶,对。
11:01
如果你是要把这个数组按照从大到小排列,那你就应该构建一个小顶堆,那刚才那个顺序我讲的是大顶堆,小小顶队,就很好理解了吗?就把那个大雨和小雨互换一下就行。好,这是第一步要做的事情,第一步做完了以后呢,第二步将堆顶元素与末尾元素交换,将最大的元素乘到数组的末端。好,第三一步,重新调整结构,使它满足这个定义,然后继续交换堆顶和当前末尾元素,反复执行交换,也就是说其实说的再直接一点,其实它是分成了两大步,这是第一步。首先先把你这一个无序序列构建成一个堆,这个堆或者是大顶堆或者小顶堆。第二步其实就是这个过程的一个循环。是不是就说你下面在做的事情呢,就是交换调整,再交换,再调整,也就是说实际上你整个大堆排序分成了两个大的部分,一个是第一步,先上来调整一个大顶堆,后面就是一个反复的交换,交换完了过后再调整,调整完了再交换。
12:10
一直推推,最后到什么时候呢?把所有的数都搞定以后,咱们就退出这个循环,所以说从这个分析,你们有没有发现堆排序其实完全可以不用递归。他其实可以不用丢,完全是循环就可以搞定。好,同学们,呃,这个时候呢,我相信有些同学呃,应该还是不太清楚老师在说什么,但是大体呢,知道一点哦,好像是是在说我们以这个顺序存储数组的形式,然后呢,以这种大顶堆或者是小顶堆的思想来操作这个数组,是这样是吧。啊,就说这个这个过程中是没有看到数的啊,没有看到数的,然后呢,操作的时候呢,大体分成两大步,一个是先构建成一个大顶堆,然后呢,反复的进行二三的一个循环,最后就形成一个有序序列,好如果你明白到这里呢,也就可以了,下面呢,我们用代码把刚才大家看到这个图,就以这个案例一步一步的给他敲出代码,然后大家呢。
13:11
应该很快就能理解,因为这个走代码可能理解的会更清晰一些,思路就是个大概的东西,理解了就可以。好同学们那关于堆排序的思路和它的步骤图解先给同学们聊到这,待会呢,这个图我还我还有用,好好这一讲我们先聊到这里。
我来说两句