查找第K个元素(2) 之 Median of Medians Algorithm

前言:

在上一篇”查找第K个元素(1) 之 快速排序的简单应用“中, 我们已经讨论了如何利用快速排序的思想进行查找第K个元素, 同时我们指出实际算法的效率取决于pivot选取的好坏. 这里我们讨论的Median of Medians Algorithm可以保证最坏情况下也是线性时间, 尽管这个算法的常数可能比较大, 实际效果也不会太好, 但是理论上他确实做到了线性时间的最坏时间复杂度(详细参考请参阅算法导论第九章).

Median of Medians Algorithm:

这个算法有如下步骤:

(1) 把整个数组分成groups, 每个group有5个元素, 最后一个group可能含有少于5个的元素. 找到这写group的中位数(Median)

(2) 把步骤一中的这写个中位数组成一个新的数组, 递归调用当前算法找到这些中位数中的中位数(假设有M个这样的中位数, 就是递归调用当前算法找到这写中位数的第M/2个元素). 这里注意的是不要使用其他算法, 而是直接递归调用当前算法去着中位数.

(3) 把找到的中位数当成我们的pivot, 然后利用快速排序的思想, 把这个pivot放到这个正确的位置, 后面的思路和以前”查找第K个元素(1) 之 快速排序的简单应用“一样.

分析:

Median of Medians的算法的巧妙之处在于第(2)步, 递归调用当前算法, 这样找到的pivot能保证在这个pivot之前一定有至少0.3N的数, 在这个pivot之后的也至少有0.3N的数, 从而, 每次partition不会出现数据倾斜(基本上整个数组都在pivot之后或者之前), 理论分析这个算法的时间复杂度是O(N) . 具体证明细节请参考算法导论.

代码:

c++源代码如下, 由于常数比较大, 试了几个OJ, 基本上是超时(其他测试正确, 大数据超时), 所以实际效果并不一定好.

int partition2(int A[], int p, int r) {
    int x = A[r];
    int i = p;
    for(int j = p; j < r; ++j) {
        if(A[j] <= x) swap(A[i++], A[j]);
    }
    swap(A[i], A[r]);
    return i;
}

int select2(int A[], int p, int r, int k) {
    if(p < r) {
        int tmp[r - p];
        int cnt = 0;

        // (1) divide groups
        for(int i = p; i < r; i += grp_size) {
            tmp[cnt++] = medien5(A, i, min(i + grp_size - 1, r)); // median5 return the median number
        }
        // step (2) in the above description
        int x = select2(tmp, 0, cnt - 1, (cnt + 1)/ 2);
        // make the last element x
        for(int i = p; i <= r; ++i) {
            if(x == A[i]) {
                swap(A[i], A[r]);
                break;
            }
        } // set the pivot in the last postion

        // the following is the same as before
        int q = partition2(A, p, r);
        int real_kth = q - p + 1;
        if(k == real_kth)
            return A[q];
        else if(k > real_kth)
            return select2(A, q + 1, r, k - real_kth);
        else
            return select2(A, p, q - 1, k);
    }
    else if(p == r) { // n is 1
        if(1 == k) return A[p];
        else
            throw k_out_of_bound;
    }
    else
        throw no_valid_range;
    return undefined;
}

(Please specify the source  烟客旅人 sigmainfy — http://www.sigmainfy.com  as well as the original permalink

URL for any reprints,  and please do not use it for commercial purpose)

Written on September 7, 2013