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

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

#include<iostream>
using namespace std;
#define LEN 8
int 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》）