PHP实现堆排序算法（代码示例）

内容导读

收集整理的这篇技术教程文章主要介绍了PHP实现堆排序算法（代码示例），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2721字，纯文字阅读大概需要4分钟。

内容图文

在计算机科学中，heapsort(1964年由J. W. J. Williams发明)是一种基于比较的排序算法。Heapsort（堆排序）可以看作是一种改进的选择排序:与该算法类似，它将输入分为已排序区域和未排序区域，并通过提取最大的元素并将其移动到已排序区域来交互式地缩小未排序区域。改进包括使用堆数据结构，而不是线性时间搜索来找到最大值。

尽管在大多数机器上，它的实际运行速度比实现良好的快速排序要慢一些，但它的优势是在最坏情况下O(n log n)运行时更有利。堆排序是一种就地排序算法，但它不是一种稳定排序。

heapsort算法对一组随机排列的值进行排序。在算法的第一阶段，数组元素被重新排序以满足堆属性。在进行实际排序之前，将简要展示堆树结构以供说明。

PHP堆排序算法思路示意图：

PHP堆排序实现代码如下：

<?phpclass Node{    private $_i;    public function __construct($key)    {        $this->_i = $key;    }    public function getKey()    {        return $this->_i;    }}class Heap{    private $heap_Array;    private $_current_Size;    public function __construct()    {        $heap_Array = array();        $this->_current_Size = 0;    }     public function remove()    {        $root = $this->heap_Array[0];                $this->heap_Array[0] = $this->heap_Array[--$this->_current_Size];        $this->bubbleDown(0);        return $root;    }       public function bubbleDown($index)    {        $larger_Child = null;        $top = $this->heap_Array[$index];         while ($index < (int)($this->_current_Size/2)) {             $leftChild = 2 * $index + 1;            $rightChild = $leftChild + 1;                      if ($rightChild < $this->_current_Size                && $this->heap_Array[$leftChild] < $this->heap_Array[$rightChild])             {                $larger_Child = $rightChild;            } else {                $larger_Child = $leftChild;            }            if ($top->getKey() >= $this->heap_Array[$larger_Child]->getKey()) {                break;            }                        $this->heap_Array[$index] = $this->heap_Array[$larger_Child];            $index = $larger_Child;        }        $this->heap_Array[$index] = $top;    }    public function insertAt($index, Node $newNode)    {        $this->heap_Array[$index] = $newNode;    }    public function incrementSize()    {        $this->_current_Size++;    }    public function getSize()    {        return $this->_current_Size;    }    public function asArray()    {        $arr = array();        for ($j = 0; $j < sizeof($this->heap_Array); $j++) {            $arr[] = $this->heap_Array[$j]->getKey();        }        return $arr;    }}function heapsort(Heap $Heap){    $size = $Heap->getSize();        for ($j = (int)($size/2) - 1; $j >= 0; $j--)    {        $Heap->bubbleDown($j);    }       for ($j = $size-1; $j >= 0; $j--) {        $BiggestNode = $Heap->remove();            $Heap->insertAt($j, $BiggestNode);    }    return $Heap->asArray();}$arr = array(3, 0, 2, 5, -1, 4, 1);echo "原始数组 : ";echo implode(', ',$arr );$Heap = new Heap();foreach ($arr as $key => $val) {    $Node = new Node($val);    $Heap->insertAt($key, $Node);    $Heap->incrementSize();}$result = heapsort($Heap);echo "n排序后数组 : ";echo implode(', ',$result)."n";

输出：

原始数组 : 3, 0, 2, 5, -1, 4, 1 排序后数组 : -1, 0, 1, 2, 3, 4, 5

本篇文章就是关于PHP堆排序的介绍，希望对需要的朋友有所帮助！

以上就是PHP实现堆排序算法（代码示例）的详细内容，更多请关注Gxl网其它相关文章！

内容总结

以上是为您收集整理的PHP实现堆排序算法（代码示例）全部内容，希望文章能够帮你解决PHP实现堆排序算法（代码示例）所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。