楼主:
kurc (辛拉面)
2015-01-28 13:19:38题目如下:
http://i.imgur.com/gfkrFsm.png
http://i.imgur.com/X33UFng.png
一开始看以为是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
给大家参考囉,如果有问题可以再讨论
作者:
APE36 (PT乡民)
2015-01-28 13:26:00pivot取中间值后就开始sort,比较好奇是(3)是否也是同样Quick的Worst Case
是quick sort吧,细节有点不同但原理一样,会觉得怪应该是因为第一次选到的是worst case第一次做完4应该在第一个哦,注意他for loop中有个casei不会变
楼主:
kurc (辛拉面)
2015-01-28 15:03:00喔喔感谢G大! 整个突破盲点! 我完全没发现第二个if没有++i这样就是标准的quick sort没错,感恩~
trace code你会发现他把比pivot大的摆在pivot左边小的放右边
作者: killerw74 (killerw74) 2015-01-29 02:08:00
想问大家 这题第二题写多少...