首页 > 代码库 > 关于利用快排思想求第K小数的分析
关于利用快排思想求第K小数的分析
最近复习快排算法,记得当时最有意思的是可以用快排的partition函数求出第K小数
于是上网搜索一番,发现都只是贴出了代码。无奈只好自己研究了下
利用快排partition求第k小数不得不从partition函数开始说:
快速排序的思想是在一组待排序的数中,找出一个数作为分界,使得它前面的数都比它小,后面的数都比它大。这个数叫做枢轴
当求出一组数的枢轴以后,一组数就可以以枢轴为界限分成两组,我们可以递归的找出这两个组的枢轴,只到每组只有一个数
这里我们应该注意的是,partition函数返回的是枢轴在这组数中的位置,而这个位置,其实就是这组数排序之后的第i个数的位置
因此要求第k小数,就是求在数组排序之后,第k位上的数是多少
于是我们就可以利用partition函数写出我们的求第k小数的函数了
int findk(int arr[],int st,int end,int k){//我们的数组从0号元素开始 if(k<0||st+k-1>end)return -1;//不存在第K小数 if(st==end)return st;//只有一个元素 int q = partition(arr,st,end);//这是枢轴的下标,我们需要知道它在[st..end]中是第几个 int i = q-st+1;//枢轴是第i小数 if(i==k)return i;//找到 else if(i>k)return findk(arr,st,q-1,k);//如果第K小数小于第i小数,则应该在枢轴的左边继续找 else return findk(arr,q+1,end,k-i);//如果第K小数大于第i小数,则应该在枢轴右边找,我们排除了前面i个数,第k小数变成了新的数组中第k-i个数 }
关于partition函数的代码我就不贴了,你来看这篇日志,前提就是会了快排吧。。
关于利用快排思想求第K小数的分析
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。