本篇章节讲解PHP排序算法之堆排序(Heap Sort)。分享给大家供大家参考,具体如下:
算法引进:
在这里我直接引用《》里面的开头:
在前面讲到 ,它在待排序的 n 个记录中选择一个最小的记录需要比较 n – 1 次,本来这也可以理解,查找第一个数据需要比较这么多次是正常的,否则如何知道他是最小的记录。
可惜的是,这样的操作并没有把每一趟的比较结果保存下来,在后一趟的比较重,有许多比较在前一趟已经做过了,但由于前一趟排序时未保存这些比较结果,所以后一趟排序时又重复执行了这些比较操作,因而记录的比较次数较多。
如果可以做到每次在选择到最小记录的同时,并根据比较结果对其他记录做出相应的调整,那样排序的总体效率就会非常高了。而堆排序,就是对简单选择排序进行的一种改进,这种改进的效果是非常明显的。
基本思想:
在介绍堆排序之前,我们先来介绍一下堆:
《》里的定义:堆 是具有下列性质的完全二叉树:每个节点的值都大于或等于其左右孩子节点的值,成为大顶堆(大根堆);或者每个节点的值都小于或等于其左右节点的值,成为小顶堆(小根堆)。
当时我在看到这里的时候也对有“堆是否是完全二叉树”有过疑问,网上也有说不是完全二叉树的,但是无论堆是不是完全二叉树,尚且保留意见。我们只要知道,在这里我们采用完全二叉树形式的大根堆(小跟堆),主要是为了方便存储和计算(后面我们会看到带来的便利)。
堆排序算法:
堆排序就是利用堆(假设利用大根堆)进行排序的方法,它的基本思想是:
大根堆排序算法的基本操作:
在这个过程中是需要大量的图示才能看的明白的,但是我懒。。。。。。
算法实现:
= $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,$i);
//经过交换,将最后一个元素(最大元素)脱离大根堆,并将未经排序的新树($arr[0…$i-1])重新调整为大根堆
HeapAdjust($arr,$i – 1);
}
}
$arr = array(9,1,5,8,3,7,4,6,2);
HeapSort($arr);
var_dump($arr);
运行结果:
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)
}
时间复杂度分析:
它的运行时间只要是消耗在初始构建对和在重建堆屎的反复筛选上。
总体上来说,堆排序的时间复杂度是
堆排序是一种不稳定排序方法。
本文参考自《》,在此仅作记录,方便以后查阅,大神勿喷!
PS:这里再为大家推荐一款关于排序的演示工具供大家参考:
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
更多关于PHP相关内容感兴趣的读者可查看本站专题:《》、《》、《》、《》、《》、《》及《》
希望本文所述对大家PHP程序设计有所帮助。