题目如下:
![]()
![]()
一开始看以为是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))
附上昨天怒打的验证XD http://goo.gl/ePgIJ0
给大家参考囉,如果有问题可以再讨论