旗下导航:搜·么
当前位置:网站首页 > PHP教程 > 正文

PHP完成堆排序算法(代码示例)【php教程】

作者:搜搜PHP网发布时间:2019-11-26分类:PHP教程浏览:122


导读:在计算机科学中,heapsort(1964年由J.W.J.Williams发现)是一种基于比较的排序算法。Heapsort(堆排序)能够看做是一种革新的挑选排序:与该算法相似...
在计算机科学中,heapsort(1964年由J. W. J. Williams发现)是一种基于比较的排序算法。Heapsort(堆排序)能够看做是一种革新的挑选排序:与该算法相似,它将输入分为 已排序地区未排序地区,并经由过程提取最大的元素并将其移动到已排序地区来交互式地减少未排序地区。革新包含运用堆数据结构,而不是线性时候搜刮来找到最大值。

只管在大多数机械上,它的现实运转速率比完成优越的疾速排序要慢一些,但它的上风是在最坏情况下O(n log n)运转时更有益。堆排序是一种当场排序算法,但它不是一种稳固排序。

heapsort算法对一组随机分列的值举行排序。在算法的第一阶段,数组元素被从新排序以满足堆属性。在举行现实排序之前,将扼要展现堆树结构以供申明。

PHP堆排序算法思绪示意图:

PHP堆排序完成代码以下:

<?php
class 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完成堆排序算法(代码示例)的细致内容,更多请关注ki4网别的相干文章!

标签:PHP堆排序