• 让天下没有难学的技术
    多数学员都来自推荐,这就是口碑的力量

归并算法

图2-归并排序核心思想
核心思想:不断的将大的数组分成两个小数组,直到不能拆分为止,即形成了单个值。此时使用合并的排序思想对已经有序的数组进行合并,合并为一个大的数据,不断重复此过程,直到最终所有数据合并到一个数组为止。

图3-归并排序“治”流程

代码实现:

登录后复制
/**
* 快排
* 时间复杂度:O(nlogn)
* 空间复杂度:O(n)
*/
def merge(left: List[Int], right: List[Int]): List[Int] = (left, right) match {
case (Nil, _) => right
case (_, Nil) => left
case (x :: xTail, y :: yTail) =>
if (x <= y) x :: merge(xTail, right)
else y :: merge(left, yTail)
}

发表评论

邮箱地址不会被公开。 必填项已用*标注