网站建设 ui设计公司网页制作怎么下载

网站建设 ui设计公司,网页制作怎么下载,百度关键词优化平台,深圳知名的网站公司简介堆排序详解堆的简述堆排序概述堆排序的树状结构下标访问的前提准备建堆过程排序与调整过程堆排序的具体实现交换函数调整堆结构函数调用堆调整的排序主函数最后一个有子节点的父节点的下标关系小结堆的简述 堆是一种完全二叉树#xff0c;并且满足#xff1a; 大根堆每个节点…堆排序详解堆的简述堆排序概述堆排序的树状结构下标访问的前提准备建堆过程排序与调整过程堆排序的具体实现交换函数调整堆结构函数调用堆调整的排序主函数最后一个有子节点的父节点的下标关系小结堆的简述堆是一种完全二叉树并且满足大根堆每个节点上的值大于等于它左右两个节点上的值小根堆每个节点上的值小于等于它左右两个节点上的值堆排序概述堆排序顾名思义是使用“堆”这种数据结构的思想快速地访问数组中最大的元素并且以类似二分的方式维护最大值的一种排序方式堆排序并非使用了堆这个数据结构而是使用数组来实现用下标来维护对应二叉树的性质堆排序的树状结构下标访问的前提准备前面我们提到堆排序使用数组模拟出二叉树的效果那么我们必须拥有能通过父节点快速访问它的两个子节点的手段由于我们是访问下标所以需要通过下标来访问具体公式如下l c h i l d f a t h e r ∗ 2 1 lchild father * 2 1lchildfather∗21r c h i l d f a t h e r ∗ 2 2 rchild father * 2 2rchildfather∗22具体推导见下建堆过程由于前面给出了父子节点之间的下标关系所以我们可以用二叉树的性质对它进行操作第一步我们应该先把这个数组调整成一个堆的形式这时候就要用到向下调整也就是说在原本的数组中如果将下标0节点看作根节点如果直接将整个数组当作大根堆来使用可能会出现父节点小于子节点的情况所以要从下向上的让每一层的子树都能够满足大根堆的性质排序与调整过程上一步我们已经将数组调整成一个最大堆也就是说数组下标为0的数已经是最大值了。这一步为了排序我们需要将最前面的数取出来但是为了根节点0下标处有值于是我们可以选择将0节点与当前堆的最后一个数交换然后由于取出来了一个数将数组大小缩小1此时的最大值也恰好来到了最后一个元素的位置反复进行之后数组自然而然完成了从小到大的排序堆排序的具体实现根据上面所说的几个需求我们写出对应的函数最终拼装在一起就是最终的排序函数交换函数这个函数我们希望交换数组的两个值直接写成传地址的函数对地址直接修改】voidswap(int*a,int*b){inttemp*a;*a*b;*btemp;}调整堆结构函数详细解释放在注释中voidhepify(int*nums,intsize,inttar){//这里的nums是待排序数组size是逻辑上的堆排序长度tar是待调整的子树的根节点下标intlchildtar*21;// 左子节点下标intrighttar*22;//右子节点下标intmaxtar;//记录一下左右子节点中有可能的最大值的下标if(lchildsizenums[lchild]nums[max]){maxlchild;//如果该节点拥有子节点并且这个字节点的值比当前的max大时就更新max为这个值}if(rchildsizenums[rchild]nums[max]){maxrchild;//同理如果右子节点存在并且值大于当前被更新过的最大值下标的对应值的时候更新最大值为右子节点}if(max!tar){//这一步是判断左右子结点中是否有比父节点大的值存在如果有那么上面的两个if语句会更新max让其不等于tar进入之后先交换父节点与该节点swap(nums[max],nums[tar]);//此时逻辑上的父节点已经被更新为了两个子节点中的较大值并且父节点也被调整到了子结点上heapify(max);//但是由于被调整下去的父节点也会作为别人的父节点继续干扰大根堆的性质所以还得对被调整下去的节点进行第二次调整此时我们就可以递归地调用函数直到最后的节点符合堆的性质或者说没有子节点为止}}调用堆调整的排序主函数先在原数组的基础上建堆对一个建好的堆和刚刚说的一样要将它的0下标数与当前堆的最后一个数交换然后长度减一最后一个有子节点的父节点的下标关系前面提到过需要先找到最后一个有子节点的父节点的下标然后从这个下标开始逐个向前进行调整我们前面推到过l c h i l d f a t h e r ∗ 2 1 lchild father * 2 1lchildfather∗21r c h i l d f a t h e r ∗ 2 2 rchild father * 2 2rchildfather∗22如果将lchild或者rchild减一再除以二就会得到f a t h e r 和 f a t h e r 0.5 father 和 father 0.5father和father0.5由于整数除法直接作截断所以无论左右子节点减一再除以二都能得到父节点的下标即f a t h e r ( l c h i l d − 1 ) / 2 ( r c h i l d − 1 ) / 2 father (lchild - 1) / 2 (rchild - 1) / 2father(lchild−1)/2(rchild−1)/2并且由于数组0下标也会有数所以要在左右子节点下标基础上减一也就是( c h i l d − 2 ) / 2 (child - 2) / 2(child−2)/2这就是调整堆结构时的起始下标voidheapSort(int*nums,intsize){for(intisize/2-1;i0;i--){//从第一个父节点开始向上挨个调整为堆结构heapify(nums,size,i);}for(intin-1;i0;i--){//从数组最后一个数的下标开始将最后一位和0下标处交换然后缩小数组大小i—-swap(nums[0],nums[i]);heapify(nums,i,0);//每次交换之后根节点变成最小值不符合最大堆结构所以要再对数组第一个数进行排序//由于数组大小在逻辑上一经减一了所以要传入此时i即为数组大小}}小结堆排序是一种利用数组搭建在逻辑上满足堆性质从而快速访问最大最小值的排序方式堆排序实质上是一种被优化过的插入排序时间复杂度也降低到了O ( N l o g N ) O(NlogN)O(NlogN)与归并排序快速排序一同在实践中大量使用