php - 用 PHP 编写归并排序

Question

我曾尝试用 PHP 编写一个涉及小数组的基本合并排序，但问题是它需要大约一分钟的时间来执行，并返回:

Fatal error: Allowed memory size of 536870912 bytes exhausted (tried to allocate 35 bytes) in /Users/web/www/merge.php on line 39

有没有人知道代码可能哪里出错了(如果有的话)？我已经盯着这个看了一个小时了。

<?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>";
}

?>

Answer 1

在您的merge 函数中，您在right 而不是$right 上调用计数。 PHP 假定这是一个字符串常量(至少在 5.3.9 中是这样)，并且在转换为始终只有一个元素的数组时。所以 count(right) 永远是一个，你永远不会退出第一次合并。