C++实现查找中位数的O(N)算法和Kmin算法
本文实例讲述了C++实现查找中位数的O(N)算法和Kmin算法，分享给大家供大家参考。具体方法如下：
利用快速排序的partition操作来完成O(N)时间内的中位数的查找算法如下：
#include<iostream>
#include<cassert>
#include<algorithm>
#include<iterator>
usingnamespacestd;
intarray[]={1,2,10,8,9,7,5};
constintsize=sizeofarray/sizeof*array;
intpartition(int*array,intleft,intright)
{
if(array==NULL)
return-1;
intpos=right;
right--;
while(left<=right)
{
while(left<pos&&array[left]<=array[pos])
left++;
while(right>=0&&array[right]>array[pos])
right--;
if(left>=right)
break;
swap(array[left],array[right]);
}
swap(array[left],array[pos]);
returnleft;
}
intgetMidIndex(int*array,intsize)
{
if(array==NULL||size<=0)
return-1;
intleft=0;
intright=size-1;
intmidPos=right>>1;
intindex=-1;
while(index!=midPos)
{
index=partition(array,left,right);
if(index<midPos)
{
left=index+1;
}
elseif(index>midPos)
{
right=index-1;
}
else
{
break;
}
}
assert(index==midPos);
returnarray[index];
}
voidmain()
{
intvalue=getMidIndex(array,size);
cout<<"value:"<<value<<endl;
}
寻找kmin算法如下：
intfindKMin(int*array,intsize,intk)
{
if(array==NULL||size<=0)
return-1;
intleft=0;
intright=size-1;
intindex=-1;
while(index!=k)
{
index=partition(array,left,right);
if(index<k)
{
left=index+1;
}
elseif(index>k)
{
right=index-1;
}
else
{
break;
}
}
assert(index==k);
returnarray[index];
}
希望本文所述对大家C++程序算法设计的学习有所帮助。