int Partition(double *Array,int left,int right)
{
double pivot=Array[left];
int i=left;
double tmp;
for (int j=left+1;j<=right;j++)
{
if (Array[j]<=pivot)
{
i++;
tmp=Array[j];
Array[j]=Array[i];
Array[i]=tmp;
}
}
//exchange A[i],pivot
tmp=Array[left];
Array[left]=Array[i];
Array[i]=tmp;
return i;
}
void K_Big(double* Array,int left,int right,int k,double *dest)//
{
if (k<=0)
{
return;
}
if (right-left+1<=k)
{
memcpy(dest,&Array[left],sizeof(double)*(right-left+1));
return;
}
int p=Partition(Array,left,right);
int right_ele_num=right-p;
if (right_ele_num>=k)//取右边的前k个
{
K_Big(Array,p+1,right,k,dest);
}
else{
//取左边的k-right_ele_num-1个，加上中间一个,再加上右边的right_ele_num个
right_ele_num++;//把中间的一个也加进来了。
memcpy(&dest[k-right_ele_num],&Array[p],right_ele_num*sizeof(double));
K_Big(Array,left,p-1,k-right_ele_num,dest);
}
}
void main()
{
double A[]={8,4,3,2,6,13,5};
int n=7;
//MergeSort(&A[0],0,6);
//QuickSort(A,0,6);
//HeapSort(A,7);
/*for (int i=0;i<n;i++)
{
cout<<A[i]<<" ";
}*/
double B[5];
int k=5;
K_Big(A,0,6,k,B);
for (int i=0;i<k;i++)
{
cout<<B[i]<<endl;
}
cout<<endl;
delete A;
}
Homepage:
http://www.zoumin.org/