内容简介:下列动图来自利用递归,先拆后合并排。
算法原理
下列动图来自 @五分钟学算法 文章,演示了归并算法的原理和步骤。
原理:
利用递归,先拆后合并排。
步骤:
- 均分数列为两个子数列
- 递归重复上一步骤,直到子数列只有一个元素
- 父数列合并两个子数列并排序,递归返回数列
代码实现
// 归并排序主程序 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)
。
参考资料
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Python深度学习
[美] 弗朗索瓦•肖莱 / 张亮 / 人民邮电出版社 / 2018-8 / 119.00元
本书由Keras之父、现任Google人工智能研究员的弗朗索瓦•肖莱(François Chollet)执笔,详尽介绍了用Python和Keras进行深度学习的探索实践,涉及计算机视觉、自然语言处理、生成式模型等应用。书中包含30多个代码示例,步骤讲解详细透彻。由于本书立足于人工智能的可达性和大众化,读者无须具备机器学习相关背景知识即可展开阅读。在学习完本书后,读者将具备搭建自己的深度学习环境、建......一起来看看 《Python深度学习》 这本书的介绍吧!