郁闷呀, 难道 5<0 吗?咋回事
郁闷呀, 难道 5<0 吗?怎么回事?
int n;
int x[N], y[N], id[N];
int compare(int ij, int tx, int ty)
{
if( x[ij] > tx ) return 1;
if( x[ij] < tx ) return -1;
if( y[ij] > ty ) return 1;
if( y[ij] < ty ) return -1;
return 0;
}
void swap(int i, int j)
{
int temp;
temp = x[i]; x[i] = x[j]; x[j] = temp;
temp = y[i]; y[i] = y[j]; y[j] = temp;
}
void sort(int l, int r)
{
int i=l, j=r, a=0;
int tx = x[(i+j)>>1], ty = y[(i+j)>>1];
do
{
printf("%c %d\n", 'i', i);
while( compare(i, tx, ty)== -1 ) i++;
printf("%c %d\n", 'i', i);
printf("%c %d\n", 'j', j);
while( compare(j, tx, ty)== 1 ) j--;
printf("%c %d\n", 'j', j);
if( i<=j )
{
swap(i,j);
i++;
j--;
}
}while( i<=j );
if( i< r ) sort(i, r);
if( j> l ) sort(l, j);
}
main
{
scanf("%d", &n);
for(i=1; i<=n; i++) scanf("%d %d", &x[i], &y[i]);
sort( 1, n );
}
测试数据
5
0 0
2 0
3 0
1 1
2 2
我晕了,那个 x[i] 和 tx 比较到是没啥问题, 但是 x[j] 和 ty 比较就不能理解了
就拿 sort(i, n) 来说,ty=0 吧,第一次 compare ,y[j]=2呀,明显 2>ty=0吧,然后 return 1 啊,再 j--,可事实上没有这样做,输出
i 1
i 3
j 5
j 5
怎么回事呀,是我错了吗?是的话我是怎么错的,请教
------解决方案--------------------
if( x[ij] < tx ) return -1;
cmopare函数,那里有 4个 if ,当 j=5 时 ,符合 if( x[ij] < tx ) return -1;
所以 j 没有 -1
int n;
int x[N], y[N], id[N];
int compare(int ij, int tx, int ty)
{
if( x[ij] > tx ) return 1;
if( x[ij] < tx ) return -1;
if( y[ij] > ty ) return 1;
if( y[ij] < ty ) return -1;
return 0;
}
void swap(int i, int j)
{
int temp;
temp = x[i]; x[i] = x[j]; x[j] = temp;
temp = y[i]; y[i] = y[j]; y[j] = temp;
}
void sort(int l, int r)
{
int i=l, j=r, a=0;
int tx = x[(i+j)>>1], ty = y[(i+j)>>1];
do
{
printf("%c %d\n", 'i', i);
while( compare(i, tx, ty)== -1 ) i++;
printf("%c %d\n", 'i', i);
printf("%c %d\n", 'j', j);
while( compare(j, tx, ty)== 1 ) j--;
printf("%c %d\n", 'j', j);
if( i<=j )
{
swap(i,j);
i++;
j--;
}
}while( i<=j );
if( i< r ) sort(i, r);
if( j> l ) sort(l, j);
}
main
{
scanf("%d", &n);
for(i=1; i<=n; i++) scanf("%d %d", &x[i], &y[i]);
sort( 1, n );
}
测试数据
5
0 0
2 0
3 0
1 1
2 2
我晕了,那个 x[i] 和 tx 比较到是没啥问题, 但是 x[j] 和 ty 比较就不能理解了
就拿 sort(i, n) 来说,ty=0 吧,第一次 compare ,y[j]=2呀,明显 2>ty=0吧,然后 return 1 啊,再 j--,可事实上没有这样做,输出
i 1
i 3
j 5
j 5
怎么回事呀,是我错了吗?是的话我是怎么错的,请教
------解决方案--------------------
if( x[ij] < tx ) return -1;
cmopare函数,那里有 4个 if ,当 j=5 时 ,符合 if( x[ij] < tx ) return -1;
所以 j 没有 -1