賺批幣的時間又到了…
這次拖了一陣子才翻，該不會大家都已經寫出來了吧（想必不太可能XD）
====
6.1 排序（Sorting）與雜湊（Hashing）
(1) 感謝名沅幫忙翻譯這一題
考慮以下修改過的隨機挑選基準(pivot)的快速排序法，以尋找第k小的元素。當k被
平均隨機挑選時（「平均」指的是每個元素被挑選到的機率是相同的），以C(N)表示使用
此演算法時，預期的比較次數。試導出C(N)的封閉型式(closed-form)解。你可以在你解
答中使用調和級數的和 H(N)=Σ(n=1 to N)1/n, which is O(log N)。
Quick-k(陣列 a, 整數 N, 整數 k) /* 1 <= k <= N */
‧從a[0]至a[N-1]平均隨機選擇一個元素作為基準值(pivot)
‧對基準值以外的a[0]至a[N-1]和基準比較（一共比較N-1次），
比基準值小的隨機存到另一個M-1個元素長的陣列left；
比基準值大的隨機存到另一個N-M個元素長的陣列right。
如果 k = M 就
回傳 基準值
否則如果 k < M 就
回傳 Quick-k(left, M-1, k)
否則
回傳 Quick-k(right, N-M, k-M)
結束如果
提示：Quick-k參數為N, k時，令其比較次數為 T(N, k)。從此演算法可得
1 k-1 N
T(N, k) =