You select a random pivot and partition the array as you would in the quicksort algorithm. Then, based on the index of the pivot element, you know which half of the array the desired element lies in. For example, say n = 30, and after you select your pivot and partition the array, the first half has 10 elements (the half before the pivot). You know that the desired median should be the 4th smallest element in the larger half. To identify that, you partition the second half of the array and continue recursively.
The reason that this is not O(n log n) is that the recursive partition call is only on one half of the array, so the expected running time is n + (n/2) + (n/4) + (n/8) + ... = O(n).
sigh i understand the difference between quicksort and median -- their expected run time differ, one is nlogn and the other is linear. but worse cases are the same.
actually found the solution in CLRS(算法导论)
worse case linear time 是个挺复杂的办法,要分成5份。。。section 9.3...