自助建站 源码,如何给局域网 做网站,泰国清迈房产网站大全,湛江企业自助建站系统这篇文章主要为大家详细介绍了PHP实现排序堆排序(Heap Sort)算法#xff0c;具有一定的参考价值#xff0c;感兴趣的小伙伴们可以参考一下算法引进#xff1a;在这里我直接引用《大话数据结构》里面的开头#xff1a;在前面讲到 简单选择排序 #xff0c;它在待排序的 n 个…这篇文章主要为大家详细介绍了PHP实现排序堆排序(Heap Sort)算法具有一定的参考价值感兴趣的小伙伴们可以参考一下算法引进在这里我直接引用《大话数据结构》里面的开头在前面讲到 简单选择排序 它在待排序的 n 个记录中选择一个最小的记录需要比较 n - 1 次本来这也可以理解查找第一个数据需要比较这么多次是正常的否则如何知道他是最小的记录。可惜的是这样的操作并没有把每一趟的比较结果保存下来在后一趟的比较重有许多比较在前一趟已经做过了但由于前一趟排序时未保存这些比较结果所以后一趟排序时又重复执行了这些比较操作因而记录的比较次数较多。如果可以做到每次在选择到最小记录的同时并根据比较结果对其他记录做出相应的调整那样排序的总体效率就会非常高了。而堆排序就是对简单选择排序进行的一种改进这种改进的效果是非常明显的。基本思想在介绍堆排序之前我们先来介绍一下堆《大话数据结构》里的定义堆 是具有下列性质的完全二叉树每个节点的值都大于或等于其左右孩子节点的值成为大顶堆(大根堆)或者每个节点的值都小于或等于其左右节点的值成为小顶堆(小根堆)。当时我在看到这里的时候也对有“堆是否是完全二叉树”有过疑问网上也有说不是完全二叉树的但是无论堆是不是完全二叉树尚且保留意见。我们只要知道在这里我们采用完全二叉树形式的大根堆(小跟堆)主要是为了方便存储和计算(后面我们会看到带来的便利)。堆排序算法堆排序就是利用堆(假设利用大根堆)进行排序的方法它的基本思想是将待排序的序列构造成一个大根堆。此时整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换此时末尾元素就是最大值)然后将剩余的 n - 1 个序列重新构造成一个堆这样就会得到 n 个元素中的次小的值。如此反复执行便能得到一个有序序列了。大根堆排序算法的基本操作①建堆建堆是不断调整堆的过程从 len/2 处开始调整一直到第一个节点此处 len 是堆中元素的个数。建堆的过程是线性的过程从 len/2 到 0 处一直调用调整堆的过程相当于 o(h1) o(h2) … o(hlen/2) 其中 h 表示节点的深度 len/2 表示节点的个数这是一个求和的过程结果是线性的 O(n)。②调整堆调整堆在构建堆的过程中会用到而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点 left(i) , right(i)选出三者最大(或者最小)者如果最大(小)值不是节点i而是它的一个孩子节点那边交互节点i和该节点然后再调用调整堆过程这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系是 lgn 的操作因为是沿着深度方向进行调整的。③堆排序堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)将前面 len-1 个节点继续进行堆调整的过程然后再将根节点取出这样一直到所有节点都取出。堆排序过程的时间复杂度是 O(nlgn)。因为建堆的时间复杂度是 O(n)(调用一次)调整堆的时间复杂度是 lgn调用了 n-1 次所以堆排序的时间复杂度是 O(nlgn)。在这个过程中是需要大量的图示才能看的明白的但是我懒。。。。。。算法实现//堆排序(对简单选择排序的改进)function swap(array $arr,$a,$b){$temp $arr[$a];$arr[$a] $arr[$b];$arr[$b] $temp;}//调整 $arr[$start]的关键字使$arr[$start]、$arr[$start1]、、、$arr[$end]成为一个大根堆(根节点最大的完全二叉树)//注意这里节点 s 的左右孩子是 2*s 1 和 2*s2 (数组开始下标为 0 时)function HeapAdjust(array $arr,$start,$end){$temp $arr[$start];//沿关键字较大的孩子节点向下筛选//左右孩子计算(我这里数组开始下标识 0)//左孩子2 * $start 1右孩子2 * $start 2for($j 2 * $start 1;$j $end;$j 2 * $j 1){if($j ! $end $arr[$j] $arr[$j 1]){$j ; //转化为右孩子}if($temp $arr[$j]){break; //已经满足大根堆}//将根节点设置为子节点的较大值$arr[$start] $arr[$j];//继续往下$start $j;}$arr[$start] $temp;}function HeapSort(array $arr){$count count($arr);//先将数组构造成大根堆(由于是完全二叉树所以这里用floor($count/2)-1下标小于或等于这数的节点都是有孩子的节点)for($i floor($count / 2) - 1;$i 0;$i --){HeapAdjust($arr,$i,$count);}for($i $count - 1;$i 0;$i --){//将堆顶元素与最后一个元素交换获取到最大元素(交换后的最后一个元素)将最大元素放到数组末尾swap($arr,0,$i);//经过交换将最后一个元素(最大元素)脱离大根堆并将未经排序的新树($arr[0...$i-1])重新调整为大根堆HeapAdjust($arr,0,$i - 1);}}$arr array(9,1,5,8,3,7,4,6,2);HeapSort($arr);var_dump($arr);时间复杂度分析它的运行时间只要是消耗在初始构建对和在重建堆屎的反复筛选上。总体上来说堆排序的时间复杂度是 O(nlogn)。由于堆排序对原始记录的排序状态并不敏感因此它无论是最好、最差和平均时间复杂度都是 O(nlogn)。这在性能上显然要远远好于冒泡、简单选择、直接插入的 O(n^2) 的时间复杂度了。堆排序是一种不稳定排序方法。本篇博客参考自《大话数据结构》在此仅作记录方便以后查阅大神勿喷您可能感兴趣的文章:
