快速排序应用--第K小的数

时间复杂度：O(n)；

主要利用快排的partition思想(if(j-l+1>=k)左半边，否则右半边)

int quick_sort(int q[], int l, int r, int k){ if(l>=r)return q[l]; int i=l-1,j=r+1,x=q[l+r>>1]; while(i<j){ while(q[++i]<x); while(q[--j]>x); if(i<j)swap(q[i],q[j]); } if(j-l+1>=k)return quick_sort(q,l,j,k); else return quick_sort(q,j+1,r,k-(j-l+1)); }

 

转载于:https://www.cnblogs.com/programyang/p/11147875.html

相关资源：快速排序求解数组第k小元素