經(jīng)常會出現(xiàn)求n個數(shù)中的前k個最小值(最大值），可以采取的策略為：
看n和k的大小，數(shù)組的規(guī)律。即便看情況也不一定有絕對的“最優(yōu)"
如果是基本有序的，那么就用Hoare的算法，每次選中間位置的數(shù)當軸。
如果k或(n-k)是小常數(shù)，那么部分排序算法，比如用堆。
如果要抵抗算法復雜度攻擊，那么可以考慮隨機Hoare或者linear
time selection.
在k為小值的時候，可以采用基于堆排序的部分排序方法：
代碼如下：
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <iterator>
using namespace std;
void min_heapify(int arr[],int i,int size)
{
int left = 2*i+1;
int right = left+1;
int largest;
if((left<=size)&&(arr[left]>arr[i]))
{
largest = left;
}
else
{
largest = i;
}
if((right<=size)&&(arr[right]>arr[largest]))
{
largest = right;
}
if(largest!=i)
{
int temp = arr[i];
arr[i]=arr[largest];
arr[largest]=temp;
min_heapify(arr,largest,size);
}
}
void fillarray(int arr[],int size)
{
for(int i=0;i<size;i++)
{
arr[i]=rand()%size;
}
}
void print(const int arr[],int size)
{
copy(arr,arr+size,ostream_iterator<int>(cout," "));
cout<<endl;
}
int main(int argc,char* argv[])
{
int size,k;
while(cin>>size)
{
int* buff=new int[size];
fillarray(buff,size);
print(buff,size);
cout<<"Please input the top k value:"<<endl;
cin>>k;
for(int i=(k-1)/2;i>=0;i--)
min_heapify(buff,i,k-1);
print(buff,size);
cout<<endl<<endl;
for(int i=size-1;i>=k;i--)
{
if(buff[i]<buff[0])
{
int temp = buff[0];
buff[0]=buff[i];
buff[i]=temp;
min_heapify(buff,0,k-1);
}
}
print(buff,size);
delete [] buff;
}
}