快速排序:求最小的 k 个数

编辑于 2017-01-21

* 移动设备下, 可左滑手指以查看较宽代码

思路

可以考虑使用堆,这里用类似快速排序的思想,如果选取枢纽随机化,可以做到平均 O(n) 的时间复杂度。

选取 S 中一个元素作为枢纽元 v,将集合 S 分割成 S1 和 S2 ,就像快速排序那样(|S|表示其长度)。

1)如果 k <= |S1|,那么第 k 个最小元素必然在 S1 中。在这种情况下,返回 QuickSelect(S1, k)。

2)如果 k = 1 + |S1|,那么枢纽元素就是第 k 个最小元素,即找到,直接返回它。

3)否则,这第 k 个最小元素就在 S2 中,即S2中的第(k - |S1| - 1)个最小元素,我们递归调用并返回 QuickSelect(S2, k - |S1| - 1)。

代码

#include <iostream>
#include <vector>
using namespace std;

int partion(vector<int>& input, int beg, int end)
{
    int key = input[beg];
    while (beg < end) {
        while (beg < end && input[end] >= key)end--;
        input[beg] = input[end];
        while (beg < end && input[beg] <= key)beg++;
        input[end] = input[beg];
    }
    input[beg] = key;
    return beg;
}
void qSort(vector<int> &input, int k, int l, int r)
{
    if(l>=r) return;
    //枢纽元
    int pos=partion(input, l, r);

    if (pos > k - 1)
        qSort(input, k, l, pos - 1);
    else if(pos < k-1)
        qSort(input, k, pos + 1, r);
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
    if (input.size() == 0 || input.size() < k || k <= 0) {
        input.clear();
        return input;
    }
    qSort(input, k, 0, input.size() - 1);
    vector<int> res(input.begin(), input.begin() + k);
    return res;
}

int main()
{
    int t[] = {4, 5, 1, 6, 2, 7, 3, 8};
    vector<int> a(begin(t), end(t));

    int K=4;

    vector<int> out=GetLeastNumbers_Solution(a, K);

    for(int i = 0; i < out.size(); i++)
        cout<<out[i]<<" ";

    return 0;
}