每天一算法（查找最小的k个元素（数组））

题目：

输入n个整数，输出其中的k个最小数。

例如：

例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
解题思路：
当然，方法最简单的就是对这n个整数都进行排序操作，但这种方法的时间复杂度尤其的高。
因此，我采用了，用另外k个空间，以换取时间的方法。每次从输入的n个整数中读入一个数。如果数组中已经插入的元素少于k个，则将读入的整数直接放到数组中。否则就是长度为k的数组已经满了，不能再往数组里插入元素，只能进行替换了。
如果读入的这个整数比数组中已有k个整数的最大值要小，则用读入的这个整数替换这个最大值；如果读入的整数比数组中已有k个整数的最大值还要大，则读入的这个整数不可能是最小的k个整数之一，抛弃这个整数。这种思路相当于只要排序k个整数，因此时间复杂可以降到O(n+nlogk)。通常情况下k要远小于n，所以这种办法要优于前面的思路。

VS2010中运行程序如下：例子程序是正确的，，如果有什么错误，希望各位高手指定，，呵呵。。
[cpp]
<span style="font-size:18px;">#include<iostream>
#include<limits.h>
using namespace std;
#define N 100
#define K 5

void bubble_sort_k(int array[],int num)
{
    int i = 0;
    int j = 0;
    //int flag = 0;
    int temp = 0;
    for(i = 0;i < num; i++)
    {
        //flag = 1;
        for(j = i+1; j < num; j++)
        {
            if(array[i] > array[j])
            {
                temp = array[j];
                array[j] = array[i];
                array[i] = temp;
                //flag = 0;
            }
        }
        //if(flag == 1)
        // break;
    }
    return;
}

int main()
{
    int array_n[N] = {INT_MAX};
    //int array_n[N] = {9,8,7,6,5,4,3,2,1};
    int array_k[K] = {INT_MAX};
    int i = 0;
    int j = 0;
    int m = 0;
    int number = 0;
    while(cin>>i)
    {

        array_n[number] = i;
        number++;
    }
    //number = 9;
    for(j=0;j<K;j++)
    {
        array_k[j] = array_n[j];
    }

    bubble_sort_k(array_k,K);

    for(i = K;i<number;i++)
    {
        for(j = 0;j<K;j++)//从数组最小的元素开始比较
        {
            if(array_n[i] < array_k[j])
            {
                for(int n = K-1;n > j;n--)//找到该数比哪个元素小之后，将其后的部分后移，即将最大元素移出数组。
                {
                    array_k[n] = array_k[n-1];
                }
                array_k[j] = array_n[i];
                break;
            }
        }
    }
    for(m=0;m<K;m++)
    {
     cout<<array_k[m]<<endl;
    }
    return 0;
}
</span>

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