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 = [];
    $leftIndex = $rightIndex = 0;

    while ($leftIndex < count($left) && $rightIndex < count($right)) {
        if ($left[$leftIndex] < $right[$rightIndex]) {
            $result[] = $left[$leftIndex];
            $leftIndex++;
        } else {
            $result[] = $right[$rightIndex];
            $rightIndex++;
        }
    }

    while ($leftIndex < count($left)) {
        $result[] = $left[$leftIndex];
        $leftIndex++;
    }

    while ($rightIndex < count($right)) {
        $result[] = $right[$rightIndex];
        $rightIndex++;
    }

    return $result;
}

使用示例

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

算法分析

时间复杂度为O(n log n)，空间复杂度为O(n)。归并排序是稳定的排序算法，适用于大数据量排序，但需要额外空间存储临时数组。