題目：
輸入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>
