php实现归并

归并排序的PHP实现

归并排序是一种基于分治法的排序算法，通过递归将数组拆分为更小的子数组，排序后再合并。以下是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);
}

使用示例

$unsortedArray = [5, 2, 9, 1, 5, 6];
$sortedArray = mergeSort($unsortedArray);
print_r($sortedArray);

算法说明

归并排序的时间复杂度为O(n log n)，空间复杂度为O(n)。该实现通过递归将数组不断二分，直到子数组长度为1，然后通过merge函数合并两个已排序的子数组。

merge函数通过比较两个子数组的首元素，将较小的元素放入结果数组，直到其中一个子数组为空，最后将剩余元素直接合并。

优化建议

对于小规模数组可切换为插入排序减少递归开销。PHP的array_shift操作有O(n)时间复杂度，可通过索引指针优化。