Написание сортировки слиянием в PHP

Question

Я попытался написать базовую сортировку слиянием в PHP, включающую небольшой массив, но проблема в том, что выполнение занимает около минуты или около того, и возвращает:

Неустранимая ошибка: допустимая памятьразмер 536870912 байт исчерпан (попытался выделить 35 байт) в /Users/web/www/merge.php в строке 39

Кто-нибудь имеет представление, где код может работать неправильно (есливсе)?Я уже давно смотрю на это.

<code><?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 "

";}?>

Answer 1

В вашей функции merge вы вызываете счет на right вместо $right.PHP предполагает, что это строковая константа (по крайней мере, в 5.3.9) и при преобразовании в массив, который всегда имеет один элемент.Так что count(right) всегда один, и вы никогда не выходите из первого слияния.

Answer 2

Попробуйте этот подход. Вместо того, чтобы сдвигать его, нарежьте.

Кроме того, для цикла while для функции merge необходимо вместо этого выполнить сравнение и && из ||

function mergeSort($array)
{
    if(count($array) == 1 )
    {
        return $array;
    }

    $mid = count($array) / 2;
    $left = array_slice($array, 0, $mid);
    $right = array_slice($array, $mid);
    $left = mergeSort($left);
    $right = mergeSort($right);

    return merge($left, $right);
}


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

    while (count($left) > 0 && count($right) > 0)
    {
        if($left[0] > $right[0])
        {
            $res[] = $right[0];
            $right = array_slice($right , 1);
        }
        else
        {
            $res[] = $left[0];
            $left = array_slice($left, 1);
        }
    }

    while (count($left) > 0)
    {
        $res[] = $left[0];
        $left = array_slice($left, 1);
    }

    while (count($right) > 0)
    {
        $res[] = $right[0];
        $right = array_slice($right, 1);
    }

    return $res;
}

Answer 3

Посмотрите на это, алгоритм уже реализован, используя array_push и массив splice вместо просто array_shift.

Answer 4

Вот класс в PHP для реализации сортировки слиянием -

            <?php
            class mergeSort{
                public $arr;
                public function __construct($arr){
                    $this->arr = $arr;
                }

                public function mSort($l,$r){
                    if($l===null || $r===null){ 
                        return false;
                    }
                    if ($l < $r)
                    {
                        // Same as ($l+$r)/2, but avoids overflow for large $l and $r
                        $m = $l+floor(($r-$l)/2);

                        // Sort first and second halves
                        $this->mSort($l, $m);
                        $this->mSort($m+1, $r);

                        $this->merge($l, $m, $r);
                    }
                }

                // Merges two subarrays of $this->arr[]. First subarray is $this->arr[$l..$m]. Second subarray is $this->arr[$m+1..$r]
                public function merge($l, $m, $r)
                {
                    if($l===null || $m===null || $r===null){    
                        return false;
                    }

                    $n1 = $m - $l + 1;
                    $n2 =  $r - $m;

                    /* create temp arrays */
                    $L=array();
                    $R=array();

                    /* Copy data to temp arrays $L[] and $R[] */
                    for ($i = 0; $i < $n1; $i++)
                        $L[$i] = $this->arr[$l + $i];

                    for ($j = 0; $j < $n2; $j++)
                        $R[$j] = $this->arr[$m + 1+ $j];

                    /* Merge the temp arrays back into $this->arr[$l..$r]*/
                    $i = 0; // Initial index of first subarray
                    $j = 0; // Initial index of second subarray
                    $k = $l; // Initial index of merged subarray
                    while ($i < $n1 && $j < $n2)
                    {
                        if($L[$i] <= $R[$j])
                        {
                            $this->arr[$k] = $L[$i];
                            $i++;
                        }
                        else
                        {
                            $this->arr[$k] = $R[$j];
                            $j++;
                        }
                        $k++;
                    }

                    /* Copy the remaining elements of $L[], if there are any */
                    while($i < $n1)
                    {
                        $this->arr[$k] = $L[$i];
                        $i++;
                        $k++;
                    }

                    /* Copy the remaining elements of $R[], if there are any */
                    while($j < $n2)
                    {
                        $this->arr[$k] = $R[$j];
                        $j++;
                        $k++;
                    }
                }
            }

            $arr = array(38, 27, 43, 5, 9, 91, 12);
            $obj = new mergeSort($arr);
            $obj->mSort(0,6);
            print_r($obj->arr);
            ?>

Answer 5

Я реализую сортировку слиянием таким образом

function mergeSort($Array)
{
    $len = count($Array);
    if($len==1){
        return $Array;
    }
    $mid = (int)$len / 2;
    $left = mergeSort(array_slice($Array, 0, $mid));
    $right = mergeSort(array_slice($Array, $mid));
    return merge($left, $right);
}

function merge($left, $right)
{


    $combined = [];
    $totalLeft = count($left);
    $totalRight = count($right);
    $rightIndex = $leftIndex=0;
    while ($leftIndex < $totalLeft && $rightIndex < $totalRight) {
        if ($left[$leftIndex] > $right[$rightIndex]) {
            $combined[]=$right[$rightIndex];
            $rightIndex++;
        }else {
            $combined[] =$left[$leftIndex];
            $leftIndex++;
        }
    }
    while($leftIndex<$totalLeft){
        $combined[]=$left[$leftIndex];
        $leftIndex++;
    }
    while ($rightIndex<$totalRight){
        $combined[] =$right[$rightIndex];
        $rightIndex++;
    }
    return $combined;
}

Answer 6

Ваша сортировка слиянием принимает список по ссылке

function merge_sort(&$list)

Так что вам нужно назначить ему новый объединенный и отсортированный список. Так что вместо

return merge($left, $right);

сделать

$list = $this->merge($left, $right);

Это должно сделать, просто удалите выход и исправьте переменную count