[理工] in place的定义 misaka0120 PTT批踢踢实业坊

[理工] in place的定义

楼主: misaka0120 (é‡Žæ ¼ç‚¸å½ˆ) 2020-01-27 11:39:16

之前我查到的定义是只使用O(1)额外空间
那这样的话quick sort在call递回的时候
长出的stack就不只O(1)了那应该不是in place
可是stackoverflow上面有人说
因为quick sort只会在自己的array上做比较跟修改
所以是in place
in place算法的定义应该是什么R

作者: cossetannie (paa) 2020-01-27 11:54:00

quick sort也可以不用recursive的方式做所以我觉得应该算是in place

作者: FRAXIS (喔喔) 2020-01-27 12:14:00

不用 recursion 做的 quick sort 大部分都需要 stack

作者: gcobc19622 2020-01-27 12:25:00

sorting in place指的应该跟额外的memory space无关，洪上课是说in place指的是在本身的array上操作，除了Merge跟linear time的方法不是，其他都是in place

继续阅读

[理工] 交大 104 线代ok8752665 计组_修改程式错误fmtshk [理工] 中央108shinle14 [理工] 107中央资演17 105交大59gcobs226484 [理工] 计组下 53 & 58lucy35 [理工] 中央103计系ponwar87123 102清大计系chiuchang [理工] 103中央资演两题ponwar87123 [理工] 08电机丙离散bochengchen [理工] 103中央离散必要但不充分ponwar87123