最小的K个数

问题描述：给定的n个整数，计算其中最小的K个数。
最直观的解法莫过于将n个数按升序排列后输出前k个。但是就效率来看，这种方法并不是最理想的。一种改进方法是借助快速排序中对数组的划分，以第k个元素对数组进行划分，使得比第k个数字小的数字都在其左边，比其大的数字都在它的右边。
[cpp]
void Swap(int &a, int &b)
{
    int c = a; a = b; b = c;
}

int Partition(int data[], int length, int start, int end)
{
    if(data == NULL || length <= 0)
        return -1;

    int index = start - 1;
    for(int i = start; i < end; ++i)
    {
        if(data[i] < data[end])
        {
            ++index;
            swap(data[i], data[index]);
        }
    }
    ++index;
    Swap(data[index], data[end]);
    return index;
}

void GetKLeastNumbers(int data[], int length, int result[], int k)
{
    if(data == NULL || length <= 0 || result == NULL || k <= 0)
        return;

    int start = 0, end = length - 1;
    int index = Partition(data, length, start, end);

    while(index != k - 1) // 第k个数作为数组划分依据
    {
        if(index > k - 1)
            index = Partition(data, length, start, index - 1);
        else
            index = Partition(data, length, index + 1, end);
    }
    for(int i = 0; i < k; ++i)
        result[i] = data[i];
}
通过分析可以确定算法的时间复杂度是O(n)，是一种比较高效的解法。但是上述算法存在的问题是修改了原始数组数据，因此在不允许修改原始数据的情况下的应用就会受到限制。
在不修改原始数据的前提条件下，我们可以创建一个大小为k的容器存放最小的k个数。再对n个整数进行遍历，如果容器中的数少于k个，则直接把读入的数存入容器；如果容器中的数大于等于k个，同时当前读入的数小于容器中最大的数，那么删除容器中最大的数，将该数读入容器，否则不做操作。为了确保快速删除容器中最大的数，容器数据的存储可以考虑使用最大堆。由于最大堆的根结点的值大于它的子树中任意结点的值，因此可以在O(1)得到已有k个数中的最大者，删除和插入操作的时间则为O(lgk)。对n个数重复最大堆的插入、删除操作总的算法时间复杂度为O(nlgk)。下面是使用STL multiset完成上述算法的实现代码。
[cpp]
//建立最大堆保存最小的k个数
void GetKLeastNumbers(const int data[], int length, multiset<int, greater<int> > &result, int k)
{
    if(data == NULL || k < 1 || k > length) // 数据合法性判断
        return;

    result.clear();
    multiset<int, greater<int> >::iterator iter;
    for(int i = 0; i < length; ++i)
    {
        if(result.size() < k)
            result.insert(data[i]);
        else
        {
            iter = result.begin();
            if(*iter < *(result.begin()))
            {
                result.erase(iter);
                result.insert(data[i]);
            }
        }
    }
}

上述两种方法都实现求最小k个数，虽然第二种方法比第一种方法慢一些，但是它并不修改原始数据，另外比较适用于海量数据处理的情形。因此两种方法各有优劣，实际应用时视具体情况确定算法的选用。

补充：软件开发 , C++ ,