php実装スタックソート

2814 ワード

$arr = [9, 43, 12, 0, 87, 1];
function swap(&$arr, $i, $j){
    $tmp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $tmp;
}
//merge_sort($arr);
function heap_sort(&$arr){
    $len = count($arr) -1;
    $m = intval($len/2);
    //        
    for($i = $m; $i >= 0; $i--){
        heap_adjust($arr, $i, $len);
    }
    //
    for($i = $len; $i > 0; $i--){
        echo "$i";
        swap($arr, 0, $i);
        heap_adjust($arr, 0, $i -1);
    }
}
/*
*$arr $start+1 $end        ,        ,              
*/
function heap_adjust(&$arr, $start, $end){
    if($start >= $end){
        return;
    }
    $tmp = $arr[$start];
    $i = $start;
    for($j = 2 * $start; $j <= $end; $j *=2 ){
        if($j+1 <= $end && $arr[$j+1] > $arr[$j]){
            $j++;
        }
        if($arr[$j] < $tmp){
            break;
        }
        $arr[$i] = $arr[$j];
        $i = $j;
    }
    $arr[$i] = $tmp;
}
heap_sort($arr);
var_export($arr);