PHP排序算法之堆排序(Heap Sort)实例详解
|
本篇章节讲授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措施计划有所辅佐。 （编辑：湖南网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
