堆
每次都比较父亲和父亲是否比父亲大,大的就换,然后比原来的父母级和现在的父母级大的就换,这一直是一大堆萝卜。 下图中的列子(heapsize此处记录的当前个数) )。
如下图删除最大的6时,首先记录6,然后将最后的公式4移动到最上面的位置,也就是0的位置,选择左边孩子和右边孩子中最大的一个,换0,比如水果大的话。 如果下面还有数字,则选择左边的子代和右边的子代最大和父亲进行比较,重复操作直到父亲的数量大于左边的子代和右边的子代。
如下图的列所示
首先删除9,将1的位置改为9的位置,然后用标记的hs间断更换后,与9交换数组关系。 然后,我知道左边的孩子和右边的孩子选择最大的和1换成比他大的,有没有左右的孩子,或者比左右的孩子大。
代码如下所示
whlie判断是否有左边的孩子,或者下面是否有孩子
下一个largest的left 1即是否有孩子heapSize是否有右边的孩子右边的孩子比左边的孩子大如果为true,left 1即右边的孩子代入largest如果不合适,left就会代入largest。
接下来父亲和大孩子之间谁大,下表给largesat
if语句是指确定是否与父代值相同,如果相同,则退出循环
swap交换largesat下标和索引下标
最后,left返回到初始状态
复杂性
1节点为1高,2节点和3节点即2高,3.4.5.6.7节点即3高
如果是数组的右n个数据即节点,则他的复杂度也是0(logn )水平
上图删除最大数,让他成为大根山,只接触经历过的节点,其余的不碰。 这样,他的复杂度也就是o(Logn )水平
堆栈排序
上图先删除最大数量,然后更换为最后一个数量,再删除heapsize最大数量和数组之间的连接,然后与左右孩子进行比较,直到该数量下没有孩子或大于左右孩子,删除最大数量和最后一个数量的交换,依此类推
上面的图中,因为假设有2N个后复杂的丈夫logN,所以整个代码的复杂度为0(nlogn ),额外的空间复杂度为o )1)
如上图所示,一次给定所有数据时,从最后一点开始检查heaoify,但是因为左右的孩子不在,所以从下跳到第二个也一样。 因此,代表现在按顺序排列。 然后,到由3个节点组成的小树heaoify,左右的孩子要求较大的一方与这个父亲进行比较,就可以交换了。 这也保证了现在小树的顺序,这样可以得到和后面的大树同样的效果。
换个for就行了。 只是单纯地做萝卜山,用这个会快一点
拿出后面的数往前推
重要:如上图如果你在系统堆里改一个已经排好的大根堆修改一个数据,系统的堆回去一个个扫描会影响效率,这个时候只能自己手写的堆才能掌控你什么地方改了就从那个地方开始heaoify
上图是主题的解答
比较器升序
降序
自己添加比较器,把黑匣子变成一堆大根
桶排序数排序
因为是年龄数组,计算年龄为0~200岁,所以制作201个容器,下标表示年龄数据代表个数,也就是说表示原始数组计算个数,所以时间的复杂度为0(n ),如果年龄不是很大的范围,就不理智,所以不继续比较的排序是
基础排序
[72、13、25、100、17]然后查看十进制数并计算位数的补充。 也就是说,为[ 072,013,025,100,017 ]。 然后,按照最后一位数放入桶中,取出,先出来
然后每10位数放入桶中
然后每百位数装一桶,按基数排序还是要看数据情况。 这种情况意味着数据有进位的限制
maxbits是找到最大值
最大=系统最小
然后遍历找到最大值
最大值/10 res个数为最大值的十进制比特有几个
digit表示此批处理中的最大值具有几个十进制位
radix表示10是基础
类推,如果下一个for:d为1,则取出一个位,如果为2,则取出一百位
下一个fot :表示下标
下一个for :数组从右到左遍历每个数,根据来的第几个来检索该位数,用count-1填充数组,然后-这是桶
下一个for:bucket数的子代被导入到arr中,就相当于维持这次桶赛的结果,等待下一个桶赛变成桶赛