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++程序算法设计的学习有所帮助。
热门推荐
10 新年祝福语大全 简短情侣
11 写春节祝福语简短的
12 退休祝福语简短独特老师
13 新年至客户祝福语简短
14 婚礼伴娘祝福语大全简短
15 牛年祝福语简短走心
16 结婚伴娘祝福语简短精辟
17 简短的古文春节祝福语
18 给儿子新婚祝福语简短