为什么归并排序必须要新建一个数组来存临时数据呢？

首页课程实战体系课手记专栏慕课教程

为什么归并排序必须要新建一个数组来存临时数据呢？

来源：3-3 归并排序法的优化

小胖鼠

2018-01-16

不理解为何什么要新建一个数组

写回答

1回答

liuyubobobo

liuyubobobo

2018-01-17

已采纳

因为没有辅助数组，将无法在线性时间里完成这个merge的过程。

可以自己尝试一下，如果不创建临时数组，看能不能实现merge这个子函数？：）

0

2

liuyubobobo

回复

小胖鼠

大赞！另外值得一提的是，如果两个有序列表以链表的形式存储，在merge的过程中就不需要辅助空间了：）

2018-01-17

共2条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

归并排序求逆序数

回答 1

自底向上归并排序在2^n+1大小的数据集上是否性能会比较差？

回答 1

为何有递归的自顶向下的排序方法要快？

回答 2

归并排序的过程中数据为什么不会错乱？

回答 1

老师，我用归并排序思想解逆序对居然超时了，求解。

回答 1

打开慕课网App查看更多内容