​PHP中怎么使用归并排序

# PHP中怎么使用归并排序

归并排序（Merge Sort）是一种基于分治思想的高效排序算法，时间复杂度为O(n log n)。本文将详细介绍如何在PHP中实现归并排序，包括原理分析、代码实现以及实际应用示例。

## 一、归并排序算法原理

归并排序的核心思想是"分而治之"，主要分为两个阶段：

1. **分割阶段**：递归地将数组分成两半，直到每个子数组只剩一个元素
2. **合并阶段**：将两个已排序的子数组合并成一个有序数组

### 算法特点
- 稳定排序（相同元素相对位置不变）
- 需要额外O(n)的空间复杂度
- 适合处理大规模数据

## 二、PHP实现归并排序

### 基础实现代码

```php
function mergeSort(array $array): array {
    $length = count($array);
    
    // 基线条件：数组长度为1时直接返回
    if ($length <= 1) {
        return $array;
    }
    
    // 分割数组
    $mid = (int) ($length / 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++];
        } else {
            $result[] = $right[$rightIndex++];
        }
    }
    
    // 合并剩余元素
    while ($leftIndex < count($left)) {
        $result[] = $left[$leftIndex++];
    }
    
    while ($rightIndex < count($right)) {
        $result[] = $right[$rightIndex++];
    }
    
    return $result;
}

优化版本（减少内存分配）

function mergeSortOptimized(array &$array, $left = 0, $right = null) {
    if ($right === null) {
        $right = count($array) - 1;
    }
    
    if ($left < $right) {
        $mid = (int) (($left + $right) / 2);
        mergeSortOptimized($array, $left, $mid);
        mergeSortOptimized($array, $mid + 1, $right);
        mergeOptimized($array, $left, $mid, $right);
    }
}

function mergeOptimized(array &$array, $left, $mid, $right) {
    $temp = [];
    $i = $left;
    $j = $mid + 1;
    
    while ($i <= $mid && $j <= $right) {
        if ($array[$i] < $array[$j]) {
            $temp[] = $array[$i++];
        } else {
            $temp[] = $array[$j++];
        }
    }
    
    while ($i <= $mid) {
        $temp[] = $array[$i++];
    }
    
    while ($j <= $right) {
        $temp[] = $array[$j++];
    }
    
    for ($k = 0; $k < count($temp); $k++) {
        $array[$left + $k] = $temp[$k];
    }
}

三、使用示例

基本使用

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

优化版使用

$data = [34, 7, 23, 32, 5, 62];
mergeSortOptimized($data);
print_r($data);
// 输出: [5, 7, 23, 32, 34, 62]

处理关联数组

function mergeSortAssoc(array $array, string $key): array {
    if (count($array) <= 1) {
        return $array;
    }
    
    $mid = (int) (count($array) / 2);
    $left = array_slice($array, 0, $mid);
    $right = array_slice($array, $mid);
    
    return mergeAssoc(
        mergeSortAssoc($left, $key),
        mergeSortAssoc($right, $key),
        $key
    );
}

function mergeAssoc(array $left, array $right, string $key): array {
    $result = [];
    $leftIndex = $rightIndex = 0;
    
    while ($leftIndex < count($left) && $rightIndex < count($right)) {
        if ($left[$leftIndex][$key] < $right[$rightIndex][$key]) {
            $result[] = $left[$leftIndex++];
        } else {
            $result[] = $right[$rightIndex++];
        }
    }
    
    return array_merge($result, array_slice($left, $leftIndex), array_slice($right, $rightIndex));
}

// 使用示例
$users = [
    ['name' => 'Alice', 'age' => 28],
    ['name' => 'Bob', 'age' => 22],
    ['name' => 'Charlie', 'age' => 25]
];
$sortedUsers = mergeSortAssoc($users, 'age');

四、性能比较

我们通过测试对比归并排序与PHP内置排序函数的性能：

// 生成10万个随机数
$largeArray = array_map(function() {
    return mt_rand(1, 1000000);
}, range(1, 100000));

// 测试归并排序
$start = microtime(true);
mergeSort($largeArray);
$mergeSortTime = microtime(true) - $start;

// 测试PHP内置排序
$start = microtime(true);
sort($largeArray);
$nativeSortTime = microtime(true) - $start;

echo "归并排序耗时: {$mergeSortTime}秒\n";
echo "内置sort()耗时: {$nativeSortTime}秒\n";

典型测试结果： - 归并排序：约0.8-1.2秒 - 内置sort()：约0.1-0.3秒

注意：PHP内置函数用C实现且经过高度优化，通常比纯PHP实现的算法更快。

五、应用场景

归并排序特别适合： 1. 需要稳定排序的场景 2. 处理超大规模数据（外部排序） 3. 链表排序（只需O(1)额外空间） 4. 需要并行处理的排序任务

六、总结

归并排序是理解分治算法的经典案例，虽然PHP中内置排序函数性能更优，但实现归并排序有助于： - 深入理解算法思想 - 处理特殊排序需求 - 为学习更复杂算法打下基础

通过本文的PHP实现，您可以灵活应用归并排序解决实际问题，或作为学习算法的实践案例。 “`