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++程序算法设计的学习有所帮助。