数组中第k小的数字 - c++编程基础

从大量数字中寻找数据的变化规律，用平均数或中位数都有可能受异常值的影响，方差、标准差是衡量其中一个数据与平均值的偏差程度。

全矩也有可能受异常值的影响。当然四分位矩是个不错的选择。

为减少算法的耗时和复杂度，只需要得到上四分位位数和下四分位位数；不排序也可以得到想要的结果。

发现百度出来的寻找第K小或K大的数字程序各种各样，记得以前在算法导论里有关于寻找第K个小的数字或第K个大的数字，算法的期望复杂度为O(n)，

，至于推导过程可以参考算法导论第9章，代码贡献给大家。

#include   
#include   
#include   
  
using namespace std;  
  
template  
int partion(T *A,int p,int r)  
{  
    int i,t;  
    T x;  
    x=A[r];  
    i=p-1;  
    for (int j=p;j  
int random_partion(T *A,int p,int r)  
{  
    int rand_base=r-p+1;  
    //............有重复数字，会有为rand_base的情况，没有深入思考，欢迎大量修正  
    if (rand_base   ==  0)  
    {  
        return  A[p];  
    }  
    //..............................................................  
    int i = p+rand()%(rand_base);  
    int t=A[i];  
    A[i]=A[r];  
    A[r]=t;  
    return partion(A,p,r);  
}  
  
template




  
T random_serchn(T *A,int p,int r,int i)   //搜索数组中第i个数，期望运行时间为o(n)  
{  
    int q;  
    int k;  
    if (p==r)  
    {  
        return A[p];  
    }  
    q=random_partion(A,p,r);  
    k=q-p+1;  
    if (q==i)  
    {  
        return A[q];  
    }  
  
    else if (i

写完程序，分析完算法，在此做个小广告，欢迎大家访问我的淘宝小店，专卖自己家种的枸杞 http://bxj2001.taobao.com/；

只需要在旺旺告诉我从文章中的链接而来，一律有优惠。