2

私はここphpでヒープソートに固執しています：

<?php
function heapSort($a, $count){
    $a = heapify($a, $count);

    $end = $count - 1;
    while ($end > 0){
        $temp = $a[$end];

        $a[$end] = $a[0] ;

        $a[0]= $temp;
        $end = $end - 1;
        siftDown($a, 0, $end);
    }
    return $a;
}

    function heapify($a,$count){
        $start = ($count - 2) / 2;

        while ($start >= 0){
            $a = siftDown($a, $start, $count-1);
            $start = $start - 1;
        }
        return $a;
    }

    function siftDown($a, $start, $end){
        $root = $start;

        while ($root * 2 + 1 <= $end){// While the root has at least one child
            $child = $root * 2 + 1;      // root*2+1 points to the left child
                                         //If the child has a sibling and the 
                                         //child's value is less than its
                                         //sibling's
            if ($child + 1 <= $end and $a[$child] < $a[$child + 1])
                $child = $child + 1;// then point to the right child instead)
            if ($a[$root] < $a[$child]){ // out of max-heap order
                  list($a[$child],$a[$root]) = array($a[$root],$a[$child]);
                $root = $child;      // repeat to continue sifting down
                                     // the child now
            }
            else {
                return $a;
    }}
    return $a;
    }


    $a = Array(3,1,5,2);
    $b = heapSort($a,count($a));
    print_r($b);
    ?>

配列を並べ替えることができません。何が問題なのかわかりませんか？

4

3 に答える 3

2

siftDown（）は、渡す配列を変更することになっています。したがって、参照によって渡す必要があります。それ以外の場合、関数はデータのコピーを操作します。

function siftDown(&$a, $start, $end) {
于 2009-06-23T05:20:09.617 に答える
1

これは、phpでのヒープソートの最も単純なコードだと思います

于 2011-06-08T11:44:17.800 に答える
0

私はPHPの専門家ではありませんが、heapify正しく行われているようには見えません。ヒープ化は、どのようにしてsiftDownへの一連の呼び出しに要約できますか...？後者は、ヒープである配列（おそらく1つの例外を除く）を処理していると仮定して書かれていますheapifyが、そもそもヒープ不変条件を確立するものです...

于 2009-06-23T05:11:20.753 に答える