到底什么是inplace
记得当初写考古的时候也有看到这个字
上网查了资料
却都没有清楚定义
有没有能抽丝剥茧一下inplace的概念
今年好多学校都有考这个

只用到额外O(1)空间的就是inplace，依照这标准去算就可以判断了

在原本input空间用交换的方式排序

Dora大 可是我看有人写说QuickSort不是in place的

sorting in place就是只说只靠原来input的资料结构的

会考这个的学校都已经考完了

可是他是实作SWAP来排序的啊

quicksort是inplace 因为他的额外空间是靠递回的stack产生的跟排序无关

了解！！所以可以定义说如果是用SWAP来SORTING的都是inplace的吧ㄥ

不是吧 不是用SWAP就会是inplace是inplace只能用SWAPhttp://i.imgur.com/DmjD1RT.jpg

https://reurl.cc/RzMl9我考前看维基百科里面，确实把Quick定义成非inplace对！Dora大跟我看得一样，所以Quicksort怎么分类啊！！

补习的时候洪逸老师是讲quicksort是inplace可能这部分有争议吧我觉得

看来要去看原文书了 不过我那时候翻原文书怎么没看到inplace的定义啊

这个最好是去查学校的ptt 毕竟改考卷的是教授我本来也以为quicksort是inplace 现在看起来我也不知道惹

照百科上的定义，只要要用到递回的算法，因为至少要用一个Stack来追踪，所以就不是inplace。看很多人则是在意在排序过程中，有没有使用额外空间

这定义蛮无聊的 你用linked list实作还会in place？

感觉着重的点是有无额外空间？就是空间复杂度

https://i.imgur.com/WXbh5hM.jpg台大那题基准为最右 看起来应该是True?

楼上大大们 我看各个网络上的分类，有的是以上面说的空间复杂度去做判别的，也有是说因为quick一定会用到递回，递回使用额外的资料结构也就是stack来协助运作，所以非in place。症结点应该在是在sorting 的中间来看，还是以整个实作面来看。说实在的，讨论这个很无聊，又不会因为我们定义他是不是in place实作上会有差异，也没有in place额外会附带什么性质，纯粹是考题考出来一翻两瞪眼，事前有做准备也会因为个人观点不同而相左。纯粹碎念～

洪毅说 inplace ? 可是笔记我在看的时候写需递回就想说洪毅应该也认为不是 .. ?

cute大，给的图是说插入排序是inplace吧？还说看错了

第一张是quick的partition 第二张是in place定义https://i.imgur.com/lBYbkNH.png补一下 贴16页的原因 觉得考试照枫叶比较好

是说quicksort有分有无inplace的版本 就看教授认为是哪个了吧.. 然后额外用logn 太小就可以忽略 说是inplace的样子?