本周又因为疫情闭组了,这周把以前的作品稍稍完善了一下,然后都拍成视频发到了哔哩哔哩上了,然后又把git看完了。本来这周是打算把前端基础进阶看完的,但是在看到JS十大排序算法是卡住了,十个题看了很长时间,刚开始在博客上看,在博客上看的时候搞不懂他是怎样排序的,看的挺吃力,然后在哔哩哔哩找了点视频看,算是把排序的运算过程明白了,但是个别的在用代码实现的时候还是有一些不明白,个别的一两个实在不想在死抠下去了,想在以后做题的时候在慢慢看吧。下面是我理解不到位的一种排序算法:
桶排序
桶排序是计数排序的优化版,原理都是一样的:分治法+空间换时间。
将数组进行分组,减少排序的数量,再对子数组进行排序,最后合并即可得到结果。
堆排序
在物理数据层的表示如下:
堆排序,是选择排序的优化版本,利用数据结构——树,对数据进行管理。
以大顶堆为例:
通过构建大顶堆
将堆顶的最大数拿出,与堆底的叶子节点进行交换
接着,树剪掉最大数的叶子
再对堆进行调整,重新变成大顶堆
返回步骤2,以此循环,直至取出所有数
构建大顶堆
从第一个非叶子节点开始,调整它所在的子树
调整下标1节点的子树后,向上继续调整它的父节点(下标0)所在的子树
最后,完成整个树的调整,构建好大顶堆。
逐个抽出堆顶最大值
堆顶数字与最末尾的叶子数字交换,抽出堆顶数字9。
此时,数字9位置固定下来,树剪掉9所在的叶子。然后,重新构建大顶堆。
大顶堆构建好后,继续抽出堆顶数字8,然后再次重新构建大顶堆。
最后,所有节点抽出完成,代表排序已完成