我在学习线性时间选择算法,编写如下程序,算法要求是找到n个元素中第k小的元素:
//线性时间选择
#include <stdio.h>
void bubbleSort(int *a,int p,int r);
int Partition(int *a,int p,int r,int val);
int Select(int *a,int p,int r,int k);
void swap(int *u,int *v);
void swap(int *u,int *v)
{
int temp;
temp=u;
u=v;
v=temp;
}
void bubbleSort(int *a,int p,int r)
{
int i,j;
for(i=p; i<r; i++)
{
for( j=i+1; j<=r; j++)
{
if(a[j]<a[i]) swap(a[i],a[j]);
}
}
}
int Partition(int *a,int p,int r,int val)
{
int pos;
int q,i,j,x;
for( q=p; q<=r; q++)
{
if(a[q]==val)
{
pos=q;
break;
}
}
swap(a[p],a[pos]);
i=p; j=r+1; x=a[p];
while(1)
{
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 s,t;
int i,j,n,x;
if(r-p<75)
{
bubbleSort(a,p,r);
return a[p+k-1];
}
//找中位数的中位数,r-p-4即上面所说的n-5
for( i=0; i<=(r-p-4)/5; i++) //把每个组的中位数交换到区间[p,p+(r-p-4)/4]
{
s=p+5*i; t=s+4;
for( j=0; j<3; j++) //冒泡排序,从后开始排,结果使得后三个数是排好顺序的(递增)
{
for( n=s; n<t-j; n++)
{
if(a[n]>a[n+1]) swap(a[n],a[n+1]);
}
}
swap(a[p+i],a[s+2]);//交换每组中的中位数到前面
}
//(r-p-4)/5表示组数-1,则[p,p+(r-p-4)/5]的区间长度等于组数
x=Select(a,p,p+(r-p-4)/5,(r-p+1)/10);//求中位数的中位数
/*
(r-p+1)/10 = (p+(r+p-4)/5-p+1)/2
*/
i=Partition(a,p,r,x); j=i-p+1;
if(k<=j) return Select(a,p,i,k);
else return Select(a,i+1,r,k-j);
}
int main(void)
{
int x,i;
//数组a存了0-79
int a[80]= {3,1,7,6,5,9,8,2,0,4,13,11,17,16,15,19,18,12,10,14,23,21,27,26,25,29,28,22,20,24,33,31,37,36,35,39,38,32,30,34,43,41,47,46,45,49,48,42,40,44,53,51,57,56,55,59,58,52,50,54,63,61,67,66,65,69,68,62,60,64,73,71,77,76,75,79,78,72,70,74,
};
scanf("%d",&x);
printf("The %d smallest number is %d\n",x,Select(a,0,79,x));
return 0;
}
运行结果如下:
请问是哪有问题,应该怎么修改。