作者misaka0120 (野格炸弹)
看板Grad-ProbAsk
标题[理工] in place的定义
时间Mon Jan 27 11:39:16 2020
之前我查到的定义是只使用O(1)额外空间
那这样的话quick sort在call递回的时候
长出的stack就不只O(1)了 那应该不是in place
可是stackoverflow上面有人说
因为quick sort只会在自己的array上做比较跟修改
所以是in place
in place演算法的定义应该是什麽R
-----
Sent from JPTT on my Sony H9493.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.12.8.221 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1580096358.A.4EB.html
1F：→ cossetannie: quick sort也可以不用recursive的方式做 所以我觉得 01/27 11:54
2F：→ cossetannie: 应该算是in place 01/27 11:54
3F：推 FRAXIS: 不用 recursion 做的 quick sort 大部分都需要 stack 01/27 12:14
4F：→ gcobc19622: sorting in place指的应该跟额外的memory space无关， 01/27 12:25
5F：→ gcobc19622: 洪上课是说in place指的是在本身的array上操作，除了M 01/27 12:25
6F：→ gcobc19622: erge跟linear time的方法不是，其他都是in place 01/27 12:25