本文实例讲述了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)。
在这个过程中是需要大量的图示才能看的明白的,但是我懒。。。。。。
算法实现:
<"htmlcode">array(9) { [0]=> int(1) [1]=> int(2) [2]=> int(3) [3]=> int(4) [4]=> int(5) [5]=> int(6) [6]=> int(7) [7]=> int(8) [8]=> int(9) }时间复杂度分析:
它的运行时间只要是消耗在初始构建对和在重建堆屎的反复筛选上。
总体上来说,堆排序的时间复杂度是 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程序设计有所帮助。
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
P70系列延期,华为新旗舰将在下月发布
3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。
而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?
根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。
更新日志
- 凤飞飞《我们的主题曲》飞跃制作[正版原抓WAV+CUE]
- 刘嘉亮《亮情歌2》[WAV+CUE][1G]
- 红馆40·谭咏麟《歌者恋歌浓情30年演唱会》3CD[低速原抓WAV+CUE][1.8G]
- 刘纬武《睡眠宝宝竖琴童谣 吉卜力工作室 白噪音安抚》[320K/MP3][193.25MB]
- 【轻音乐】曼托凡尼乐团《精选辑》2CD.1998[FLAC+CUE整轨]
- 邝美云《心中有爱》1989年香港DMIJP版1MTO东芝首版[WAV+CUE]
- 群星《情叹-发烧女声DSD》天籁女声发烧碟[WAV+CUE]
- 刘纬武《睡眠宝宝竖琴童谣 吉卜力工作室 白噪音安抚》[FLAC/分轨][748.03MB]
- 理想混蛋《Origin Sessions》[320K/MP3][37.47MB]
- 公馆青少年《我其实一点都不酷》[320K/MP3][78.78MB]
- 群星《情叹-发烧男声DSD》最值得珍藏的完美男声[WAV+CUE]
- 群星《国韵飘香·贵妃醉酒HQCD黑胶王》2CD[WAV]
- 卫兰《DAUGHTER》【低速原抓WAV+CUE】
- 公馆青少年《我其实一点都不酷》[FLAC/分轨][398.22MB]
- ZWEI《迟暮的花 (Explicit)》[320K/MP3][57.16MB]