问题描述

求中位数的中位数那里好像有问题，我找不出来。求帮忙！感激！

代码求第k小的数。编译过了，求中位数的中位数结果不对

 #include<stdio.h>
#include<stdlib.h>
void paixu(int *a,int p,int r)
{
    int b;
    for(int i=p;i<r;i++)
    {
        for(int j=r;j>i;j--)
        {
            if(a[j]>a[j-1])
            {
                b=a[j];
                a[j]=a[j-1];
                a[j-1]=b;
            }
        }
    }
}

void Swap(int *i,int *j)
{
    int b;
    b=*i;
    *i=*j;
    *j=b;
}

int Partition(int *a,int p,int r,int x)
{
    int i=p,j=r+1;
    while(true)
    {
        while(a[++i]<x&&i<r);
        while(a[--j]>x);
        if(i>=j)
            break;
        Swap(&a[i],&a[j]);
    }
    a[p]=a[j];
    a[j]=x;
    return j;
}

int Select(int *a,int p,int r,int k)
{
    int t;
    if(r-p<10)
    {
        paixu(a,p,r);
        return a[p+k-1];
    }
    for(int i=0;i<=(r-p-4)/5;i++)
    {
        paixu(a,p+5*i,p+5*i+4);
        Swap(&a[p+5*i+2],&a[p+i]);
    }
    printf("
输出数组下标从p到p+(r-p-4)/5的元素：
");
    for(int o=p;o<=p+(r-p-4)/5;o++)
    {
        printf("%3d",a[o]);
    }
    int x=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);
    printf("
拟中位数：%d
",x);
    i=Partition(a,p,r,x);
    int j=i-p+1;
    printf("输出p-r：
");
    for(int q=p;q<=r;q++)
    {
        printf("%3d",a[q]);
    }
    if(k<=j)
        return Select(a,p,i,k);
    else
        return Select(a,i+1,r,k-j);
}

int main()
{
    int a[20]={11,12,14,10,13,9,8,5,4,6,1,2,3,7,16,17,18,19,20,15};
    int k,j;
    printf("k:");
    scanf("%d",&k);
    j=Select(a,0,19,k);
    printf("第k小的元素为：%d
",j);
    return 0;
}

解决方案

int x=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);
这个是什么意思，你的select其实就是一个快速排序，然后找中间下标的那个。

http://www.cnblogs.com/RootJie/archive/2012/02/13/2349649.html

甚至你可以直接使用标准库的qsort

解决方案二：

求中位数的问题

解决方案三：

求中位数的问题