数组中第k小的数字

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

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

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

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

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

#include <stdlib.h>  
#include <iostream>  
#include <vector>  
  
using namespace std;  
  
template<class T>  
int partion(T *A,int p,int r)  
{  
    int i,t;  
    T x;  
    x=A[r];  
    i=p-1;  
    for (int j=p;j<r;j++)  
    {  
        if (A[j]<=x)  
        {  
            i=i+1;  
            t=A[i];  
            A[i]=A[j];  
            A[j]=t;  
        }  
    }  
    t=A[i+1];  
    A[i+1]=A[r];  
    A[r]=t;  
    return (i+1);  
}  
  
template<class T>  
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<class T>  
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<k)  
    {  
        return random_serchn(A,p,q-1,i);  
    }  
    else  
        return random_serchn(A,q+1,r,i);  
  
}  
  
  
int main(int argc, char **argv)  
{  
    int a[10]={6,6,3,5,6,6,0,4,6,6};  
      
    cout<<random_serchn(a,0,9,7)<<endl;  
  
    return 0;

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

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

补充：软件开发 , C++ ,