作者:zhanhailiang 日期:2012-12-17

问题：已知序列A[1…n]，及整数k, 1?k?n，试查找A中第k小的数

这个问题一般被称为顺序统计或选择问题。常规思路是对A[1…n]进行排序取第k的元素即可。但本文将介始一种算法来高效的获取第k小的元素。该算法思想和快速排序相同。在快速排序中，序列被支点分割成两个子序列，然后分别对这两个子序列递归排序。现在我们要先确定第k小的元素在哪个子序列中，然后只需对那个子序列递归排序即可。不必考虑其余的数。

/****************************************************************
算法：selection(A, n, k)
输入：A[1...n],k
输出：第k小的元素
    select(A, 1, n, k)
 
select(A, low, high, k)
    if low == high
        return low;
    else 
        split(X, low, high); // 用X[low]来分割数组X
        Let middle be the output of Partition
        if middle - low + 1 >= k then 
            return select(A, low, middle, k);
        else
            return select(A, middle + 1, high, k-(middle-low+1));
    end
****************************************************************/
function split(array, low, high) {
    var i = low;
    var x = array[low];
    for(var j = low + 1; j <= high; j++) {
        if(array[j] <= x