用 PHP 编写归并排序 [英] Writing merge sort in PHP

问题描述

我尝试在 PHP 中编写一个涉及小数组的基本合并排序，但问题是执行大约需要一分钟左右，然后返回:

<块引用>

致命错误:允许的内存大小为 536870912 字节已用尽(已尝试在第 39 行的/Users/web/www/merge.php 中分配 35 个字节

有谁知道代码可能出错的地方(如果有的话)?我已经盯着这个看了一个小时.

 0 || count(right) > 0){if(count($left) > 0 && count(right) > 0){if($left[0] <= $right[0]){$result[] = array_shift($left);} 别的 {$result[] = array_shift($right);}} elseif (count($left) > 0){$result[] = array_shift($left);} elseif (count($right) > 0){$result[] = array_shift($right);}}打印数组($result)；退出；返回 $result;}函数print_array($array){echo "
";print_r($array);echo "<br/>";echo "</pre>";}?>
解决方案
在你的 merge 函数中，你调用 count on right 而不是 $right.PHP 假定这是一个字符串常量(至少在 5.3.9 中)并且当被转换为一个始终只有一个元素的数组时.所以 count(right) 总是一个，你永远不会退出第一次合并.
I have tried to write a basic merge sort in PHP involving a small array, yet the problem is it takes about a minute or so to execute, and returns:

  
Fatal error: Allowed memory size of 536870912 bytes exhausted (tried
  to allocate 35 bytes) in /Users/web/www/merge.php on line 39
Does anyone have an idea where the code might be going wrong (if at all)? I've been staring at this for a good hour now.
<?php

$array = array(8,1,2,5,6,7);
print_array($array);
merge_sort($array);
print_array($array);

function merge_sort(&$list){
    if( count($list) <= 1 ){
        return $list;
    }

    $left =  array();
    $right = array();

    $middle = (int) ( count($list)/2 );

    // Make left
    for( $i=0; $i < $middle; $i++ ){
        $left[] = $list[$i];
    }

    // Make right
    for( $i = $middle; $i < count($list); $i++ ){
        $right[] = $list[$i];
    }

    // Merge sort left & right
    merge_sort($left);
    merge_sort($right);

    // Merge left & right
    return merge($left, $right);
}

function merge(&$left, &$right){
    $result = array();

    while(count($left) > 0 || count(right) > 0){
        if(count($left) > 0 && count(right) > 0){
            if($left[0] <= $right[0]){
                $result[] = array_shift($left);
            } else {
                $result[] = array_shift($right);
            }
        } elseif (count($left) > 0){
            $result[] = array_shift($left);
        } elseif (count($right) > 0){
            $result[] = array_shift($right);
        }
    }

    print_array($result);exit;

    return $result;
}

function print_array($array){
    echo "<pre>";
    print_r($array);
    echo "<br/>";
    echo "</pre>";
}

?>

解决方案
In your merge function, you call count on right instead of $right. PHP assumes this is a string constant (at least in 5.3.9) and when casted into an array that always has one element. So count(right) is always one, and you never exit the first merge.


                        
这篇关于用 PHP 编写归并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！