共计 1207 个字符，预计需要花费 4 分钟才能阅读完成。
算法原理
下列动图来自 @五分钟学算法，演示了归并算法的原理和步骤。
原理:
利用递归，先拆分、后合并、再排序。
步骤:
均分数列为两个子数列
递归重复上一步骤，直到子数列只有一个元素
父数列合并两个子数列并排序，递归返回数列
代码实现
// 归并排序主程序
function mergeSort($arr) {
$len = count($arr);
if ($len <= 1) {
return $arr;
} // 递归结束条件, 到达这步的时候, 数组就只剩下一个元素了, 也就是分离了数组
$mid = intval($len / 2); // 取数组中间
$left = array_slice($arr, 0, $mid); // 拆分数组 0 -mid 这部分给左边 left
$right = array_slice($arr, $mid); // 拆分数组 mid- 末尾这部分给右边 right
$left = mergeSort($left); // 左边拆分完后开始递归合并往上走
$right = mergeSort($right); // 右边拆分完毕开始递归往上走
$arr = merge($left, $right); // 合并两个数组, 继续递归
return $arr;
}
// merge 函数将指定的两个有序数组 (arrA, arr) 合并并且排序
function merge($arrA, $arrB) {
$arrC = array();
while (count($arrA) && count($arrB)) {
// 这里不断的判断哪个值小, 就将小的值给到 arrC, 但是到最后肯定要剩下几个值,
// 不是剩下 arrA 里面的就是剩下 arrB 里面的而且这几个有序的值, 肯定比 arrC 里面所有的值都大所以使用
$arrC[] = $arrA[0] < $arrB[0] ? array_shift($arrA) : array_shift($arrB);
}
return array_merge($arrC, $arrA, $arrB);
}
测试:
$startTime = microtime(1);
$arr = range(1, 10);
shuffle($arr);
echo “before sort: “, implode(‘, ‘, $arr), “\n”;
$sortArr = mergeSort($arr);
echo “after sort: “, implode(‘, ‘, $sortArr), “\n”;
echo “use time: “, microtime(1) – $startTime, “s\n”;
时间复杂度
归并排序的时间复杂度是 O(N*lgN)。
假设被排序的数列中有 N 个数。遍历一趟的时间复杂度是 O(N)，需要遍历多少次呢？
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是 O(N*lgN)。
参考资料
归并排序
十大经典排序算法动画与解析
感谢您的阅读，觉得内容不错，点个赞吧 ????
原文地址: https://shockerli.net/post/me…
