折半排序问题 C语言
修改好了。
你的主要错误是一个j--写成了j++. 此外,我给你加了一点检查的代码。
此外,count的值是0,你没有统计它,你自己再修改一下。
#include <stdio.h>
main()
{
int a[101],b[101],con,count = 0,i,j,t,n,m=0; /*count用来记录计算次数,a数组是输入数组,b数组时排序以后数组,con用来标记看a数组中的数字是否找到相应的位置,m用来表示b数组长度*/
scanf ("%d",&n);
for ( i = 0;i < n; i++) /*输入数据*/
scanf ("%d",&a[i]);
b[0] = a[0];
m = 1;
for (i = 1;i < n;i++)
{
j = m / 2;
con = 1;
t = compare ( a[i],&b[j],&count,&con,&m,&j); /*conpare函数用来寻找a中数字插入的位置*/
if (t == 200) { /* check abnormal return */
printf("unexpected error\n");
exit(1);
}
printf("m = %d, t = %d\n", m, t);
for (j = m;j > t;j--) /*找到位置以后重新排序*/ // j--, not j++
b[j] = b[j-1];
b[t] = a[i];
if ( t != 200)
m = m+1;
}
printf("the sorted array:\n");
for (i = 0;i < m;i++)
printf ("%d ",b[i]);
printf ("\b\ncount: %d\n",count);
printf("press any key to exit\n");
getch();
}
int
compare (a,b,count,con,m,j) /*j表示所插入的位置*/
int a,*b,*count,*con,*m,*j;
{
int i,k = 0;
if (a > *b)
{
*con = 2 * (*con); /*用整除的方式表示,能被2整除,说明有过比a小的数字,能被3整除说明比较过比a大的数字,而当a在比它比它小的数之间时,被六整除,可以得到所求的位置*/
i = 1;
*j = *j + 1;
}
if (a < *b)
{
*con = 3 * (*con);
i = -1;
*j = *j -1;
k = 1;
}
if (a == *b)
return 200; /*返回值为200说明有数字相同,重新排序操作*/
if (*con % 6 == 0 || *j == -1 || *j == *m) /*当j过大或者过小的时候把数字排列在最左边或者最右边,返回主函数*/
return (*j + k);
else return compare (a,b+i,count,con,m,j); /*当还没找到所需要位置的时候,再次使用该函数找到位置*/
}