PHP排序算法的堆排序示例的详细说明

本文描述了PHP的堆排序排序算法。分享给大家参考，如下：

算法介绍：

这里我直接引用《大话数据结构》的开头：

说到简单的选择排序，需要将N条记录中最小的一条记录进行n-1次比较排序。本来可以理解为第一个数据对比那么多次是正常的，不然怎么知道是最小的记录呢？

可惜这次操作没有保存每次行程的对比结果，后一次行程比较重，前一次行程已经做了很多对比。但是，由于这些比较结果在前一次行程中没有保存，这些比较操作在后一次行程中重复进行，因此记录的比较次数较多。

如果我们每次都可以选择最小的记录，并根据比较结果对其他记录进行相应的调整，那么排序的整体效率会非常高。堆排序是对简单选择排序的改进，这种改进的效果非常明显。

基本思想：

在介绍堆排序之前，我们先介绍一下堆：

《大话数据结构》中的定义：堆是一个完整的二叉树，具有以下性质：每个节点的值大于或等于其左右子节点的值，成为一个大的顶堆(大根堆)；或者每个节点的值小于或等于其左右节点的值，则成为一个小的顶部堆(小的根堆)。

当时看到这里，也对堆是不是一棵完整的二叉树产生了怀疑。网上也说不是完全的二叉树，但堆是不是完全的二叉树我还是有所保留。只要我们知道，这里我们用大根堆(小跟堆)的形式完成二叉树，主要是为了方便存储和计算(后面我们会看到带来的便利)。

堆排序算法：

堆排序是一种使用堆进行排序的方法(假设有一个大的根堆)。它的基本思想是构造一个大的待排序序列的根堆。此时，整个序列的最大值是堆顶部的根节点。把它移开(实际上是和堆数组的最后一个元素交换，当最后一个元素是最大值的时候)，然后把剩下的n-1个序列重新构造成一个堆，从而得到n个元素中的下一个最小值。如果你重复这样做，你可以得到一个有序的序列。

大根堆排序算法的基本操作；

(1)堆构建是一个不断调整堆的过程，从len/2开始到第一个节点，其中len是堆中元素的数量。堆的建立是一个线性的过程，调整堆的过程从len/2到0调用，相当于o(h1) o(h2) … o(hlen/2)，其中h表示节点的深度，len/2表示节点的个数，是一个求和的过程，结果是线性的O(n)。

调整堆：调整堆将用于构建堆的过程中，也用于对堆进行排序的过程中。使用的思想是将节点I与其左(I)和右(I)的子节点进行比较，并选择三个子节点中最大的(或最小的)。如果最大(或最小)值不是节点I，而是它的一个子节点，那么将节点I与这个节点进行交互，然后调用堆调整过程，就是一个递归过程。调整堆的时间复杂度与堆的深度有关，这是lgn的操作，因为是沿着深度方向调整的。

堆排序：堆排序采用以上两种流程进行。首先是基于元素构建一个堆。然后取出堆的根节点(通常与最后一个节点交换)，继续对前面的len-1节点进行堆调整的过程，然后取出根节点，直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为堆构建的时间复杂度是O(n)(调用一次)；调整堆的时间复杂度为lgn，称为n-1次，因此堆排序的时间复杂度为O(nlgn)。

在这个过程中，我需要很多插图才能看清楚，但我很懒。

算法实现：

？Php//堆排序(简单选择排序的改进)函数交换(array $ arr，$ a，$ b){ $ temp=$ arr[$ a]；$ arr[$ a]=$ arr[$ b]；$ arr[$ b]=$ temp；}//调整$arr[$start]的关键字，使$arr[$start]，$arr[$start 1]，$arr[$end]成为一个大的根堆(根节点最大的完整二叉树)//注意这里的节点S的左右子节点是2*s 1和2*s 2(数组起始下标)//沿着关键字较大的子节点向下过滤//计算左右子节点(我在这里的数组开头标记0)//Left child 2 * $ start 1，right child 2 * $ start 2 for($ 2)$ 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；}函数HeapSort(array $ arr){ $ count=count($ arr)；//首先，将数组构造成一个大的根堆(因为是一个完整的二叉树，这里使用floor($count/2)-1，下标小于等于这个数的节点都是有子节点的节点)为($ I=floor($ count/2)-1；$ I=0；$i - ){ HeapAdjust($arr，$i，$ count)；} for($ I=$ count-1；$ I=0；$ I-){//用最后一个元素交换堆的顶部元素，得到最大的元素(交换后的最后一个元素)，把最大的元素放在数组交换的末尾($arr，0，$ I)；//交换后，最后一个元素(最大的元素)从大根堆中分离出来，未排序的新树($arr[0.$i-1])被重新调整为大根堆headapdjust ($ arr，0，$ I-1)；}}$arr=array(9，1，5，8，3，7，4，6，2)；HeapSort(arr美元)；var _ dump($ arr)；运行结果：

数组(9){[0]=int(1)[1]=int(2)[2]=int(3)[3]=int(4)[4]=int(5)[5]=int(6)[6]=int(7)[7

只要它的运行时间花在初始构建对和重建堆屎的反复筛选上。

一般来说，堆排序的时间复杂度为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数学运算技巧总结》、0103010

希望本文对PHP编程有所帮助。