1.问题

n（1≤n≤100）个正整数（无序的）中，找出第k（k≤n）小的数。注意，第k小的数意味着从小到大排在第k位置的数。

2.解析

3.设计

[int select(int a[], int l, int r, int k){
int group;
int i;
int left,right,mid;
int pivot;
int p,left_num;
if (r-l+1 <= 5) {
insertsort(a,l,r);
return a[l+k-1];
}
group = (r-l+1+5)/5;
for(i=0; ileft = l+5i;
right = (l+5i+4) > r?r:l+5*i+4;
mid = (left+right)/2;
insertsort(a,left,right);
swap(a,l+i,mid);
}
pivot = select(a,l,l+group-1,(group+1)/2);
p = partition(a,l,r,pivot);
left_num = p-l;
if(k == left_num+1)
return a[p];
else if(k<=left_num)
return select(a, l, p-1, k);
else
return select(a, p+1, r, k-left_num-1);
}

4.分析

5.源码

https://github.com/joserfdave/arithmetic/blob/main/%E7%89%B9%E5%AE%9A%E5%88%86%E6%B2%BB%E7%AD%96%E7%95%A5