用 PHP 编写合并排序

Question

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

致命错误：允许的内存大小 536870912 字节已耗尽（已尝试 分配 35 个字节）在 /Users/web/www/merge.php 第 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 上的 count 而不是 $right。 PHP 假定这是一个字符串常量（至少在 5.3.9 中），并且当转换为始终具有一个元素的数组时。因此 count(right) 始终为 1，并且您永远不会退出第一次合并。

Answer 2

尝试这种方法。不要移动它，而是切片。

另外，对于 merge 函数的 in while 循环，您需要进行和 && 比较
||

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 和 array splice 而不是仅仅 array_shift。

http://www.codecodex.com/wiki/Merge_sort#PHP

Answer 4

我这样实现合并排序

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 5

这是 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 6

我一直在寻找 PHP 中优化的合并排序算法。答案中有 5 种算法，所以我测试了这些算法，也测试了我的算法。使用 PHP 7.2.7，时间如下：

对 1000 个随机数进行排序：

• Avanche 1 0.0396 秒
• Avanche 2 0.0347 秒
• Kartik 0.0291 秒
• Kripa 0.0282 秒
• 塞缪尔 0.0247 秒
• 我的0.0144 秒

对 10 个随机数进行排序：

• Avanche 1 0.000222 秒
• Kartik 0.000216 秒
• Kripa 0.000159 秒
• Avanche 2 0.000144 秒
• Samuel 0.000128 秒
• 我的0.000098 秒

所以，尽管我鼓励谁阅读它以使其更快（这是我一直在寻找的，并且我相信它可以完成），但我也让你实现我的实现，原因似乎是比其他答案更快：

//This function needs start and end limits
function mergeSortRec(&$a,$start,$end){
  if($start<$end){
    $center=($start+$end)>>1; //Binary right shift is like divide by 2
    mergeSortRec($a, $start, $center);
    mergeSortRec($a, $center+1, $end);
    //Mixing the 2 halfs
    $aux=array();
    $left=$start; $right=$center;
    //Main loop
    while($left<$center && $right<=$end){
      if($a[$left]<$a[$right]){
        $aux[]=$a[$left++];
      }else{
        $aux[]=$a[$right++];
      }
    }
    //Copy the rest of the first half
    while($left<$center) $aux[]=$a[$left++];
    //Copy the rest of the second half
    while($right<=$end) $aux[]=$a[$right++];
    //Copy the aux array to the main array
    foreach($aux as $v) $a[$start++]=$v;
  }
}
//This is the function easier to call
function mergeSort(&$a) {
  mergeSortRec($a,0,count($a)-1);
}

如果您发布新答案，请让我发表评论来测试它并添加它。

---

编辑：对于那些寻求更好实现的人，我做了一些新的优化。

Answer 7

您的合并排序通过引用接受列表

function merge_sort(&$list)

，因此您需要为其分配新的合并和排序列表。因此，不要这样做

return merge($left, $right);

，

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

只需删除退出并修复计数变量即可

Answer 8

PHP 中的归并排序

<?php 
class Solution 
{
    function mergeSort(&$arr)
    {
        if(count($arr) > 1) {
            $mid = floor(count($arr)/2);
            
            $left = array_slice($arr, 0, $mid);
            $right = array_slice($arr, $mid);

            $this->mergeSort($left);
            $this->mergeSort($right);

            // Merge the results.
            $i = $j = $k = 0;
            while(($i < count($left)) && ($j < count($right))) {
                if($left[$i] < $right[$j]) {
                    $arr[$k] = $left[$i];
                    $i++;
                } else {
                    $arr[$k] = $right[$j];
                    $j++;
                }
                $k++;
            }

            while($i < count($left)) {
                $arr[$k] = $left[$i];
                $i++;
                $k++;
            }

            while($j < count($right)) {
                $arr[$k] = $right[$j];
                $j++;
                $k++;
            }
        }
    }
}

$s = new Solution();
$tmp = [12, 7, 11, 13, 5, 6, 7];
$s->mergeSort($tmp);
print_r($tmp);