对于一个非有序的数组A[p..r]，求数组中第k小的元素。
如何考虑
排序(部分排序）就不用说了。。o(nlgn)，当然如果在实际情况中要一直取值，当然要排序后，一次搞定，以后都是O(1)
我们这里提供了取一次最K小的一个o(n)的解法，
用了快速排序的一种思想，
关键在于划分只一个部分，我们知道快速排序选择一个pivot对数组进行划分，左边小于pivot，右边大于等于pivot，
所以我们计算左边小于pivot(加上pivot)的个数count总共有多少，如果等于k,正是我们所要的，如果大于k，说明第k小的
数在左边，那就在左边进行我们的递归；否则，在右边，那么说明右边的第k-count小的数就是我们所要的，在右边进行
我们的递归。
3.代码
当k>(r-p+1),返回最大值，当k<1,返回最小值
#include<iostream>
using namespace std;
#include<time.h> inline void Swap(int a[],int i,int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
} int Partition(int a[],int p,int r)//根据pivot a[r]来划分数组
{
int pivot=a[r];
int low=p-;
int i;
for(i=p;i<r;i++)
{
if(a[i]<=pivot)
Swap(a,++low,i);
}
Swap(a,++low,r);
return low;
} int RondomPartition(int a[],int p,int r)
{
int i=p+rand()%(r-p+);//随机选择一个pivot来划分
Swap(a,i,r);
return Partition(a,p,r);
} int SelectKMin(int a[],int p,int r,int k)
{
if(p==r)
return a[p];
int q=RondomPartition(a,p,r);
int count=q-p+;//计算 a[p..q]的元素数量
if(k==count)//刚好,返回
return a[q];
else if(k<count)//在前半部分
return SelectKMin(a,p,q-,k);
else //在后半部分
return SelectKMin(a,q+,r,k-count);
} const int N=;
const int K=;
int a[N]; int main()
{
int i;
for(i=;i<N;i++)
a[i]=i;
srand(unsigned(time(NULL)));
for(i=;i<K;i++){//获得0-100不重复随机数
Swap(a,i,i+rand()%(N-i));
}
int k;
while(cin>>k)
{
cout<<SelectKMin(a,,K-,k)<<endl;
}
return ;
}
本文实例讲述了C++实现查找中位数的O(N)算法和Kmin算法，分享给大家供大家参考。具体方法如下：
利用快速排序的partition操作来完成O(N)时间内的中位数的查找算法如下：
? #include <iostream>
#include <cassert>
#include <algorithm>
#include <iterator> using namespace std; int array[] = {, , , , , , };
const int size = sizeof array / sizeof *array; int partition(int *array, int left, int right)
{
if (array == NULL)
return -; int pos = right;
right--;
while (left <= right)
{
while (left < pos && array[left] <= array[pos])
left++; while (right >= && array[right] > array[pos])
right--; if (left >= right)
break; swap(array[left], array[right]);
}
swap(array[left], array[pos]); return left;
} int getMidIndex(int *array, int size)
{
if (array == NULL || size <= )
return -; int left = ;
int right = size - ;
int midPos = right >> ;
int index = -; while (index != midPos)
{
index = partition(array, left, right); if (index < midPos)
{
left = index + ;
}
else if (index > midPos)
{
right = index - ;
}
else
{
break;
}
} assert(index == midPos);
return array[index];
} void main()
{
int value = getMidIndex(array, size); cout << "value: " << value << endl;
}
寻找kmin算法如下： int findKMin(int *array, int size, int k)
{
if (array == NULL || size <= )
return -; int left = ;
int right = size - ;
int index = -; while (index != k)
{
index = partition(array, left, right); if (index < k)
{
left = index + ;
}
else if (index > k)
{
right = index - ;
}
else
{
break;
}
} assert(index == k);
return array[index];
}
希望本文所述
利用最小堆
此种方法为常用方法，建立一个大小为K的最小堆。每次遍历数组时，需要判断是否需要加入堆中。
堆中存储着的是最大的k个数字，但是若是需要插入堆中，则需要对堆进行调整时间为o(log k)。
全部的时间复杂度为o(n * log k)。
这种方法当数据量比较大的时候，比较方便。因为对所有的数据只会遍历一次，第一种方法则会多次遍历
数组。 如果所查找的k的数量比较大。可以考虑先求出k` ，然后再求出看k`+1 到 2 * k`之间的数字，然后
一次求取。
#include<iostream>
using namespace std; void minHeapify(int a[],int heapSize,int i)
{
int l=*i+;
int r=*i+;
int smallest;
if(l<heapSize && a[l]<a[i])
smallest=l;
else
smallest=i;
if(r<heapSize && a[r]<a[smallest])
smallest=r; if(smallest!=i)
{
swap(a[i],a[smallest]);
minHeapify(a,heapSize,smallest);
}
} void bulidMinHeap(int a[],int n)
{
int heapsize=n;
for(int i=n/-;i>=;i--)
minHeapify(a,heapsize,i); }
#define aSize 10; int main()
{
int a[]={,,,,, ,,,,};
int n=sizeof(a)/sizeof(a[]);
int k=;
bulidMinHeap(a,k);
//如果X比堆顶元素Y小，则不需要改变原来的堆
//如果X比堆顶元素Y大，那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质
for(int i=n-;i>=k;i--)//>=k，因为第0个也存
{
if(a[]<a[i])
{
swap(a[],a[i]);
minHeapify(a,k,);
}
}
for(int i=;i<k;i++)
cout<<a[i]<<endl; }
上面的输出：10,16,14，可以看到第k大的存在a[0],为10.