归并排序是一种基于分治思想的排序算法，利用递归将数组分割成若干子数组，再将它们合并为有序数组。归并排序稳定且效率较高，适用于大规模数据的排序。
目录
算法思路
归并排序采用分治法将问题分解为若干个小问题。基本步骤如下：
- 分解：将数组不断二分，直到每个子数组只含一个元素（单个元素视为有序）。
- 合并：将两个有序子数组合并成一个新的有序数组，逐步向上归并，直至整个数组有序。
这种分而治之的策略保证了排序过程的稳定性，并能在 O(n log n) 的时间复杂度内完成排序。
PHP 代码实现
下面给出归并排序的 PHP 实现示例：
<?php
// 归并排序函数
function mergeSort(array $arr): array {
$n = count($arr);
if ($n <= 1) {
return $arr;
}
$mid = (int)($n / 2);
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid);
// 分别对左右部分排序
$left = mergeSort($left);
$right = mergeSort($right);
// 合并排序好的子数组
return merge($left, $right);
}
// 合并两个有序数组
function merge(array $left, array $right): array {
$result = [];
$i = $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++];
}
while ($j < count($right)) {
$result[] = $right[$j++];
}
return $result;
}
// 测试示例
$data = [38, 27, 43, 3, 9, 82, 10];
echo "排序前: " . implode(", ", $data) . "\n";
$sorted = mergeSort($data);
echo "排序后: " . implode(", ", $sorted) . "\n";
?>
输出示例：
排序前: 38, 27, 43, 3, 9, 82, 10
排序后: 3, 9, 10, 27, 38, 43, 82
时间复杂度分析
| 情况 | 时间复杂度 |
|---|---|
| 最佳情况 | O(n log n) |
| 最坏情况 | O(n log n) |
| 平均情况 | O(n log n) |
归并排序在所有情况下均保持 O(n log n) 的时间复杂度。此外，归并排序是稳定排序，但由于需要额外的空间来存储合并结果，其空间复杂度为 O(n)。
适用场景与优势
- 大规模数据排序：归并排序适合于数据量较大且数据随机分布的情况，能保持较高的效率。
- 稳定性要求高：归并排序在合并过程中不会改变相同元素的相对顺序，因此是一种稳定排序。
- 外部排序：当数据量过大无法全部载入内存时，归并排序特别适用，比如磁盘归并排序。
- 并行化优势：由于归并排序采用分治思想，各个子问题可以并行处理，有利于分布式计算环境下的优化。
练习题
- 递归实现与非递归实现：分别用递归和非递归方式实现归并排序，并对比两种方法的性能和代码复杂度。
- 空间优化：尝试在归并排序中原地排序，减少额外空间的使用，讨论其可行性和实现难度。
- 归并排序与其他排序算法比较：在相同数据集上实现归并排序、快速排序和堆排序，比较它们在最佳、最坏和平均情况的性能差异。
- 扩展练习：将归并排序应用于链表排序，实现对链表的归并排序算法，并分析时间和空间复杂度。
相关链接
🔗 GeeksforGeeks – Merge Sort
🔗 Algorithm Visualizer – Merge Sort
🔗 Wikipedia – Merge Sort
参考资料
- 《算法导论》—— Thomas H. Cormen 等
- 《数据结构与算法分析》—— Mark Allen Weiss
- GeeksforGeeks – Sorting Algorithms
归并排序凭借其稳定性和一致的 O(n log n) 时间复杂度，成为处理大规模数据排序的经典算法。通过理解分治思想和归并过程，你可以更高效地实现排序，并在实践中不断优化和改进。Happy Coding! 🚀
发表回复