• 售前

  • 售后

热门帖子
入门百科

PHP排序算法之堆排序(Heap Sort)实例详解

[复制链接]
123457297 显示全部楼层 发表于 2021-10-25 19:35:37 |阅读模式 打印 上一主题 下一主题
本文实例报告了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)。
在这个过程中是须要大量的图示才能看的明白的,但是我懒。。。。。。
算法实现:
  1. <?php
  2. //堆排序(对简单选择排序的改进)
  3. function swap(array &$arr,$a,$b){
  4.   $temp = $arr[$a];
  5.   $arr[$a] = $arr[$b];
  6.   $arr[$b] = $temp;
  7. }
  8. //调整 $arr[$start]的关键字,使$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆(根节点最大的完全二叉树)
  9. //注意这里节点 s 的左右孩子是 2*s + 1 和 2*s+2 (数组开始下标为 0 时)
  10. function HeapAdjust(array &$arr,$start,$end){
  11.   $temp = $arr[$start];
  12.   //沿关键字较大的孩子节点向下筛选
  13.   //左右孩子计算(我这里数组开始下标识 0)
  14.   //左孩子2 * $start + 1,右孩子2 * $start + 2
  15.   for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){
  16.     if($j != $end && $arr[$j] < $arr[$j + 1]){
  17.       $j ++; //转化为右孩子
  18.     }
  19.     if($temp >= $arr[$j]){
  20.       break; //已经满足大根堆
  21.     }
  22.     //将根节点设置为子节点的较大值
  23.     $arr[$start] = $arr[$j];
  24.     //继续往下
  25.     $start = $j;
  26.   }
  27.   $arr[$start] = $temp;
  28. }
  29. function HeapSort(array &$arr){
  30.   $count = count($arr);
  31.   //先将数组构造成大根堆(由于是完全二叉树,所以这里用floor($count/2)-1,下标小于或等于这数的节点都是有孩子的节点)
  32.   for($i = floor($count / 2) - 1;$i >= 0;$i --){
  33.     HeapAdjust($arr,$i,$count);
  34.   }
  35.   for($i = $count - 1;$i >= 0;$i --){
  36.     //将堆顶元素与最后一个元素交换,获取到最大元素(交换后的最后一个元素),将最大元素放到数组末尾
  37.     swap($arr,0,$i);
  38.     //经过交换,将最后一个元素(最大元素)脱离大根堆,并将未经排序的新树($arr[0...$i-1])重新调整为大根堆
  39.     HeapAdjust($arr,0,$i - 1);
  40.   }
  41. }
  42. $arr = array(9,1,5,8,3,7,4,6,2);
  43. HeapSort($arr);
  44. var_dump($arr);
复制代码
运行结果:
  1. array(9) {
  2. [0]=>
  3. int(1)
  4. [1]=>
  5. int(2)
  6. [2]=>
  7. int(3)
  8. [3]=>
  9. int(4)
  10. [4]=>
  11. int(5)
  12. [5]=>
  13. int(6)
  14. [6]=>
  15. int(7)
  16. [7]=>
  17. int(8)
  18. [8]=>
  19. int(9)
  20. }
复制代码
时间复杂度分析:
它的运行时间只要是消耗在初始构建对和在重修堆屎的反复筛选上。
总体上来说,堆排序的时间复杂度是 O(nlogn)。由于堆排序对原始记录的排序状态并不敏感,因此它无论是最好、最差和均匀时间复杂度都是 O(nlogn)。这在性能上显然要远远好于冒泡、简单选择、直接插入的 O(n^2) 的时间复杂度了。
堆排序是一种不稳固排序方法。
本文参考自《大话数据结构》,在此仅作记录,方便以后查阅,大神勿喷!
PS:这里再为各人推荐一款关于排序的演示工具供各人参考:
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys
更多关于PHP相关内容感爱好的读者可检察本站专题:《php排序算法总结》、《PHP数据结构与算法教程》、《php步伐计划算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操纵本领大全》、《PHP常用遍历算法与本领总结》及《PHP数学运算本领总结》
渴望本文所述对各人PHP步伐计划有所资助。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作