PHP 如何实现两个有序数组合并并保持排序

核心逻辑：双指针归并策略

要实现两个有序数组 A 和 B 合并为有序数组 C，且不使用现成的排序函数，最有效的方法是采用归并算法（Merge Algorithm）的核心思想：

1. 准备三个数组指针：分别指向数组 A、数组 B 和结果数组 C 的当前处理位置。
2. 比较 A 和 B 当前指向的元素大小。
3. 将较小的元素追加到结果数组 C 中，并将对应数组的指针后移一位。
4. 如果其中一个数组遍历完毕，将另一个数组剩余的所有元素直接追加到 C 末尾。

这种方法的时间复杂度为 O(M+N)，比先合并再排序的 O((M+N)log(M+N)) 更高效。

具体操作：PHP 代码实现步骤

第1步：定义数据结构与辅助方法

创建一个类来封装操作，包含输入数组、输出数组以及获取长度和元素的辅助方法。注意：原文代码使用了旧式的 var 关键字定义属性，在新版 PHP 中建议使用 public 或 private。

<?php
class ArrayMerger {
    // 定义属性：使用现代 PHP 语法
    public $lista = array();
    public $listb = array();
    public $listc = array();

    // 获取数组长度
    public function getLength($arr) {
        return count($arr);
    }

    // 安全获取指定索引的元素，若不存在返回空字符串
    public function getElement($arr, $index) {
        return isset($arr[$index]) ? $arr[$index] : '';
    }

    // 向数组末尾插入元素
    public function insertElement(&$arr, $element) {
        $arr[] = $element;
    }
}
?>

第2步：初始化数据与指针

实例化对象，定义两个已排序的源数组，并初始化用于遍历的索引变量 $i (指向 lista) 和 $j (指向 listb)。

<?php
$merger = new ArrayMerger();
// 假设这两个数组已经是有序的
$merger->lista = array(3, 5, 8, 11);
$merger->listb = array(2, 6, 8, 9, 11, 15);
$merger->listc = array(); // 结果数组初始为空

$lena = $merger->getLength($merger->lista);
$lenb = $merger->getLength($merger->listb);

$i = 0; // lista 的指针
$j = 0; // listb 的指针
?>

第3步：执行主循环比较与合并

当两个数组都还有未处理元素时（即 $i < $lena 且 $j < $lenb），持续进行比较。

<?php
while ($i < $lena && $j < $lenb) {
    $ea = $merger->getElement($merger->lista, $i);
    $eb = $merger->getElement($merger->listb, $j);

    // 关键判断：取较小者放入结果表
    if ($ea <= $eb) {
        $merger->insertElement($merger->listc, $ea);
        ++$i; // A 表指针后移
    } else {
        $merger->insertElement($merger->listc, $eb);
        ++$j; // B 表指针后移
    }
}
?>

第4步：处理剩余元素

当上述循环结束时，意味着至少有一个数组已经全部处理完毕。此时需要将另一个数组剩余的部分直接追加到结果数组末尾。

<?php
// 如果 lista 还有剩余元素
while ($i < $lena) {
    $ea = $merger->getElement($merger->lista, $i);
    $merger->insertElement($merger->listc, $ea);
    ++$i;
}

// 如果 listb 还有剩余元素
while ($j < $lenb) {
    $eb = $merger->getElement($merger->listb, $j);
    $merger->insertElement($merger->listc, $eb);
    ++$j;
}
?>

第5步：输出验证结果

打印最终合并后的数组，检查是否保持了升序排列。

<?php
print_r($merger->listc);
// 预期输出: Array ([0]=2, [1]=3, [2]=5, [3]=6, [4]=8, [5]=8, [6]=9, [7]=11, [8]=11, [9]=15)
?>

完成判断与原理解析

通过上述步骤，我们成功在不使用 sort() 的情况下完成了合并。判断完成的标准是：listc 的长度等于 lista 和 listb 长度之和，且内部元素严格满足递增关系。

• 相等值处理：在判断条件中使用了 <=，这意味着当两个元素相等时，优先取左侧数组的元素。这保证了稳定性（Stable Sort），即原始顺序在相等元素间得以保留。
• 边界情况：如果其中一个输入数组为空，主循环不会执行，直接进入对应的 while 剩余元素处理块，代码依然健壮有效。

以上就是 PHP 实现两表合并成新表并且有序排列的详细内容，更多关于 PHP 数组算法优化的资料请关注本站其它相关文章！