php归并实现排序

归并排序原理

归并排序是一种分治算法，通过递归将数组拆分为更小的子数组，直到每个子数组只有一个元素。随后合并这些有序子数组，最终得到完全有序的数组。时间复杂度为O(n log n)，空间复杂度为O(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);
        }
    }

    while (count($left) > 0) {
        $result[] = array_shift($left);
    }

    while (count($right) > 0) {
        $result[] = array_shift($right);
    }

    return $result;
}

代码解析

mergeSort函数负责递归拆分数组，当子数组长度小于等于1时直接返回。通过array_slice将数组分为左右两部分，分别递归排序后再调用merge合并。

merge函数通过双指针方式比较左右子数组的元素，将较小值放入结果数组。当任一子数组遍历完成后，将剩余元素直接追加到结果数组末尾。

使用示例

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