用PHP编写归并排序

Question

我尝试在PHP中编写一个基本的归并排序，涉及一个小数组，但问题是它需要大约一分钟的时间才能执行，并返回以下内容:

“致命错误：在/Users/web/www/merge.php的第39行尝试分配35个字节时，已耗尽536870912字节的允许内存大小。”

如果有人知道代码可能出了什么问题（如果有的话），请告诉我。我已经盯着这个问题看了一个小时了。

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

?>

- jweb

---

虽然这不是你的问题，但请注意 PHP 有一个最大递归限制为 100。当给定足够大的数组时，您可能最终会达到此限制。 - Charles

请查看此网站以获取更多帮助：http://php.net/manual/zh/array.sorting.php - Sam Arul Raj T

最好包含一个链接到你想做的事情：http://en.wikipedia.org/wiki/Merge_sort。我个人会使用php的本地（用C编写）排序算法-我认为php代码将比php的本地快速排序方法效率低。除了显而易见的本地与PHP代码之外，为什么快速排序比归并排序更好的解释可以在这里找到：https://dev59.com/7HRB5IYBdhLWcg3wQFLu。 - Arend

即使这是真的，你也需要一个大约有2^100（1.268 x 10^30）个元素的数组才能达到递归限制。在那之前，你早就用完了内存。 - Omnimike

@Arend 我知道这是一个非常老的帖子，但我仍然觉得有必要评论一下你的话。当然，在许多情况下，快速排序比归并排序更有效率，但这完全取决于情况、环境和其他因素。你不能简单地说算法A总是比算法B更好。有不同的排序算法是有充分理由的。 - Ruben

Answer 1

在你的merge函数中，你调用了right上的计数，而不是$right。在PHP 5.3.9中，PHP假定这是一个字符串常量，并将其转换为始终具有一个元素的数组。因此，count(right)始终为1，你从未退出第一个合并。

- Juan

---

很抱歉，但是这个程序并不太好用。结尾处的 exit 命令会让你得到最小长度为 2 的数组。如果你不使用它，程序会返回所有的数组。需要在其中进行一些数组合并的操作。 - Tom Granot

Answer 2

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

此外，在merge函数的for循环中，您需要进行&&比较，而不是||。

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

- Kartik

---

如果你的数组大小是奇数怎么办？ - marfis

Answer 3

看一下这个，算法已经实现了，使用array_push和array_splice而不是仅使用array_shift。

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

- Avanche

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

- Samuel James

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);
            ?>

- Kripa Yadav

Answer 6

我正在寻找一个优化后的PHP归并排序算法。有5种算法在回答中，所以我测试了那些和我的算法。使用PHP 7.2.7，这是时间:

对1000个随机数字进行排序:

• Avanche 1 0.0396秒
• Avanche 2 0.0347秒
• Kartik 0.0291秒
• Kripa 0.0282秒
• Samuel 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);
}

如果您发布了新的答案，请给我留言以进行测试并添加。

---

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

- Leopoldo Sanczyk

---

最后一行应该是 foreach ($aux as $v) $a[$start++] = $v;。 - chqrlie

您可能还想测试一下$center = ($start + $end) >> 1;或$center = (int)(($start + $end) / 2);是否比$center = floor(($start + $end) / 2);更有效率。 - chqrlie

另一个想法：您可以使用一个名为mergeSort_rec的单独函数，不带有默认参数值或测试$end=$end??count($a)-1;，并从mergeSort()中调用该函数。将$end视为排除产生更清洁和简单的代码。 - chqrlie

感谢@chqrlie。你是正确的，我应该在这里应用一些优化，而不是等待其他答案。二进制移位始终是一个好方法，它使算法运行快了10%（没有尝试int转换）。将函数分成递归和非递归调用使它运行得更快了5%。避免mix()调用，又多出了5%。所以我用这些修改更新了代码。 - Leopoldo Sanczyk

也许我们可以稍后添加一些不太明显的微调并保持更新。我记得有一个，它在两个数组之间交替，并避免创建和销毁辅助数组，例如，但这需要时间。让我们等待新的鼓励。目前，感谢您的支持 ;) - Leopoldo Sanczyk

Answer 7

你的归并排序通过引用接受一个列表

function merge_sort(&$list)

所以你需要将它分配给新的合并和排序后的列表。因此，不是

return merge($left, $right);

做

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

应该就是这样了，只需删除 exit 并修复计数变量即可

- Rana Kolta

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);

- Sukeshini