微软intern面经，求答案

回复 20# rayray81502


    you are right!! no need for any sort! 只要一个temp variable用来swap就够了，O(1)吧

不就是快排的其中一个步骤么
gboystal 发表于 2012-3-16 23:51

同感。。。

回复 42# ilovexiao77

快排中的partition是不稳定的

41楼和42楼是什么关系{:4_84:}

http://qing.weibo.com/1570303725/5d98eeed33000hcb.html

LZ可以看看这篇，时间O（nlogn），空间O（1）
国内面试也遇到过这题，貌似是腾讯，还是创新工场，还是淘宝忘了。不过比你这题更变态，时间要O（n）。

回复 20# rayray81502


    链表的话，这么做是o(n), 普通数组的话，是o(n^2)。人家说的是数组，估计默认都不是链表。在普通数组的情况下，用递归是o（ n lg(n) ）。

没看到2-3页回复，当我没说。。。