找出一组序列中第k小的元素(要求时间复杂度为O(n))

在阅读linuxc中看到一种快排的应用,求最小值,但是要求时间复杂度保持在O(n).
实现如下,k代表要找的第k小!

#include using namespace std; #define LEN 8 int order_partition(int a[], int low, int high,int k){ k = a[low]; while(low= k ) high--; if(low=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; }

【找出一组序列中第k小的元素(要求时间复杂度为O(n))】可以分析一下为什么时间复杂度是Θ(n),在最好情况下每次丢掉一半的元素,n+n/2+n/4+n/8+...=2n,平均情况下的分析比较复杂,但快速排序类似,时间复杂度和最好情况下一致。(摘自《linuxc》)

    推荐阅读