PHP 合并排序法

封面图 • 2025-12-17 • PHP

“PHP 合并排序法”通常指的是在 PHP 中实现 **归并排序（Merge Sort）** 算法。归并排序是一种基于分治策略的高效排序算法，时间复杂度为 **O(n log n)**，适用于各种数据规模。

---

## 📌 什么是归并排序？

归并排序的基本思想是：

1. **分解**：将数组分成两半，递归地对每一半进行归并排序。
2. **合并**：将已排序的两部分合并成一个有序数组。

---

## ✅ PHP 实现归并排序

```php
<?php

function mergeSort($arr) {
    // 如果数组长度小于等于1，直接返回
    if (count($arr) <= 1) {
        return $arr;
    }

// 分割数组
    $mid = count($arr) / 2;
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);

// 递归排序左右子数组
    $left = mergeSort($left);
    $right = mergeSort($right);

// 合并两个已排序的数组
    return merge($left, $right);
}

function merge($left, $right) {
    $result = [];
    $i = 0;
    $j = 0;

// 比较左右两个数组的元素，按顺序放入结果数组
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] < $right[$j]) {
            $result[] = $left[$i];
            $i++;
        } else {
            $result[] = $right[$j];
            $j++;
        }
    }

// 将剩余的元素追加到结果数组中
    while ($i < count($left)) {
        $result[] = $left[$i];
        $i++;
    }

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

return $result;
}

// 示例用法
$array = [38, 27, 43, 3, 9, 82, 10];
$sortedArray = mergeSort($array);
print_r($sortedArray);
```

---

## 🔍 输出示例

```
Array
(
    [0] => 3
    [1] => 9
    [2] => 10
    [3] => 27
    [4] => 38
    [5] => 43
    [6] => 82
)
```

---

## ⚠️ 注意事项

- `array_slice` 是 PHP 中用于切片数组的函数。
- 归并排序是 **稳定排序算法**（相同元素的相对顺序不会改变）。
- 由于需要额外的空间来存储临时数组，空间复杂度为 **O(n)**。

---

## 🧠 为什么选择归并排序？

- 时间复杂度稳定为 O(n log n)，适合大数据量。
- 对于链表结构（如 PHP 的数组），归并排序效率较高。
- 适合外部排序（当数据量太大无法全部加载到内存时）。

---

如果你有更具体的使用场景或需要优化版本，请告诉我！