题目如下:




一开始看以为是quicksort
但是下去追踪后完全不是这一回事
整个都没排序到的感觉Orz
我自己做的部分: (这部分是错的，因为没注意到第二个else if没i++的结果)
第一次partiton，pivot是4，结束后 1 0 0 1 4 2 3 1 0 2
↑ ↑
low(值为-1) high(指向data[5])
补充正解（感谢galapous大提醒盲点）
第一次 parition 后：4 1 3 2 0 1 0 0 1 2 low=-1 high=1
第二次：　　　　　　　3 2 2 1 1 1 0 0 0 low=1 high=6
第三次：　　　　　　　3 2 　　　　　　　low=0 high=2
第四次：　　　　　　　　　　　　　0 0 0 low=-1 high=3　
final content : 4 3 2 2 1 1 1 0 0 0 (Ans(1))
partition invoked: 4次　(Ans(2))
这个是由大排到小的quick sort:　最差时间复杂度　size^2 (Ans(3))
附上昨天怒打的验证ＸＤ　http://goo.gl/ePgIJ0
给大家参考囉，如果有问题可以再讨论

pivot取中间值后就开始sort，比较好奇是(3)是否也是同样Quick的Worst Case

是quick sort吧，细节有点不同但原理一样，会觉得怪应该是因为第一次选到的是worst case第一次做完4应该在第一个哦，注意他for loop中有个casei不会变

喔喔感谢G大! 整个突破盲点! 我完全没发现第二个if没有++i这样就是标准的quick sort没错，感恩～

还是看不懂QQ"有人大大会详细的做法吗~~

trace code你会发现他把比pivot大的摆在pivot左边小的放右边

想问大家 这题第二题写多少...

5