問題描述：給定的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個數，雖然第二種方法比第一種方法慢一些，但是它並不修改原始數據，另外比較適用於海量數據處理的情形。因此兩種方法各有優劣，實際應用時視具體情況確定算法的選用。
