寻找第k大or第k小的数--＞寻找中位数

快排思想，选取数组中第一个元素e为参考元素，利用partition() 使得数组左边的元素全都不大于e，数组右边的元素全都不小于e–>升序排序

设数组长度为n，若e的下标m恰好为n-k，则寻找到第k大的元素，即e；若e的下标m恰好为k-1，则寻找到第k小的元素，即e

如果m>n-k，在e元素的左半边递归寻找；如果m<n-k, 在e元素的右半边递归寻找

如果m>k-1，在e元素的左半边递归寻找；如果m<k-1, 在e元素的右半边递归寻找

寻找中位数–>k = (n/2) + (n%2)，数组长度为奇数时向上取整，即(n/2) + 1

int Partition(int* arr,int low ,int high)
{
    int temp = arr[low];
    while(low < high)
    {
        while(low < high && arr[high] >= temp)
            high--;
        arr[low] = arr[high];
        while(low < high && arr[low] <= temp)
            low++;
        arr[high] = arr[low];
    }
    arr[low] = temp;//确定参考元素的位置
    return low;
}
int KthElement(int * arr,int low, int high,int n ,int k)
{
    if(arr == nullptr || low >= high || k > n)//边界条件和特殊输入的处理
        return 0;
    int pos = Partition(arr,low,high);
    while(pos != n  - k)
    {
        if(pos > n - k)
        {
            high = pos - 1;
            pos = Partition(arr,low,high);
        }
        if(pos < n - k)
        {
            low = pos + 1;
            pos = Partition(arr,low,high);
        }
    }
    return arr[pos];//pos=n-k,递归结束
 
}
 
int main()
{
 
   int a[]={1,5,5,7,88,11};
   cout<<KthElement(a,0,5,6,2);
   
}

最后

以上就是疯狂荷花为你收集整理的寻找第k大or第k小的数--＞寻找中位数的全部内容，希望文章能够帮你解决寻找第k大or第k小的数--＞寻找中位数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。