首页 > 代码库 > 关于利用快排思想求第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小数的分析