赚批币的时间又到了…
这次拖了一阵子才翻，该不会大家都已经写出来了吧（想必不太可能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) =