查找第K个元素(1) 之 快速排序的简单应用(5种不同方法)

前言:

查找第K个元素问题就是: 给你一个无序的数组, 让你返回这个数组里面第K大(或者第K小)的元素. 这个问题有很多讨论, 这里我自己总结一番.

总结:

这个问题基本上有两个很好的解答资源可以参考(其他也可以google出很多网上的资料).

(1) 编程之美2.5节, 里面基本上介绍了五种解法:

(a) 排序O(NlogN) 或者O(KN);

(b) 快速排序, 平均时间O(N), 最坏的可以是O(N^2), 这里书里面是不管怎么样都两边都排序, 所以书里面的平均时间复杂度是O(NlogN), 而我说的平均线性时间的复杂度, 是说只排序一边的情况, 这个方法是我们这里的重点, 稍后重点说.

(c) 二分搜索第K个元素, 在数据分布比较好的情况下也是O(NlogN);

(d) 建立一个大小是K的堆, 然后线性扫每个元素, 并且根据大小情况更新堆, 时间复杂度O(NlogK)

(e) 哈希统计每个数字的频率, 时间复杂度和最大的数有关

(2) 算法导论第九章.

算法导论里面讨论的主要是利用快速排序的思想进行解答的, 同时算法导论中还给出了能够保证最坏情况下也是线性的算法**Median of Medians **算法, 这是我们下一篇的重点.

那么有兴趣的人可以去找上面这个两个资料看看各种方法的解答, 这里主要介绍利用快速排序着无序数组中的第K个元素.

快速排序(quick sort)应用:

这个问题最直观的想法就是先排序再直接找第K的元素. 这种方法效率不高或者说效率有很多提升的空间的原因是我们只需要找到第K个元素, 并不需要保证K前面以及K后面的元素是排序好的. 所以这部分的排序可以进一步提升效率. 那么具体来讲就是利用快速排序里面的partition函数. partition函数可以在线性时间内将选出的pivot元素放到正确的位置, 比如pivot是第q小的元素, 那么partition就会把pivot放在位置q上, 同时保证q后面的都是比q大的元素, q前面的都是比q小的元素(假设所有元素不相同). 有了这个以后我们就可以判断了, 如果q正好是第K个元素那么直接返回, 如果q是比第K个元素小的, 那么说明第K个元素在q的后半部分, 我们递归处理, 剩下一种情况就是第K个元素在q的前半部分, 也同样递归处理. 这个算法的平均时间复杂度是O(N), 因为每次只搜半边, 最坏的情况O(N^2). 实际时间复杂度完全取决于pivot选取的好坏, 在”查找第K个的元素(2) 之 Median of Medians Algorithm“中我们介绍能够保证最坏时间复杂度也是线性(常数较大)的的Median of Medians算法并给出代码.

代码:

上述算法的C++源代码如下:

int partition1(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 select1(int A[], int p, int r, int k) {
    if(p < r) {
        int q = partition1(A, p, r);
        int real_kth = q - p + 1;
        if(k == real_kth)
            return A[q];
        else if(k > real_kth)
            return select1(A, q + 1, r, k - real_kth);
        else
            return select1(A, p, q - 1, k);
    }
    else if(p == r) {
        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