>>66
少し考えてみたけど、O(N)でいきますね。
アルゴリズム示します。

(1)まずメディアンを求める。
(1-1)配列a[m]の中から小さい法からl個目を抜き出す関数f(a,m,l)を考える。
　　これに、m = N, l = N / 2を入れればいい。
(1-2)m個の数字を、その中のある数字を閾値にそれ以上(big)と以下(small)にわける。
(1-3)小さい方がs個だったとする。
(1-3-1) s < lなら、小さい方にメディアンがある。f(small,s-1,l)を呼び出す
(1-3-2) s > lなら、大きい方にメディアンがある。f(big, m-s, l-s)を呼び出す。

(2)　全ての数字について(1)で求まったメディアンとの差の絶対値を求める。
　これで、この差の絶対値から小さい方からk個抜き出すという問題に置き換わった。

(3)(1)と同様に大きいほう、小さい方にわけていく。これは、小さい方からk個目を
求め、その呼び出し関数のsmallに入っている数字は全て、小さいほうからk個の中に
入っていることになる。

計算量を検証します。
(1)上手く1/2ずつ絞り込めていけば。
N + 2/N + 4/N + 8/N + ..... = 2N
で計算できますので、O(N)。
まあ、実際にそんな上手くはいかないでしょうが、クイックソートがO(nlog(n))
の計算量というのと一緒ですね。

(2)N個の絶対値求めるだけなので、O(N)
(3)(1)と同様にO(N)