1.归并排序

归并排序(MERGE-SORT) 是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

归并分割的意义:把整个数组分割为以个为单位。

简介

在这里插入图片描述
在这里插入图片描述

代码

在这里插入图片描述

分析

时间复杂度:O(N*logN)
空间复杂度:O(N)

归并的非递归形式

归并非递归形式可以用栈吗?
**不适合用栈。**原因在于快排用栈本质上是因为快排是一种前序遍历,遍历完之后就不需要再管原来的区间了,但是归并是先分而后并,是一种后序遍历, 栈很难控制,问题在于递归之后回不去了。

那如何解决?直接省略递归分割过程,直接去模拟回归的过程。

在这里插入图片描述

我们发现:
归并是消耗空间复杂度O(N)的,由于归并的这一特性可以做外排序(外排序就是在内存外即硬盘中进行排序)。


EOF

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部