PHP排序算法系列之归并排序详解

归并排序详解

归并排序是一种非常高效的排序算法，它基于分治的思想。它将待排序的数组分成两个子数组，然后分别对这两个子数组进行排序，最后将两个有序的子数组合并成一个有序的数组。

1. 基本原理

归并排序的基本思想是将数组分成两半，然后对每一半分别进行排序，最后将两个有序的子数组合并成一个有序的数组。

归并排序的具体步骤如下：

将待排序数组划分为两个子数组，分别为左子数组和右子数组。

对左右子数组分别进行递归调用归并排序，直到数组长度为1。

将排好序的左右子数组进行合并，得到一个排好序的数组。

2. 代码实现

下面是PHP实现归并排序的代码：

/**
 * 归并排序
 *
 * @param array $arr 待排序的数组
 * @return array 排序后的数组
 */
function mergeSort(array $arr): array
{
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    
    $mid = intval($length / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);
    
    return merge(mergeSort($left), mergeSort($right));
}
/**
 * 合并两个有序数组
 *
 * @param array $left 左子数组
 * @param array $right 右子数组
 * @return array 合并后的有序数组
 */
function merge(array $left, array $right): array
{
    $result = [];
    $i = 0;
    $j = 0;
    
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] < $right[$j]) {
            $result[] = $left[$i++];
        } else {
            $result[] = $right[$j++];
        }
    }
    
    while ($i < count($left)) {
        $result[] = $left[$i++];
    }
    
    while ($j < count($right)) {
        $result[] = $right[$j++];
    }
    
    return $result;
}

3. 时间复杂度

归并排序的时间复杂度是O(nlogn)，其中n是待排序数组的长度。这是因为每次都将数组分成两半，需要logn次，每次合并的操作需要O(n)的时间。

归并排序虽然效率较高，但是它需要额外的空间来存储合并过程中的临时数组，所以空间复杂度是O(n)。

4. 总结

归并排序是一种非常高效的排序算法，它具有稳定性和较高的时间复杂度。通过分治的思想，归并排序能够将一个大问题拆分成多个小问题，并最终解决这些小问题，最后将结果合并起来得到最终的解。

在实际应用中，归并排序被广泛应用于需要稳定排序的场景，例如对学生成绩进行排序。由于归并排序的时间复杂度较为稳定，因此在面对大规模数据排序时，归并排序也是一个可选的高效排序算法。