快排的内存都去哪儿了？

MTC · 2014-10-22 20:33:34

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

看书写归并排序内存O（N）是排序算法里最大的，尼玛他和快排不是开一样的数组吗？

1guangnian · 2014-10-23 01:21:02

归并实现的时候，需要一个辅助数组吧

MTC · 2014-10-23 09:26:55

1guangnian 发表于 2014-10-23 01:21
归并实现的时候，需要一个辅助数组吧

是递归调用完成后合并的操作需要额外数组还是分类数组的时候需要？

1guangnian · 2014-10-23 09:45:38

MTC 发表于 2014-10-23 09:26
是递归调用完成后合并的操作需要额外数组还是分类数组的时候需要？

merge的时候

readman · 2014-10-23 09:48:00

MTC 发表于 2014-10-23 09:26
是递归调用完成后合并的操作需要额外数组还是分类数组的时候需要？

有in-place的

doveonthewing · 2014-10-23 11:08:43

对于每一步的divide，有in-place的方法。
但是我见过的所有快排都是递归做的，递归会有栈空间的消耗(log(n))。

daihao0310 · 2014-10-23 23:08:29

主要是递归过程中对上层递归的记录吧……

MTC · 2014-10-24 11:08:21

doveonthewing 发表于 2014-10-23 11:08
对于每一步的divide，有in-place的方法。
但是我见过的所有快排都是递归做的，递归会有栈空间的消耗(log(n ...

哦，懂了，不是in-palce的就是开的两个数组+递归的开销，O（N+logN）=O（N），for in-place just O(logN),cuz we dont use any extra arrays,right?