[理工] 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