2 yi zhangzhi yi_zhangzhi 于 2016.04.03 16:55 提问

求中位数的中位数那里好像有问题,我找不出来。求帮忙!感激! 10C

代码求第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("\n输出数组下标从p到p+(r-p-4)/5的元素:\n");
    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("\n拟中位数:%d\n",x);
    i=Partition(a,p,r,x);
    int j=i-p+1;
    printf("输出p-r:\n");
    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\n",j);
    return 0;
}

3个回答

caozhy
caozhy   Ds   Rxr 2016.04.03 18:36

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

yi_zhangzhi
yi_zhangzhi int x=Select(a,p,p+(r-p-4)/5,(r-p+6)/10)是递归调用Select在中位数中再去找中位数,但是是错的
一年多之前 回复
CSDNXIAON
CSDNXIAON   2016.04.06 17:02

求中位数的问题
----------------------同志你好,我是CSDN问答机器人小N,奉组织之命为你提供参考答案,编程尚未成功,同志仍需努力!

CSDNXIAOD
CSDNXIAOD   2016.04.06 17:02

求中位数的问题
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!