For partitioning the array ,the rough median of an unsorted array can be found in O(N) using the median of 5’s algorithm. It involves splitting the array into groups of 5 and finding the median of this group of 5 elements. The median of 5 elements can be found in at most 6 comparisons(How? Think!). Once you find the medians of all the groups, you again recursively divide these medians into groups of 5 and keep finding the medians until you reach the exact median. You can prove that this method is O(N) though the constant factor is too large for practical implementation. I think this algorithm is coded in the second answer on the link given above.You can look at Wikipedia page for details.

Now coming to the randomized implementation ,it has a worst case time of O(N^2) but on an average it runs in O(N). When you partition the array and recursively apply the algorithm, the equation for this will be something like T(N)=T(N/2) + O(N) assuming you split the array in half every time. T(N) = T(N/2)+ c * N where c is a constant. Therefore T(N)= c * N + c * (N/2) + c * (N/4)+ … = c * N * (1+ 1/2 + 1/4 + 1/8 + …) = c * N * 2 which is O(N).

The main argument that you must have against this proof is that the array will not be partitioned into equal halves every time as i have taken here. However if you assume that you are eliminating around 30% of the array every time instead of 50% above (i.e. 3:7 split instead of 5:5) ,you can prove that the algorithm will still be O(N) by using the recursive equation T(N) = T(7 * N /10) + O(N). (7/10 because i removed 30% and recursed on the remaining 70%).There are other better proofs for this but i think this will give you a rough idea about why we say it is O(N) average.