A.Which sorting method is the fastest one in average case?
1.merge sort 2.heap sort 3.quick sort 4.radix sort 5.bubble sort
答案给3但是4不是linear所以可以是O(n+e)吗?
B.randomized quicksort和quicksort的recurrence and solutin?
quicksort有分average and worst 那跟randomized差在哪呢??
是pivot比较不会是最小or最大吗?
C.Consider the failure function defined as below.Show the values of
f(o),f(1)...,f(5) of string p0p1p2p3p4p5=ababaa
f(j)={largest 0<=i<j such that p0...pi=pj-1...pj and pi+1 != pj+1
-1 if there is no i>=o satisfying above }
Ans: a b a b a a
-1 -1 0 1 2 0
不懂这题的意思@@"
希望各位帮我解惑 先谢谢了!

A 我记得快速排序的快取运用很好，平均很快。B 就是代表支点随便取的 quicksortC KMP algorithm

thanks!

所以A到底为啥quicksort比radix sort快? 是因为一般来说input值都很大吗?

记得没错，实作来说quicksort在所有sort里头平均最快的