算法提升之快速排序求第k个数

#includecstdiousing namespace std;constintN1e55;intnum_k0;voidquicksort(intnum[],intl,intr,intk){if(lr){//此时第k个数就是最后一个排好的数在此之前没有给num_k赋值所以这个数就是要找的第k个数num_knum[r];}// 双指针挖坑填坑//取左边为枢轴pivotintpivotnum[l];//此时i的位置被pivot挖走了intholel;intil,jr;while(ij){//左边是坑就一定要先从右边找while(j!holenum[j]pivot){j--;}if(ji){num[i]num[j];holej;}while(i!holenum[i]pivot){i;}if(ij){num[j]num[i];holei;}}//while结束后ijhole//把坑填上num[hole]pivot;if(holek){num_knum[k];return;}//此时hole对应的元素就在最终位置上了直接排除//只递归k存在的那一半if(khole)quicksort(num,l,hole-1,k);elsequicksort(num,hole1,r,k);return;}intmain(){//快速排序intn0;scanf(%d,n);intk0;scanf(%d,k);intnum[N]{0};for(inti0;in;i){scanf(%d,num[i]);}quicksort(num,0,n-1,k-1);printf(%d\n,num_k);return0;}