关于c++:找出一组序列中第k小的元素要求时间复杂度为On

在浏览linuxc中看到一种快排的利用，求最小值，然而要求工夫复杂度放弃在O(n).
实现如下，k代表要找的第k小！

#include<iostream>using namespace std;#define LEN 8int order_partition(int a[], int low, int high,int k){    k = a[low];    while(low<high){        while(low <high && a[high]>= k )            high--;        if(low<high)            a[low++] = a[high];        while( low<high && a[low]<= k )            low++;        if(low<high)            a[high--] = a[low];    }    a[low] = k;    return low;}int order_K_statistic(int a[],int start,int end, int k){    int i;    while(end>=start){        i = order_partition(a,start,end,k);        if(k == i){            return a[i];        }else if(k > i && k < LEN){            return order_K_statistic(a,i+1,end,k);        }else if(k < i && k >= 0){            return order_K_statistic(a,start,i-1,k);        }else{            return -1;        }    }}int main(){    int a[LEN] = { 5, 2, 4, 7, 1, 3, 2, 6 };    int x = 0;    for(int i = 0; i < LEN; i++){        x = order_K_statistic(a,0,LEN-1,i);        printf("%d\n",x);    }    return 0;}

能够剖析一下为什么工夫复杂度是(n)，在最好状况下每次丢掉一半的元素，n+n/2+n/4+n/8+...=2n，均匀状况下的剖析比较复杂，但疾速排序相似，工夫复杂度和最好状况下统一。（摘自《linuxc》）