[理工] [资结] 102交大资演 第9题

楼主: 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:00
pivot取中间值后就开始sort,比较好奇是(3)是否也是同样Quick的Worst Case
作者: galapous (墨)   2015-01-28 14:29:00
是quick sort吧,细节有点不同但原理一样,会觉得怪应该是因为第一次选到的是worst case第一次做完4应该在第一个哦,注意他for loop中有个casei不会变
楼主: kurc (辛拉面)   2015-01-28 15:03:00
喔喔感谢G大! 整个突破盲点! 我完全没发现第二个if没有++i这样就是标准的quick sort没错,感恩~
作者: AgentSkye56 (大安周渝民)   2015-01-28 21:04:00
还是看不懂QQ"有人大大会详细的做法吗~~
作者: galapous (墨)   2015-01-28 22:16:00
trace code你会发现他把比pivot大的摆在pivot左边小的放右边
作者: killerw74 (killerw74)   2015-01-29 02:08:00
想问大家 这题第二题写多少...
作者: galapous (墨)   2015-01-29 09:30:00
5

Links booklink

Contact Us: admin [ a t ] ucptt.com