php实现归并

归并排序的PHP实现

归并排序是一种基于分治法的稳定排序算法，时间复杂度为O(n log n)。以下是PHP实现归并排序的完整代码示例：

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

    $mid = (int)(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(array $left, array $right): array {
    $result = [];

    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }

    return array_merge($result, $left, $right);
}

使用示例

$unsorted = [34, 7, 23, 32, 5, 62];
$sorted = mergeSort($unsorted);
print_r($sorted);

算法说明

mergeSort函数负责递归地将数组分成两半，直到每个子数组只包含一个元素。merge函数负责将两个已排序的数组合并成一个有序数组。

时间复杂度始终为O(n log n)，空间复杂度为O(n)。归并排序是稳定的排序算法，适合处理大规模数据。

优化建议

对于小规模数组，可以切换到插入排序等简单算法提高性能。可以预先分配结果数组大小避免频繁的内存分配。